4.9. СХЕМЫ СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ

При решении ряда важных классов задач, аналогичных задаче мы, по-видимому, вынуждены вернуться к способам, при которых последовательность из операций выполняется за время (в худшем случае). В один такой класс входят задачи, в которых последовательность из операций ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ и УДАЛИТЬ выполняется в случае, когда допускается гораздо больше элем нтов, чем используется на самом деле. В этом случае нельзя выбрать элемент, обращаясь прямо в массив указателей. Надо применять расстановку или дерево двоичного поиска.

Если элементов уже вставлены, то в методе расстановки один выбор осуществляется за постоянное время в среднем и в худшем случае. Дерево двоичного поиска дает среднее время на один выбор, но в худшем случае может тоже дать плохое время выбора, если множество имен изменяется. Если же просто добавлять имена к дереву, не имея никакого механизма для поддержания его сбалансированности, то можно в результате придти к дереву с узлами, глубина которого близка к Поэтому в худшем случае производительность дерева двоичного поиска будет шагов на операцию. Методом, изложенным в этом разделе, можно уменьшить сложность в худшем случае до шагов на операцию.

Другой класс задач, требующих времени, образуют задачи выполнения последовательности из операций, включающих ВСТАВИТЬ, УДАЛИТЬ и MIN, в префиксном режиме. Еще один, третий, класс задач возникает, когда нужно представлять упорядоченные списки и уметь сцеплять и расцеплять их.

В настоящем разделе мы познакомимся с техникой, позволяющей выполнять в префиксном режиме последовательности,

содержащие важные подмножества семи основных операций на множествах, введенных в разд. 4.1. Структурой данных, лежащей в основе метода, является сбалансированное дерево, под которым мы понимаем дерево с высотой, приблизительно равной логарифму числа его узлов.

Вначале сбалансированное дерево строится легко. Трудно не дать ему в процессе выполнения последовательности операций ВСТАВИТЬ и УДАЛИТЬ превратиться в несбалансированное. Например, если периодически не делать перебалансировку, то при выполнении последовательности операций которые удаляют узлы только из левой части дерева, получается дерево, смещенное вправо.

Известно много способов перебалансировки дерева в случае необходимости. Некоторые из них оставляют структуру дерева достаточно гибкой, так что число узлов в дереве высоты может изменяться от до или В них позволяется по меньшей мере удвоить число узлов в поддереве, прежде чем что-то менять выше его корня.

Мы обсудим два метода этого рода, называемые методами 2-3-деревьев и АВЛ-деревьев. Алгоритмы, работающие с 2-3-деревьями, понять легче, и сейчас мы обсудим их. Алгоритмы с АВЛ-деревьями похожи на них, и потому вынесены в упражнения.

Определение. 2-3-деревом называется дерево, в котором каждый узел, не являющийся листом, имеет двух или трех сыновей, а длины всех путей из корня в листья одинаковы. Заметим, что дерево, состоящее из единственного узла, является 2-3-деревом. На рис. 4.26 приведены два 2-3-дерева с шестью листьями.

В следующей лемме показана связь числа узлов и числа листьев в 2-3-дереве с его высотой.

Лемма 4.6. Пусть будет 2-3-деревом высоты Число узлов дерева заключено между а число листьев — между

Доказательство. Элементарная индукция по

Рис. 4.26. 2-3-деревья,

Линейно упорядоченное множество можно представить 2-3-деревом, приписав его элементы листьям дерева. Обозначим элемент, приписанный листу I, через Существуют два основных метода приписывания элементов листьям; какой из них применить, зависит от рассматриваемой задачи.

Если допускается элементов гораздо больше, чем на самом деле используется, и дереву предстоит быть словарем, то, вероятно, лучше приписывать элементы в порядке возрастания слева направо. В каждом узле не являющемся листом, нам потребуется еще два данных: и — это наибольший элемент множества в поддереве, корнем которого служит самый левый сын узла это наибольший элемент множества в поддереве, корнем которого служит второй сын узла (см. рис. 4.26). Значения приписанные узлам, позволяют искать элемент, начиная с корня, способом, аналогичным двоичному поиску. Время обнаружения произвольного элемента пропорционально высоте дерева. Поэтому операцию ПРИНАДЛЕЖАТЬ можно выполнить на множестве из элементов за время если представить его в виде 2-3-дерева такого рода.

Во втором методе приписывания элементов листьям на порядок, в котором приписываются эти элементы, не налагается никаких ограничений. Метод особенно полезен для реализации операции ОБЪЕДИНИТЬ. Однако для выполнения операций типа УДАЛИТЬ нужен механизм для определения положения листа, представляющего данный элемент. Если элементами множества являются целые числа из фиксированной области, скажем от 1 до то лист, представляющий элемент можно находить с помощью ячейки некоторого массива. Если же элементы рассматриваемых множеств принадлежат некоторому большому универсальному множеству, то лист, представляющий элемент I, можно находить с помощью вспомогательного словаря.

Рассмотрим следующие наборы операций.

Структуру данных, обеспечивающую выполнение операций из множества 1, будем называть словарем, из множества 2 — очередью с приоритетами, из множества 3 — сливаемым деревом, из множества 4 — сцепляемой очередью.

Покажем, что 2-3-деревья могут служить для реализации словарей, очередей с приоритетами, сцепляемых очередей и сливаемых деревьев, применение которых обеспечивает выполнение операций за время

Развитая здесь техника достаточно мощна, чтобы выполнить последовательности, составленные из любого совместного подмножества семи операций, перечисленных в начале главы. Единственная несовместность состоит в том, что операция ОБЪЕДИНИТЬ приводит к неупорядоченному множеству, а РАСЦЕПИТЬ и СЦЕПИТЬ предполагают наличие порядка.