Деревья

Упражнение 1. Определите предикат, который проверяет принадлежность элемента двоичному дереву.

Двоичное дерево поиска — это конечное корневое дерево, в котором элементы левого поддерева любой вершины меньше этой вершины, а элементы правого поддерева не меньше нее. На рис. 9.2 приведен пример двоичного дерева поиска.

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

Предикат insert/2 вставляет элемент в двоичное дерево поиска так, чтобы оно оставалось деревом поиска. Предикат get_nd/2 недетерминированно возвращает вершины заданного уровня. Предикат height/1 возвращает высоту дерева, предикат height_nd/2 недетерминированно возвращает высоту ветвей дерева. Высота дерева определяется как максимальная из высот ветвей. Предикаты sum/1 и count/1 вычисляют соответственно сумму элементов дерева и количество четных вершин. В подсчетах используются накопители. Предикат replace/3 заменяет элементы дерева с заданным значением другими элементами.

domains
    binTree{Elem} = bt(binTree{Elem}, Elem, binTree{Elem}); leaf.

class predicates      % построение дерева предков
    createBinTree: (unsigned, positive) -> binTree{unsigned}.
    createBinTree: (unsigned, positive, binTree{unsigned})
        -> binTree{unsigned}.
    insert: (Elem, binTree{Elem}) -> binTree{Elem}.
clauses
    createBinTree(R, N) = createBinTree(R, N, leaf).

    createBinTree(_, 0, Tree) = Tree:- !.
    createBinTree(R, N, Tree) =
        createBinTree(R, N - 1, insert(math::random(R), Tree)).

    insert(X, leaf) = bt(leaf, X, leaf).
    insert(X, bt(LTree, Y, RTree)) = bt(insert(X, LTree), Y, RTree):-
        X < Y,
        !.
    insert(X, bt(LTree, Y, RTree)) = bt(LTree, Y, insert(X, RTree)).

class predicates
    print: (binTree{Elem}).
    print: (binTree{Elem}, charCount).
clauses
    print(BinTree):-
        print(BinTree, 0).

    print(leaf, _).
    print(bt(LeftTree, Elem, RightTree), N):-
        print(LeftTree, N + 1),
        write(string::create(N, "\t"), Elem), nl,
        print(RightTree, N + 1).

class predicates      % вершины заданного уровня
    get_nd: (binTree{Elem}, positive) -> Elem nondeterm.
clauses
    get_nd(bt(_, A, _), 0) = A:- !.
    get_nd(bt(LTree, _, _), N) = get_nd(LTree, N - 1).
    get_nd(bt(_, _, RTree), N) = get_nd(RTree, N - 1).

class predicates      % высота дерева
    height: (binTree{Elem}) -> integer.
    height_nd: (binTree{Elem}, integer) -> integer nondeterm.
clauses
    height(Tree) = list::maximum([N || N = height_nd(Tree, -1)]).

    height_nd(leaf, N) = N.
    height_nd(bt(LTree, _, _), N) = height_nd(LTree, N + 1).
    height_nd(bt(_, _, RTree), N) = height_nd(RTree, N + 1).

class predicates      % подсчеты
    sum: (binTree{unsigned}) -> unsigned.
    sum: (binTree{unsigned}, unsigned) -> unsigned.
    count: (binTree{unsigned}) -> positive.
    count: (binTree{unsigned}, positive) -> positive.
clauses
    sum(Tree) = sum(Tree, 0).    % сумма всех вершин

    sum(leaf, N) = N.
    sum(bt(LTree, A, RTree), N) = sum(RTree, sum(LTree, N) + A).

    count(Tree) = count(Tree, 0).  % количество четных вершин

    count(leaf, N) = N.
    count(bt(LTr, A, RTr), N) = count(RTr, count(LTr, N) + C):-
        C = if A mod 2 = 0 then 1 else 0 end if.

class predicates      % замена заданных вершин
    replace: (binTree{unsigned}, unsigned, unsigned)
        -> binTree{unsigned}.
clauses
    replace(leaf, _, _) = leaf.
    replace(bt(LTree, V, RTree), A, B) =
            bt(replace(LTree, A, B), C, replace(RTree, A, B)):-
        C = if V = A then B else V end if.

    run():-
        Tree = createBinTree(20, 20),
        print(Tree),
        write("\n\nПоколение 3: ", [Elem || Elem = get_nd(Tree, 3)]),
        write("\nВысота дерева: ", height(Tree)),
        write("\nСумма элементов дерева: ", sum(Tree)),
        write("\nКоличество четных вершин дерева: ", count(Tree)),
        write("\nЗамена нулевых элементов на 100:\n\n"),
        Tree1 = replace(Tree, 0, 100),
        print(Tree1),
        _ = readLine().

Предикат maximum возвращает максимальный элемент списка.

9.2. Произвольное дерево

В произвольном корневом дереве каждая вершина может иметь любое количество поддеревьев (рис. 9.1 (b)).

Полиморфный домен таких деревьев так же, как и в предыдущем случае, определяется рекурсивно:

domains
    tree{Elem} = t(Elem, tree{Elem}*).

Бинарная структура хранит элемент дерева и список его поддеревьев.

В следующей программе рекурсивно строится дерево потомков человека. Дерево строит предикат createTree/1. Определение этого предиката содержит всего одно правило. Список поддеревьев получается как результат применения предиката высшего порядка list::map/2 к списку "детей" корня дерева. Он строит для каждой вершины поддерево с корнем в этой вершине.

