Tree ++++
.pdf
Идеально сбалансированные бинарные деревья
Бинарное дерево называется идеально сбалансированным, если для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1.
51
Высота идеально сбалансированного бинарного дерева
Длина внутреннего пути в идеально сбалансированном дереве, содержащем n вершин, не превосходит величины:
|
|
|
|
2 |
|
|
log |
n |
|
|
h |
|
n 1 |
log |
|
n 2 |
|
2 |
2 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
n 2 |
m |
|
h n m 2
52
Алгоритм построения идеально сбалансированного бинарного дерева
Формулируется с помощью рекурсии. Для достижения минимальной высоты при заданном числе вершин, нужно располагать максимально возможное число вершин на всех уровнях, кроме самого нижнего. Это можно сделать очень просто, если распределять все поступающие в дерево вершины поровну слева и справа от каждой вершины.
Идея алгоритма:
взять одну вершину в качестве корня.
построить левое поддерево с n1 = n / 2 вершинами тем же способом.
построить правое поддерево с n2 = n-n1-1 вершинами тем же
способом.
53
Программа построения идеально
сбалансированного бинарного дерева
TREE *CreateIdealTree (int n, TREE *&p) // p - указатель на корень дерева.
{ TREE *q=p; int x, nL, nR; if(!n) return 0;
nL = n/2; nR = n – nL - 1; input(x);
q = (TREE*) malloc(sizeof(TREE)); q->key = x;
CreateIdealTree (nL, q->left);
CreateIdealTree (nR, q->right); p = q;
return p;
} // CreateIdealTree |
54 |
|
Пример построения дерева
8, 9, 11, 15, 19, 20, 21, 7, 3, 2, 1, 5, 6, 4, 13, 14, 10, 12, 17, 16, 18.
55
АВЛ (AVL) - сбалансированные по высоте деревья
Бинарное дерево поиска называется сбалансированным по высоте, если для каждой его вершины высота её двух поддеревьев различается не более, чем на 1.
Деревья, удовлетворяющие этому условию, часто называют АВЛдеревьями (по первым буквам фамилий их изобретателей Г.М.
Адельсона-Вельского и Е.М. Ландиса).
Показатель сбалансированности вершины бинарного дерева есть
разность высоты его правого и левого поддерева.
Все идеально сбалансированные деревья являются также и АВЛ - деревьями и среди АВЛ-деревьев они являются деревьями с минимальной высотой при заданном числе вершин.
56
АВЛ - деревья
Адельсон-Вельский и Ландис доказали, что АВЛдерево никогда не будет более, чем на 45% выше соответствующего идеально сбалансированного дерева независимо от количества узлов.
Проведённый анализ показывает, что АВЛдеревья имеют достаточно короткие пути из корня в листья, что позволяет использовать их для организации поиска в больших массивах информации.
Чтобы убедиться в этом, нужно показать, что включение и исключение узлов можно проводить, оставляя деревья АВЛсбалансированными.
57
Алгоритмы балансировки. Общие положения
Рассмотрим теперь, что может произойти при включении в сбалансированное дерево новой вершины. Если у нас есть корень r, левое (L) и правое (R) поддеревья, то необходимо различать три возможных случая.
Предположим, что включение в L новой вершины увеличит на 1 его высоту; тогда возможны три случая:
сначала было hL = hR. После включения L и R станут разной высоты, но критерий сбалансированности не будет нарушен;
сначала было hL < hR. После включения L и R станут равной высоты, то есть критерий сбалансированности даже улучшится;
сначала было hL > hR. После включения критерий сбалансированности нарушится и дерево необходимо перестраивать.
58
Пример дерева
Вершины с ключами 9 и 11 можно включить в дерево, не нарушив его сбалансированности: дерево с корнем 10 становится односторонним, а дерево с корнем 8 - лучше сбалансированным. Однако включение значений 1, 3, 5 и 7 требует последующей балансировки.
Алгоритм включения и балансировки существенно зависит от того, каким способом хранится информация о сбалансированности дерева. Удобно хранить в каждой вершине показатель
сбалансированности. |
59 |
struct NODE
Структура вершины АВЛ-дерева будет следующей
struct NODE { int key;
int count; int balance;
//Показатель сбалансированности вершины = разность между
//высотой правого и левого поддерева.
NODE *Left, Right;
};
60