Основы программирования

         

Реализации множества на базе деревьев


Реализация множества с помощью бинарного поиска во всех отношениях лучше наивной реализации. Вместе с тем, она все же имеет недостатки: 1) при добавлении и удалении элементов в середине массива приходится переписывать элементы в конце массива на новое место, чтобы освободить место для добавляемого элемента либо закрыть образовавшуюся лакуну при удалении элемента; 2) поиск выполняется гарантированно быстро, но все-таки не мгновенно. От первого из этих недостатков можно избавиться, применяя вместо непрерывной реализации на базе массива ссылочную реализацию, при которой элементы множества содержатся в вершинах бинарного дерева. Элементы в вершинах упорядочены таким образом, что, если зафиксировать некоторую вершину V и рассмотреть два поддерева, соответствующих левому и правому сыновьям вершины, то все элементы в вершинах левого поддерева должны быть меньше, чем элемент в вершине V, а все элементы в вершинах правого поддерева должны быть больше него.


Для такого дерева можно также применять алгоритм бинарного поиска. Максимальное число сравнений при поиске в таком дереве равняется его высоте ( т.е. максимальной длине пути от корня к терминальной вершине).

Чтобы поиск выполнялся быстро, дерево должно быть сбалансированным, т.е. все его ветви должны иметь почти одинаковую длину.

Точное определение сбалансированности следующее: будем считать, что у каждой вершины, включая терминальные, ровно два сына, при необходимости добавляя внешние, или нулевые, вершины. Например, у терминальной вершины оба сына нулевые. (Это в точности сответствует представлению дерева в языке Си, где каждая вершина хранит два указателя на сыновей; если сына нет, то соответствующий указатель нулевой.) Обычные вершины дерева будем называть собственными. Рассмотрим путь от корня дерева к внешней (нулевой) вершине. Длиной пути считается количество собственных вершин в нем. Дерево называется сбалансированным, если длины всех возможных путей от корня дерева к внешним вершинам различаются не более чем на единицу.
Иногда в литературе такие деревья называют почти сбалансированными, понимая под сбалансированностью строгое равенство длин всех путей от корня к внешним узлам; мы, однако, будем придерживаться нестрогого определения. Пример сбалансированного дерева представлен на рисунке.



Высота сбалансированного дерева h оценивается логарифмически в зависимости от числа вершин n:

h <= log2n + 1

Поскольку максимальное число сравнений при поиске элемента в упорядоченном бинарном дереве равняется высоте дерева, поиск в сбалансированном дереве осуществляется исключительно быстро, за время, логарифмически зависящее от числа элементов множества. (Можно доказать, что это является теоретической оценкой снизу: никакой алгоритм не может в общем случае находить элемент быстрее, чем за log2n операций.)

Для эффективной реализации множества на базе дерева процедуры добавления и удаления элементов должны сохранять свойство сбалансированности (или почти сбалансированности). Рассмотрим коротко две наиболее популярные схемы реализации.


Содержание раздела