Сбалансированные деревья поиска

Время поиска в БД поиска определяется высотой самого дерева. Для заданного числа элементов n высота дерева зависит от порядка поступления элементов при построении дерева и может колебаться от в случае идеальной сбалансированности дерева до n -1 в случае вырождения дерева в линейный список. Следовательно, затраты на поиск и включение будут порядка от до n.

Доказано, что при случайном порядке включения элементов в дерево средние затраты на поиск элемента будут 1.386* . Увеличение затрат на 39% объясняется простыми средствами поддержания обычного дерева поиска по сравнению с идеально сбалансированным деревом поиска. Однако при работе с большими деревьями свойство случайности распределения поступающих данных редко соблюдается – это, скорее, исключение, чем правило. Обычно выходные последовательности являются частично упорядоченными. Для таких последовательностей наиболее подходящими оказываются сбалансированные деревья поиска. Рассмотрим один из видов таких деревьев: АВЛ – деревья, предложенные в 1962 г. Адельсоном-Вельским и Ландисом.

Требования к сбалансированности в АВЛ-деревьях менее жесткие, чем в идеально сбалансированных деревьях.

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

Максимальная высота АВЛ-дерева с n вершинами не превосходит 1.44* т.е. затраты на поиск не превосходят 1.45* .

Отличие АВЛ-дерева от обычного дерева поиска заключается в том, что при включении и удалении элементов необходимо поддерживать сбалансированность дерева в целом. Для этого в каждый узел дерева добавляется одно вспомогательное поле, содержащее информацию о равновесности поддеревьев (показатель сбалансированности узла). Его значениями могут быть: 0 – высоты правого и левого поддеревьев равны; 1 – высота правого поддерева больше; -1 – высота левого поддерева больше.

При попытке добавить или удалить элемент в поддереве с показателем сбалансированности, отличным от 0, дерево может стать несбалансированным, и потребуется операция балансировки.

Дата добавления: 2015-07-16