VPF::Бинарное упорядоченное дерево

blur

Дата 28.4.2007, 19:16 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 126
Регистрация: 9.11.2004

Репутация: нет
Всего: 1

Мне нужно создать бинарное упорядоченное дерево. Есть предикат, который создает узел в дереве:

Код


insert_leaf(X, empty, tree(X, empty, empty)).
insert_leaf(X, tree (Y, L, R), tree(Y, L1, R)):-
        X < Y,!,insert_leaf(X, L, L1).
insert_leaf(X, tree(Y, L, R), tree(Y, L, R1)):-
        X > Y,!,insert_leaf(X, R, R1).

дерево получается хоть и упорядоченное, но не бинарное (если ввести 1,2,3, то получается 1-корень,2-правое,3-правое, а надо 2-корень, 1-левое, 3-правое). Помогите пожалуйста модифицировать данный предикат.

Artemios

Дата 29.4.2007, 08:05 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 6
Всего: 50

Цитата(blur @ 28.4.2007, 20:16

)

Нет, все делается, как и должно быть. Дерево бинарное, но каждая левая ветвь остается пустой, т.к. на вход подаешь последовательность чисел уже в упорядоченном виде. Структура упорядоченного дерева будет зависеть от того, в какой последовательности подаешь числа. Смотри:

Цитата

?- insert_leaf(1,empty,X),insert_leaf(2,X,Y),insert_leaf(3,Y,Z).

X = tree(1, empty, empty)
Y = tree(1, empty, tree(2, empty, empty))
Z = tree(1, empty, tree(2, empty, tree(3, empty, empty)))

Yes
?- insert_leaf(3,empty,X),insert_leaf(2,X,Y),insert_leaf(1,Y,Z).

X = tree(3, empty, empty)
Y = tree(3, tree(2, empty, empty), empty)
Z = tree(3, tree(2, tree(1, empty, empty), empty), empty)

Yes
?- insert_leaf(2,empty,X),insert_leaf(3,X,Y),insert_leaf(1,Y,Z).

X = tree(2, empty, empty)
Y = tree(2, empty, tree(3, empty, empty))
Z = tree(2, tree(1, empty, empty), tree(3, empty, empty))

Yes
?-

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

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

blur

Дата 29.4.2007, 12:11 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 126
Регистрация: 9.11.2004

Репутация: нет
Всего: 1

Artemios,

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

Artemios

Дата 29.4.2007, 16:10 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 6
Всего: 50

blur, Для сбалансированного дерева (АВЛ-дерева) высота левого и правого поддеревьев отличается не более чем на 1.
Алгоритм добавления вершины в АВЛ-дерево

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

Вообще, в сети много про них пишут. Посмотри, если не будет получаться -- пиши.

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

blur

Дата 30.4.2007, 00:44 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 126
Регистрация: 9.11.2004

Репутация: нет
Всего: 1

Цитата(Artemios @ 29.4.2007, 16:10

)

Вообще, в сети много про них пишут. Посмотри, если не будет получаться -- пиши.

Ну с теорией я вроде разобрался, но все примеры по ссылкам не на прологе. Как это сделать например на си мне понятно. Так что не мог бы ты мне написать нужный предикат - лабу скоро нужно сдавать smile

Artemios

Дата 1.5.2007, 00:07 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 6
Всего: 50

Ну например АВЛ-дерево (идеально сбалансированное). Сделал "в лоб" (то есть не оптимально) по картинкам из ссылки добавление вершины в АВЛ-дерево :

Код


% Дерево представляем в виде: 
% tr(Корень,ЛевоеПоддерево,ПравоеПоддерево,ВысотаДерева)

% вставка в упорядоченное дерево
ins(X,nil,tr(X,nil,nil,1)).
ins(X,tr(Y,L,R,H),tr(Y,L2,R,H2)):-
    X<Y, H2 is H+1, ins(X,L,L2).
ins(X,tr(Y,L,R,H),tr(Y,L,R2,H2)):-
    X>Y, H2 is H+1, ins(X,R,R2).

height(nil,0).
height(tr(_,_,_,H),H).

% малое правое вращение
rot_right_small(
    tr(A,L,tr(B,C,R,_),_),
    tr(B,tr(A,L,C,Ha2),R,Hb2)
    ):-
        height(C,Hc),
        height(R,Hr),
        Hc < Hr,
        height(L,Hl),
        Ha2 is max(Hl,Hc)+1,
        Hb2 is max(Ha2,Hr)+1.

