Создать двоичное дерево поиска из списка целых чисел

Question

Есть ли способ реализовать программу Prolog, которая получает в качестве входных данных список целых чисел и создает двоичное дерево поиска? Если входное значение равно 3 6 1 5, программа должна вывести (узел 3 нулевой) (узел 6 3) (узел 1 3) (узел 5 6), выводом является один узел за раз, включая его родителя.

Answer 1

Деревья уже существуют в библиотеке SWI-Prolog (ассо c) : списки ассоциаций.

Пример:

?- empty_assoc(Tree0),put_assoc(3,Tree0,three,Tree1),put_assoc(6,Tree1,six,Tree2),put_assoc(1,Tree2,one,Tree3),put_assoc(5,Tree3,five,Tree).
Tree0 = t,
Tree1 = t(3, three, -, t, t),
Tree2 = t(3, three, >, t, t(6, six, -, t, t)),
Tree3 = t(3, three, -, t(1, one, -, t, t), t(6, six, -, t, t)),
Tree = t(3, three, >, t(1, one, -, t, t), t(6, six, <, t(5, five, -, t, t), t)).

Дерево реализовано как как AVL дерево , которое является сбалансированным двоичным деревом.