Методы программирования. Громов Ю.Ю - 114 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

114
21. СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ
Рассмотренный в предыдущем параграфе алгоритм поиска со встав-
кой в дерево даёт хорошие результаты при использовании случайных
входных данных, но существует неприятная возможность того, что при
этом будет построено вырожденное дерево (линейный список). Для под-
держания бинарного дерева в так называемом хорошем состоянии его
можно реорганизовывать на некоторых этапах построения.
Красивое решение задачи реорганизации бинарного дерева было от-
крыто в 1962 г. советскими математиками Г.М. Адельсон-Вельским и
Е.М. Ландисом. Их метод требует двух дополнительных битов на каждый
узел дерева и никогда не использует более
)(log NO
операций для поиска
по дереву или вставки нового элемента. Предложенный подход также
даёт общую технологию представления линейных списков длиной N та-
ким образом, что любая из следующих операций может быть выполнена
за время порядка
Nlog
:
а) поиск элемента по заданному ключу;
б) поиск k-го элемента по заданному k;
в) вставка элемента в определённое место;
г) удаление определённого элемента.
При последовательном расположении в памяти элементов линейных
списков операции (а) и (б) выполняются очень эффективно, в то время
как операции (в) и (г) требуют порядка N шагов. При использовании свя-
занных элементов, напротив, эффективно будут выполняться операции
(в) и (г), а операции (а) и (б) потребуют порядка N шагов. Представление
линейных списков в виде дерева позволяет выполнить каждую из четы-
рёх операций за
)(log NO
шагов. При этом можно более или менее эф-
фективно выполнять и другие операции, например сцепление списка из
М элементов со списком из N элементов за
))(log( NMO +
шагов.
Метод, предоставляющий все эти преимущества, будем называть
сбалансированными деревьями (AVL-деревьями – по первым буквам фа-
милий авторов).
Высотой дерева называется его максимальный уровень, т.е. длина
самого длинного пути от корня к внешнему узлу (листу). Бинарное дере-
во называют сбалансированным, если высота левого поддерева любого
узла отличается не более чем на ±1 от высоты правого поддерева. На ри-
сунке 40 изображено сбалансированное дерево высотой 5 с 17 внутрен-
ними узлами. Фактор сбалансированности обозначен внутри каждого
узла знаками «+», «•» и «–» в соответствии с величиной разности между
высотами правого и левого поддеревьев (+1, 0 или –1).

Страницы