Дерево выводится на печать (предикат print/1), при этом корень дерева располагается слева, а поддеревья справа. Вершины одного уровня находятся на одинаковом расстоянии от левой границы окна консоли. В определении этого предиката участвует предикат второго порядка list::forAll/2.

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

class predicates
    createTree: (string Name) -> tree{string}.
    createTreeList: (string Name*) -> tree{string}*.
clauses
    createTree(X) = t(X, createTreeList([Y || parent(X, Y)])).

    createTreeList([X | L]) = [createTree(X) | createTreeList(L)].
    createTreeList([]) = [].

class predicates
    print: (tree{Elem}).
    print: (tree{Elem}, charCount).
    printTreeList: (tree{Elem}*, charCount).
clauses
    print(Tree):-
        print(Tree, 0).

    print(t(X, TreeList), N):-
        write(string::create(N, "\t"), X), nl,
        printTreeList(TreeList, N + 1).

    printTreeList([T | L], N):-
        print(T, N),
        printTreeList(L, N).
    printTreeList([], _).

В программе также строится список вершин дерева. Предикат get_nd/1 недетерминированно возвращает произвольную вершину дерева.

class facts - rel
    parent: (string Родитель, string Ребенок).
    male: (string).
    female: (string).

domains
    tree{Elem} = t(Elem, tree{Elem}*).

class predicates    % построение дерева потомков
    createTree: (string Name) -> tree{string}.
clauses
    createTree(X) =
        t(X, list::map([Y || parent(X, Y)], {(Z) = createTree(Z)})).

class predicates    % печать дерева
    print: (tree{Elem}).
    print: (tree{Elem}, charCount).
clauses
    print(Tree):-
        print(Tree, 0).

    print(t(X, TreeList), N):-
        write(string::create(N, "\t"), X), nl,
        list::forAll(TreeList, {(T):- print(T, N + 1)}).

class predicates    % обход дерева
    get_nd: (tree{Elem}) -> Elem multi.
clauses
    get_nd(t(A, _)) = A.
    get_nd(t(_, TreeList)) = get_nd(list::getMember_nd(TreeList)).

    run():-
        file::consult("fam.txt", rel),
        Tree = createTree("Иван"),
        print(Tree), nl,
        write([Elem || Elem = get_nd(Tree)]),
        _ = readLine().

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

    open core, console, list

domains
    tree{Elem} = t(Elem, tree{Elem}*).

class facts
    arc: (unsigned, unsigned).
clauses
    arc(1, 2).    arc(1, 3).    arc(1, 4).     arc(2, 5).    arc(2, 6).
    arc(3, 7).    arc(7, 8).    arc(7, 9).     arc(7, 10).  arc(9, 11).

class predicates
    createTree: (unsigned) -> tree{unsigned}.
    print: (tree{Elem}).
    print: (tree{Elem}, charCount).
clauses
    createTree(X) = 
        t(X, map([Y || arc(X, Y)], {(Z) = createTree(Z)})).

    print(Tree):-
        print(Tree, 0).

    print(t(X, TreeList), N):-
        write(string::create(N, "\t"), X), nl,
        forAll(TreeList, {(T):- print(T, N + 1)}).

class predicates      % вершины заданного уровня
    get_nd: (tree{Elem}, positive) -> Elem nondeterm.
clauses
    get_nd(t(A, _), 0) = A:- !.
    get_nd(t(_, TrList), N) = get_nd(getMember_nd(TrList), N - 1).

class predicates      % высота дерева
    height: (tree{Elem}) -> integer.
    height_nd: (tree{Elem}, integer) -> integer nondeterm.
clauses
    height(Tree) = maximum([N || N = height_nd(Tree, 0)]).

    height_nd(t(_, []), N) = N.
    height_nd(t(_, TreeList), N) =
        height_nd(getMember_nd(TreeList), N + 1).

class predicates      % подсчеты
    sum: (tree{unsigned}) -> unsigned.
    count: (tree{Elem}) -> positive.
clauses
    % сумма четных вершин
    sum(t(A, TrList)) = C + fold(TrList, {(T, S) = sum(T) + S}, 0):-
        C = if A mod 2 = 0 then A else 0 end if.
    % количество всех вершин
    count(t(_, TrList)) = 1 + fold(TrList, {(T, S) = count(T) + S}, 0).

class predicates      % замена заданных вершин
    replace: (tree{unsigned}, unsigned, unsigned) -> tree{unsigned}.
clauses
    replace(t(V, TreeList), A, B) =
            t(C, map(TreeList, {(T) = replace(T, A, B)})):-
        C = if V = A then B else V end if.

    run():-
        Tree = createTree(1),
        print(Tree),
        write("\n\nПоколение 3: ", [Elem || Elem = get_nd(Tree, 3)]),
        write("\nВысота дерева: ", height(Tree)),
        write("\nСумма четных элементов дерева: ", sum(Tree)),
        write("\nКоличество вершин дерева: ", count(Tree)),
        write("\nЗамена 9 на 100:\n\n"),
        Tree1 = replace(Tree, 9, 100),
        print(Tree1),
        _ = readLine().

Упражнение 2. Определите предикаты sum/1, count/1 и replace/3, которые предназначены для вычисления суммы четных элементов дерева, количества всех вершин дерева и замены одного элемента другим, не используя предикаты высшего порядка fold и map класса list. Введите дополнительные предикаты, которые обрабатывают списки деревьев.

В языке Visual Prolog имеются реализации красно-черных деревьев (класс redBlackTree), цифровых деревьев (класс radixTree) и др.

Упражнения