Неизвестно - Prolog

Прологовская программа для внесения нового элемента на произвольный уровень дерева (раздел 9.3) была впервые показана автору М. Ван Эмденом (при личном общении).

Aho А. V., Hopcroft J. Е. and Ullman J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. [Имеется перевод: Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. - М-: Мир, 1979.]

Aho А. V., Hopcroft J. Е. and Ullman J. D. (1983). Data Structures and Algorithms. Addison-Wesley.

Baase S. (1978). Computer Algorithms. Addison-Wesley.

Gonnet G. H. (1984). Handbook of Algorithms and Data Structures. Addison-Wesley.

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

Глава 10

УСОВЕРШЕНСТВОВАННЫЕ МЕТОДЫ

ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ ДЕРЕВЬЯМИ

В данной главе мы рассмотрим усовершенствованные методы представления множеств при помощи деревьев. Основная идея состоит в том, чтобы поддерживать сбалансированности или приближенную сбалансированность дерева, с тем чтобы избежать вырождения его в список. Механизмы балансировки деревьев гарантируют, даже в худшем случае, относительно быстрый доступ к элементам данных, хранящихся в дереве, при логарифмическом порядке времени доступа. В этой главе изложено два таких механизма: двоично-троичные (кратко, 2-3) деревья и AVL-деревья. (Для изучения остальных глав понимание данной главы не обязательно.)

10. 1. Двоично - троичные справочники

Двоичное дерево называют хорошо сбалансированным, если оба его поддерева имеют примерно одинаковую глубину (или размер) и сами сбалансированы. Глубина сбалансированного дерева приближенно равна log n , где n - число вершин дерева. Время, необходимое для вычислений, производимых отношениями внутри, добавитьи удалитьнад двоичными справочниками, пропорционально глубине дерева. Таким образом, в случае двоичных справочников это время имеет порядок log n . Логарифмический рост сложности алгоритма, проверяющего принадлежность элемента множеству, - это определенное достижение по сравнению со списковым представлением, поскольку в последнем случае мы имеем линейный рост сложности

Рис. 10. 1. Полностью разбалансированный двоичный справочник.

Производительность его та же, что и у списка.

с ростом размера множества. Однако плохая сбалансированность дерева ведет к деградации производительности алгоритмов, работающие со справочником. В крайнем случае, двоичный справочник вырождается в список, как показано на рис.10. l. Форма справочника зависит от той последовательности, а которой в всего записываются элементы данных. В лучшей случае мы получаем хорошую балансировку и производительность порядка log n , а в худшем - производительность будет порядка n . Анализ показывает, что в среднем сложность алгоритмов внутри, добавитьи удалитьсохраняет порядок log n в допущении, что все возможные входные последовательности равновероятны. Таким образом, средняя производительность, к счастью, оказывается ближе к лучшему случаю, чек к худшему. Существует, однако, несколько довольно простых механизмов, которые поддерживают хорошую сбалансированность дерева, вне зависимости от входной последовательности, формирующей дерево. Эти механизмы гарантируют производительность алгоритмов внутри, добавитьи удалитьпорядка log n даже в худшем случае . Один из этих механизмов - двоично-троичные деревья (кратко, 2-3 деревья), а другой - AVL-деревья.

2-3 дерево определяется следующим образом: оно или пусто, или состоит из единственной вершины, или удовлетворяет следующим условиям:

каждая внутренняя вершина имеет две или три дочерних вершины, и

все листья дерева находятся на одном и том же уровне.

Двоично-троичным (2-3) справочником называется 2-3 дерево, все элементы данных которого хранятся в листьях и упорядочены слева направо. На рис. 10.2 показан пример. Внутренние вершины содержат метки, равные минимальным элементам тех или иных своих поддеревьев, в соответствии со следующими правилами:

если внутренняя вершина имеет два поддерева, то она содержит минимальный элемент второго из них;

если внутренняя вершина имеет три поддерева, то она содержит минимальные элементы второго и третьего поддеревьев.