Фундаментальные структуры данных. АВЛ-деревья. Метод «преобразуй и властвуй», страница 2

АВЛ-деревья

Операция удаления информации из AVL-дерева значительно сложнее, чем вставка, но, к счастью, она принадлежит к тому же классу эффективности, что и вставка, - т.е. к логарифмическому. Недостатками AVL-деревьев являются частые повороты, необходимость поддержания сбалансированности узлов дерева и сложность, в особенности операции удаления. Эти недостатки не позволили стать AVL-деревьям стандартной структурой данных для реализации словарей. В то же время идея балансировки оказалась очень плодотворной и привела к открытию других интересных вариаций бинарных деревьев поиска.

Деревья Фибоначчи

• Деревом Фибоначчи называется такое АВЛ-дерево, для которого высоты поддеревьев для каждого узла отличаются ровно на 1 (например, высоты всех правых поддеревьев на 1 меньше высот всех левых поддеревьев. При заданной высоте такое дерево единственно (с точностью до замены правых поддеревьев на левые). Это дерево худшее АВЛ-дерево. Числа узлов деревьев Фибоначчи за заданных высот называются числами Леонарда: L0 = 0, L1 = 1, Lh = 1 + Lh-1 + Lh-2.
• Пример. Для h = 7 - L7 = 33, а максимальное число узлов совершенного дерева равно 127. Число узлов любого АВЛ-дерева высоты 7 лежит между этими двумя числами.

2-3-деревья

Данный подход представляет собой вариант изменения представления: допускается наличие более чем одного элемента в узле дерева поиска. Частными случаями таких деревьев являются 2-3-деревья, 2-3-4-деревья и более общий и важный случай В-деревья. Они различаются количеством элементов, которые допустимы в одном узле дерева поиска, но все они являются идеально сбалансированными. Простейшей реализацией этой идеи являются 2-3-деревья, разработанные в 1970 г. американским кибернетиком Дж. Хопкровтом (John Hopcroft).

2-3-деревья

2-3-дерево представляет собой дерево, которое может иметь узлы двух видов – 2-узлы и 3-узлы. 2-узел содержит единственный ключ К и имеет два потомка: левый дочерний узел служит корнем поддерева, все ключи в котором меньше К, а правый – корнем поддерева, все ключи в котором больше К. Другими словами, 2-узел точно такой же, как и узел в классическом бинарном дереве поиска. 3-узел содержит два упорядоченных ключа К1 и К2 (К1<К2) и имеет три дочерних узла. Левый дочерний узел служит корнем поддерева, ключи в котором меньше К1, средний – корнем поддерева, ключи в котором больше К1 и меньше К2, а правый – корнем поддерева, все ключи в котором больше К2.

2-3-деревья

Последнее требование к 2-3-дереву заключается в том, что все его листья должны находиться на одном уровне, т.е. 2-3-дерево всегда сбалансировано по высоте: длина пути от корня дерева к листу должна быть одинакова для всех листьев. Это свойство достигается ценой разрешения иметь узлы с тремя дочерними узлами. Поиск заданного ключа К в 2-3-дереве достаточно прост. Он начинается с корня. Если корень представляет собой 2-узел, то мы действуем так же, как и в случае бинарного дерева поиска, - либо прекращаем поиск, если значение К равно значению ключа поиска, либо продолжаем поиск

2-3-деревья в левом или правом поддереве, в зависимости от того, меньше ли значение К, чем ключ корня, или больше. Если же корень представляет собой 3-узел, то после не более чем двух сравнений мы знаем, следует ли прекратить поиск (если К равно одному из ключей 3-узла) или в каком из трех поддеревьев он должен быть продолжен. Вставка нового ключа в 2-3-дерево выполняется следующим образом. Новый ключ К всегда вставляется в лист, за исключением случая пустого дерева. Соответствующий лист мы находим, выполняя поиск ключа К. Если искомый лист – 2-узел, мы вставляем К либо как первый, либо как второй ключ – в зависимости