Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Pascal] Балансировка двоичного дерева поиска

Автор: Relkin 22.12.2006, 18:38

Нужно написать процедуру балансировки двоичного поискового дерева (дерева сравнений). На вход подаётся несбалансированое дерево.
Ключ - фамилия студента. Данные - его оценка.
Я думаю нужно определить количество элементов в дереве.

Код


procedure kolvo(top: pnode; var k: integer);
begin
     if top <> nil then begin
        kolvo(top^.left, k);
        inc(k);
        kolvo(top^.right, k);
     end;
end;

Создать динамический массив (по кол-ву эл-тов).

Код


type
people = record
              Name: string[NameL];
              mark: real;
     end;
     massiv = array[1..200] of people;
     pmassiv = ^massiv;

     getmem(mas, k * sizeof(people));

Записать в него данные по возрастанию, уничтожить это дерево, и создать новое таким образом:
1. Корень дерева - элемент массива с номером (k div 2);
2. Левый сын - ((k div 2) div 2);
3. Правый сын - ((k div 2) div 2) + (k div 2);
4. Далее с каждым сыном поступаем так же, как с корнем.

У меня не получается реализовать этот алгоритм. Если кто знает как сбалансировать дерево (этим алгоритмом или другим) то прошу помочь.
Если же найдены ошибки в коде или алгоритме прошу исправить.

Автор: Kuvaldis 22.12.2006, 21:20

Relkin,
построение идеально сбалансированного дерева - задача ОЧЕНЬ неблагодарная и долгая. Еще в 60-е годы придумали алгоритмы балансировки, строящие так называемые почти сбалансированные деревья. Самые известные из них: красно-черные деревья и АВЛ-деревья.
Более рациональным и эфффективным способом являются красно-черные деревья. О них можно поискать в Сети. Лучшее из того, что я в свое время нашел, это сайт Алголист. Правда, там на С, но зато очень хорошо описана сама идея.
Вот http://algolist.manual.ru/ds/rbtree.php
Кстати, на этом же сайте есть и про АВЛ деревья.... smile

Автор: Relkin 22.12.2006, 21:47

Спасибо, конечно, но это всё- таки не моя задача. Единственное что я нашёл это:http://www.stanford.edu/~blp/avl/libavl.html/Balancing-a-BST.html
http://www.stanford.edu/~blp/avl/libavl.html/Destroying-a-BST-by-Rotation.html
http://www.stanford.edu/~blp/avl/libavl.html/Transforming-a-Vine-into-a-Balanced-BST.html