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

Длина поиска в двоичном дереве поиска определяется высотой самого дерева. Она для заданного числа элементов n зависит от порядка поступления элементов при построении дерева и может колебаться от Iog₂n в случае идеальной сбалансированности дерева до (n-1) в случае вырождения дерева в линейный список. Таким образом, затраты на поиск и включение элемента будут порядка от O(log₂n) до О(n).

Доказано, что при случайном порядке включения элементов в дерево средние затраты на поиск элемента будут 1.386*O(log₂n). Увеличение затрат на 39% вполне оправдано более простыми средствами поддержания обычного дерева поиска по сравнению с идеально сбалансированным деревом поиска. Однако при работе с большими деревьями свойство случайности распределения поступающих данных редко соблюдается — это скорее исключение, чем правило. Обычно входные последовательности являются частично упорядоченными (по фамилиям, номенклатурным номерам, квалификационным признакам и т.п.). Для таких ситуаций наиболее подходящими являются так называемые сбалансированные деревья поиска. Рассмотрим два вида таких деревьев: АВЛ- деревья, предложенные в 1962 г. Адельсоном-Вельским и Ландисом, и рандомизированные деревья поиска.
   8.1. Сбалансированные АВЛ-деревья поиска
 

Требования к сбалансированности в АВЛ - деревьях менее жесткие, чем в идеально сбалансированных деревьях. АВЛ - деревом называется такое дерево, у которого высота поддеревьев для каждой вершины различается не более чем на 1. Максимальная высота АВЛ -дерева с n вершинами не превосходит 1,44*log₂(n+ 1) - 1,33, т. е. затраты на поиск не превосходят l,45*O(log₂n).

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

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

Создание рандомизированных деревьев поиска основа на том, что «случайность» включается в алгоритм вставки элемента в дерево без каких-либо допущений относительно порядка вставки элементов. Идея заключается в том, что при вставке нового узла в дерево, состоящее из N узлов, вероятность появления ново-о узла в корне дерева должна быть 1/(N +1).