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

Оптимальные деревья

Оптимальным назовем дерево, высота которого минимальна. Это означает, что у него заполнены все уровни, кроме, быть может, последнего. Алгоритм построения оптимального дерева заключается в следующем:

- отсортируем ключи и средний из них поместим в корень

- левым сыном сделаем ключ, являющийся средним среди ключей слева от корня

- правым сыном сделаем ключ, являющийся средним среди ключей справа от корня

- точно также поступим при выборе сыновей каждого из узлов.

Ниже представлен текст функции, формирующей оптимальное дерево.

const int LEFT=0;

const int RIGHT=1;

struct NODE {

int Info;

struct NODE *Left;

struct NODE *Right;

};

NODE *CreateOptimalTree(int KeyArray[], int m, int n){

/*создать оптимальное дерево из ключей отрезка от m до n

сортированного массива ключей KeyArray */

int k;

NODE *Root;

if(n<m) return NULL;

Root=new NODE;

k=(n+m)/2;

Root->Info=KeyArray[k];

if(n==m){

Root->Left=NULL;

Root->Right=NULL;

} else {

Root->Left=CreateOptimalTree(KeyArray,m,k-1);

Root->Right=CreateOptimalTree(KeyArray,k+1,n);

}

return Root;

}

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

Сбалансированные деревья представляют собой компромисс между оптимальными и случайными деревьями. Авторы идеи сбаланси­ро­ван­ного дерева - Адельсон-Вельский и Ландис (1962 г.), поэтому такие деревья называют также AVL-деревьями. AVL-деревья используют дополнительно 2 бита на узел и позволяют за время ~log₂N, выполнять операции вставки, поиска и удаления.

Определим высоту дерева как максимальную длину пути от корня до листа. Будем называть дерево сбалансированным, если в каждом узле высота

Рис.43 Пример сбалансированного дерева

изображен пример сбалансированного дерева. Оценим максимальную высоту сбалансированного дерева. Обозначим минимальное число узлов в AVL-дереве высоты h через N(h). В таком дереве с минимальным числом узлов одна из ветвей, исходящих из корня, должна содержать N(h-1) узлов, а другая - N(h-2) узлов. Таким образом,

(6)

Очевидно, что N(0)=1, N(1)=2. Далее по формуле (6) находим , что N(2)=4. Для h=3 и h=4 можно непосредственно проверить, а затем по индукции доказать, что при h³3 справедливо неравенство

(7)

где

-положительный корень уравнения , которое является характеристическим для разностного уравнения (6). Действительно, допустим, что неравенство (7) выполняется для всех k<N. Тогда, подставив в правую часть равенства (6) нижние границы N(h-1), N(h-2) в соответствии с неравенством (7), получим:

(8)

Подставим в левую часть неравенства (7) нижнюю грань для N(h) из неравенства (8). В результате будет получено более сильное неравенство:

(9)

Очевидно, что если (9) справедливо, то тем более справедливо (7). Преобразуем неравенство (9) к виду:

Трехчлен в скобках тождественно равен нулю, так как a - его корень. Остается –1<0. Таким образом, неравенство (7) доказано. Следовательно, если сбалансированное дерево содержит ветвь длины h>3, то число его вершин n удовлетворяет неравенству , откуда

(10)

Величина h+1 – это число сравнений ключей при поиске записи, расположенной в конце пути длиной h, исходящем из корня. Окончательный вывод: число сравнений ключей при поиске в сбалан­сированном дереве из n узлов не превышает .