Int Info;

struct NODE *Left;

struct NODE *Right;

};

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

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

// сортированного массива ключей KeyArrayint 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;

}

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

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

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

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

Рис.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) к виду:

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

(10)

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

9.3.4.1. Поддержание балансировки

Для работы алгоритма поддержания балансировки требуется в каждом узле хранить показатель сбалансированности, принимающий значения –1, 0, 1,

Рис 44. Два случая нарушения балансировки

и равный разности высот правого и левого поддеревьев узла. В принципе возможны только два случая нарушения балансировки, изображенные на рис 44. Другие "плохие" случаи можно получить вращением вокруг вертикальных осей, проходящих через узлы A и B.

Первый случай имеет место, когда вставка увеличивает высоту правого поддерева узла В с h до h+1. Во втором случае либо h=0 и X – новый узел, либо узел X имеет поддеревья с высотами h, h+1. Преобразования, изображенные на р ис.45 восстанавливают балансировку, сохраняя правильность построения дерева.

Рис. 45 Восстановление балансировки

В обоих случаях в дереве нужно изменить лишь несколько связей. Преобразованные деревья имеют высоту h+2, как до включения нового узла. Следовательно, часть дерева, расположенная над узлам А не изменится. Обратите внимание на тот факт, что порядок следования узлов в обратном порядке до и после преобразования не изменился.