отобр( Д3, H1), 8
tab( H), write( --), nl, --
tab( H), write( M3), nl, 8
отобр( Д2, H1), --
tab( H), write( M2), nl, 7
tab( H), write( --), nl, --
отобр( Д1, H1). 7
--
(a) 5
-- 5
--
4
--
4
3
3
--
1
(б)
Рис. 10. 7. (а) Программа для отображения 2-3 справочника.
(b) Справочник (см. рис. 10.2), отпечатанный этой программой.
Назад | Содержание | Вперёд
Назад | Содержание | Вперёд
10. 2. AVL - дерево: приближенно сбалансированное дерево
AVL-дерево - это дерево, обладающее следующими свойствами:
(1) Левое и правое поддеревья отличаются по глубине не более чем на 1.
(2) Оба поддерева являются AVL-деревьями.
Деревья, удовлетворяющие этому определению, могут быть слегка разбалансированными. Однако можно показать, что даже в худшем случае глубина AVL-дерева примерно пропорциональна log
Операции над AVL-деревом работают по существу так же, как и над двоичным справочником. В них только сделаны добавления, связанные с поддержанием приближенной сбалансированности дерева. Если после вставления или удаления дерево перестает быть приближенно сбалансированным, то специальные механизмы возвращают ему требуемую степень сбалансированности. Для того, чтобы эффективно реализовать этот механизм, нам придется
