Назад | Содержание| Вперёд Глава 10 УСОВЕРШЕНСТВОВА...

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

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

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

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