% большое правое вращение
rot_right_big(
    tr(A,L,tr(B,tr(C,M,N,Hc),R,_),_),
    tr(C,tr(A,L,M,Ha2),tr(B,N,R,Hb2),Hc2)
    ):-
        height(R,Hr),
        Hc>Hr,
        height(L,Hl),
        height(M,Hm),
        height(N,Hn),
        Ha2 is max(Hl,Hm)+1,
        Hb2 is max(Hn,Hr)+1,
        Hc2 is max(Ha2,Hb2)+1.

rot_left_small(
    tr(A,tr(B,L,C,_),R,_),
    tr(B,L,tr(A,C,R,Ha2),Hb2)
    ):-
        height(C,Hc),
        height(L,Hl),
        Hc<Hl,
        height(R,Hr),
        Ha2 is max(Hc,Hr)+1,
        Hb2 is max(Hl,Ha2)+1.

rot_left_big(
    tr(A,tr(B,L,tr(C,M,N,Hc),_),R,_),
    tr(C,tr(B,L,M,Hb2),tr(A,N,R,Ha2),Hc2)
    ):-
        height(L,Hl),
        Hc>Hl,
        height(M,Hm),
        height(N,Hn),
        height(R,Hr),
        Ha2 is max(Hn,Hr)+1,
        Hb2 is max(Hl,Hm)+1,
        Hc2 is max(Ha2,Hb2)+1.

% балансировка
balance(nil,nil,0).
balance(tr(X,L,R,_),tr(X2,L2,R2,H2),H2):-
    balance(L,LL,Hl),
    balance(R,RR,Hr),
    HH is max(Hl,Hr)+1, (
        abs(Hl-Hr)<2,
            X=X2, L2=LL, R2=RR, H2=HH;
        Hr-Hl =:= 2, (
            rot_right_small(tr(X,LL,RR,HH),tr(X2,L2,R2,H2));
            rot_right_big(tr(X,LL,RR,HH),tr(X2,L2,R2,H2))
        );
        Hl-Hr =:= 2, (
            rot_left_small(tr(X,LL,RR,HH),tr(X2,L2,R2,H2));
            rot_left_big(tr(X,LL,RR,HH),tr(X2,L2,R2,H2))
        )
    ).

% вставка в АВЛ-дерево
avl_insert(X,Tree,TreeNew):-
    ins(X,Tree,T),
    balance(T,TreeNew,_).


list2avl([],T,T).
list2avl([X|Xs],T,T2):-
    avl_insert(X,T,TT),
    list2avl(Xs,TT,T2).
list2avl(Lst,Tr):-list2avl(Lst,nil,Tr).

Проверка:

Цитата

?- list2avl([2,1,6,4,5,3],T).

T = tr(4, tr(2, tr(1, nil, nil, 1), tr(3, nil, nil, 1), 2), tr(5, nil, tr(6, nil, nil, 1), 2), 3)

Yes
?- list2avl([3,1,5,4,2,6],T).

T = tr(3, tr(1, nil, tr(2, nil, nil, 1), 2), tr(5, tr(4, nil, nil, 1), tr(6, nil, nil, 1), 2), 3)

Yes
?- list2avl([1,2,3,4,5,6],T).

T = tr(4, tr(2, tr(1, nil, nil, 1), tr(3, nil, nil, 1), 2), tr(5, nil, tr(6, nil, nil, 1), 2), 3)

Yes
?- list2avl([6,5,4,3,2,1],T).

T = tr(3, tr(2, tr(1, nil, nil, 1), nil, 2), tr(5, tr(4, nil, nil, 1), tr(6, nil, nil, 1), 2), 3)

Yes
?-

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

Цитата(blur @ 30.4.2007, 01:44

)

Так что не мог бы ты мне написать нужный предикат - лабу скоро нужно сдавать smile

С тебя пиво smile

Много

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

blur

Дата 1.5.2007, 00:14 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 126
Регистрация: 9.11.2004

Репутация: нет
Всего: 1

Цитата(Artemios @ 1.5.2007, 00:07

)

С тебя пиво smile Много smile

Большое тебе человеческое спасибо smile

А вот пиво только таким образом smile

Artemios

Дата 1.5.2007, 01:36 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 6
Всего: 50

Цитата(blur @ 1.5.2007, 01:14)

А вот пиво только таким образом smile

И на том спасибо smile

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

Artemios

Дата 1.5.2007, 01:58 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 6
Всего: 50

Кстати, вот более хорошее решение:
AVL-дерево (из кн. И. Братко "Программирование на языке Пролог для искусственного интеллекта")

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Prolog \| Следующая тема »