Здравствуйте, такая проблема, не могу понять как элемент добавляется в дерево.
Вот правила добавления:
1) результат добавления элемента Х к пустому дереву есть дерево tree(X, nil, nil);
2) если Х совпадает с корнем дерева Т, то Т1=Т (не допускается дублирования);
3) если корень дерева Т больше, чем Х, то Х вносится в левое поддерево Т;
4) если корень дерева Т меньше, чем Х, то Х вносится в правое поддерево Т.
Кажется всё просто, но это до тех пор, пока не дошло до реализации:

Вторая цель: тут вроде всё понятно, если дерево пустое, мы заносим в него первый элемент.
Третья цель: вот тут начинаются непонятки, много раз дебагером прошёлся, всё равно понять не могу.
Вот последовательность действий пролога:
1) Пропускаем первое правило, так как Т2 не nill,
2) Пропускаем второе правило, так как Т2 не равно Т3.
3) Пропускаем третье правило, так как K > X.
4) Так как K < X, рекурсивно вызываем предикат Add, k = 1, X = 2, R = nill, R2 = _
5) Первое правило выполняется - так как R = nill, каким-то образом, значение 2 заносится в правое поддерево T2, и всё это становится значением Т3.
Как мы попадаем в правое поддерево? Почему, если мы подали в качестве второй переменной правое поддерево, то мы в него заносим значение третьей переменной? 

Это что, форум риторических вопросов и я не туда попал?

Во-первых, не факт, что все, кто может ответить, сидят на форуме постоянно и ждут, когда Вы что-то напишете.   Во-вторых, вот отсюда

следует, что Вы более чем слабо представляете себе механизм работы программ на Прологе (да и не только Прологе). Чему может быть "не равно" T3, если в момент вызова эта переменная еще ни с чем не связана? 

Соответственно, остальные вопросы, скажем так, не вполне осмысленны.

Я только что начал изучать Пролог, поэтому естественно, что я слабо представляю себе механизм работы программ на Прологе. Если бы я понимал механизм я бы не задал вопрос.
 
Я исходя из правил вопрос задавал.
Заранее спасибо

А T2 связана, вот я и подумал, что протускается второе правило именно по причине неравенства, то есть 
очень простой пример: 

Он выведет, что А=глаз. Объясните кто-нибудь про деревья если не сложно пожалуйста.

Это сообщение отредактировал(а) Fredwriter - 26.4.2012, 04:43

Нет. Если аргумент предиката (или его "составные части") в момент вызова не связаны, то никакого сопоставления с образцом при вызове не происходит, и аргумент играет роль обычного выходного параметра.


Так что объяснить-то? С учетом написанного выше Ваши начальные вопросы теряют смысл, их сначала надо заменить.

Хорошо, вопросы следующие. Почему пропускается втророе правило? Почему только четвёртое подошло? Ну и дальше: Как мы попадаем в правое поддерево? Почему, если мы подали в качестве второй переменной правое поддерево, то мы в него заносим значение третьей переменной?  

Потому что в вершине дерева, являющегося вторым аргументом, находится элемент, не совпадающий со значением первого аргумента.


При подстановке значений аргументов в третье правило получается, что K=1, X=2, соответственно, условие K>X не выполняется.


Если мы добрались до четвертого правила, то в нем значение первого аргумента добавляется как раз в правое поддерево. Вот эта вот строчка:

означает примерно следующее: если значение первого аргумента больше, чем вершина дерева, в которое это число надо добавить, то надо попытаться добавить это же число в правое поддерево исходного дерева, после чего "собрать" результат из старой вершины, старого левого поддерева и нового (с добавленным элементом) нового поддерева.


А вот именно этот вопрос я понять и не могу (от изменения порядка пары слов смысла больше не стало). Очевидно, что Вы что-то не понимаете, но по Вашему вопросу трудно догадаться даже о том, что Вы могли бы иметь в виду.

Вот, точно, спасибо, Фантом.

У меня примерно такое же объяснение, но оно обравается на одном моменте, который я и описал в последнем вопросе.

Четвертое правило:
x = 2 
R = nil, (так как это правое поддререво)
R1 = _,
    Вызывается первое правило c этими значениями, R1 становится равным tree(2, nil, nil), получается следующее

Каким образом эта запись записала в правое поддерево? Мы просто выполнили факт, в котором через запятую в предикате били перечислены три переменные 2, nil, и объект tree(2, nil, nil). Не понимаю. Теперь понимаете, что я не понимаю? 



Это сообщение отредактировал(а) Fredwriter - 27.4.2012, 03:52

Да, похоже, что понял.

Давайте разбирать по порядку. 
1) Исходно вызывается предикат с таким набором параметров (если подставить все, уже известное):  add(2,tree(1,nil,nil),T3), причем T3 в момент вызова не конкретизирована и должна в итоге содержать возвращаемое значение
2) Система, как мы уже выяснили, доходит до четвертого правила. После этого при получении заголовка вида: 

содержимое конкретизированных аргументов (первых двух) "разбирается" по шаблону. Х принимает значение 2, K - 1, L и R - nil. После этого также по шаблону собирается возвращаемое значение, которое должно попасть в третий аргумент. K и L системе уже известны, они просто переносятся в третий аргумент, а вот R1 надо откуда-то получить.
3) Для получения R1 служит правая часть четвертого правила. Условие K<X, как мы уже знаем, проходится, после чего следует вызов add(X, R, R1). При этом X и R система уже знает, эти значения конкретизированы, а R1 - еще нет, и задача тем самым сводится к предыдущей. В итоге новый вызов add отрабатывает, возвращает новое правое поддерево в R1, и образовавшееся значение используется для завершения сборки возвращаемого значения третьего аргумента. 

Грубо говоря, можно представлять себе, что пролог-система проходится по правилу сначала слева направо, постепенно конкретизируя значения всех переменных, где это возможно, а затем возвращается справа налево, продолжая ту же конкретизацию.

Спасибо, Фантом, всё теперь стало понятно, просто, как обычно невнимательно посмотрел.