АВЛ-дерево
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска:
A < k < B; |H(A) - H(B)| <=1
struct node // структура для представления узлов дерева
{
int key;
unsigned char height;
node* left;
node* right;
node(int k) { key = k; left = right = 0; height = 1; }
};
Поле key хранит ключ узла, поле height — высоту поддерева с корнем в данном узле, поля left и right — указатели на левое и правое поддеревья. Простой конструктор создает новый узел (высоты 1) с заданным ключом k.
unsigned char height(node* p)
{
return p?p->height:0;
}
Традиционно, узлы АВЛ-дерева хранят не высоту, а разницу высот правого и левого поддеревьев (так называемый balance factor), которая может принимать только три значения -1, 0 и 1.
int bfactor(node* p)//-1, 0 и 1
{
return height(p->right)-height(p->left);
}
void fixheight(node* p)//Calculate height
{
unsigned char hl = height(p->left);
unsigned char hr = height(p->right);
p->height = (hl>hr?hl:hr)+1;
}
Балансировка узлов
balance factor оказывается равными 2 или -2.
Код, реализующий правый поворот(Kак обычно, каждая функция, изменяющая дерево, возвращает новый корень полученного дерева):
node* rotateright(node* p) // правый поворот вокруг p
{
node* q = p->left;
p->left = q->right;
q->right = p;
fixheight(p);
fixheight(q);
return q;
}
Левый поворот является симметричной копией правого:
node* rotateleft(node* q) // левый поворот вокруг q
{
node* p = q->right;
q->right = p->left;
p->left = q;
fixheight(q);
fixheight(p);
return p;
}
Заметим, что все функции являются нерекурсивными, т.е. время их работы есть величина О(1)..
Рассмотрим теперь ситуацию дисбаланса, когда высота правого поддерева узла p на 2 больше высоты левого поддерева (обратный случай является симметричным и реализуется аналогично). Пусть q — правый дочерний узел узла p, а s — левый дочерний узел узла q.
Анализ возможных случаев в рамках данной ситуации показывает, что для исправления расбалансировки в узле p достаточно выполнить либо простой поворот влево вокруг p, либо так называемый большой поворот влево вокруг того же p. Простой поворот выполняется при условии, что высота левого поддерева узла q больше высоты его правого поддерева: h(s)≤h(D).
Большой поворот применяется при условии h(s)>h(D) и сводится в данном случае к двум простым — сначала правый поворот вокруг q и затем левый вокруг p.
Код, выполняющий балансировку, сводится к проверке условий и выполнению поворотов:
node* balance(node* p) // балансировка узла p
{
fixheight(p);
if( bfactor(p)==2 )
{
if( bfactor(p->right) < 0 )
p->right = rotateright(p->right);
return rotateleft(p);
}
if( bfactor(p)==-2 )
{
if( bfactor(p->left) > 0 )
p->left = rotateleft(p->left);
return rotateright(p);
}
return p; // балансировка не нужна
}
Описанные функции поворотов и балансировки также не содержат ни циклов, ни рекурсии, а значит выполняются за постоянное время, не зависящее от размера АВЛ-дерева.
.
Вставка ключей
Строго доказывается, что возникающий при такой вставке дисбаланс в любом узле по пути движения не превышает двух, а значит применение вышеописанной функции балансировки является корректным.
node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
{
if( !p ) return new node(k);
if( k<p->key )
p->left = insert(p->left,k);
else
p->right = insert(p->right,k);
return balance(p);
}
Удаление ключей
Идея следующая: находим узел p с заданным ключом k (если не находим, то делать ничего не надо), в правом поддереве находим узел min с наименьшим ключом и заменяем удаляемый узел p на найденный узел min.
При реализации возникает несколько нюансов. Прежде всего, если у найденный узел p не имеет правого поддерева, то по свойству АВЛ-дерева слева у этого узла может быть только один единственный дочерний узел (дерево высоты 1), либо узел p вообще лист. В обоих этих случаях надо просто удалить узел p и вернуть в качестве результата указатель на левый дочерний узел узла p.
Пусть теперь правое поддерево у p есть. Находим минимальный ключ в этом поддереве.
node* findmin(node* p) // поиск узла с минимальным ключом в дереве p
{
return p->left?findmin(p->left):p;
}
Еще одна служебная функция у нас будет заниматься удалением минимального элемента из заданного дерева. Опять же, по свойству АВЛ-дерева у минимального элемента справа либо подвешен единственный узел, либо там пусто. В обоих случаях надо просто вернуть указатель на правый узел и по пути назад (при возвращении из рекурсии) выполнить балансировку. Сам минимальный узел не удаляется, т.к. он нам еще пригодится.
node* removemin(node* p) // удаление узла с минимальным ключом из дерева p
{
if( p->left==0 )
return p->right;
p->left = removemin(p->left);
return balance(p);
}
.
Теперь все готово для реализации удаления ключа из АВЛ-дерева. Сначала находим нужный узел, выполняя те же действия, что и при вставке ключа:
node* remove(node* p, int k) // удаление ключа k из дерева p
{
if( !p ) return 0;
if( k < p->key )
p->left = remove(p->left,k);
else if( k > p->key )
p->right = remove(p->right,k);
Как только ключ k найден, переходим к плану Б: запоминаем корни q и r левого и правого поддеревьев узла p; удаляем узел p; если правое поддерево пустое, то возвращаем указатель на левое поддерево; если правое поддерево не пустое, то находим там минимальный элемент min, потом его извлекаем оттуда, слева к min подвешиваем q, справа — то, что получилось из r, возвращаем min после его балансировки.
else // k == p->key
{
node* q = p->left;
node* r = p->right;
delete p;
if( !r ) return q;
node* min = findmin(r);
min->right = removemin(r);
min->left = q;
return balance(min);
}
При выходе из рекурсии не забываем выполнить балансировку:
return balance(p);
}
Вот собственно и все! Поиск минимального узла и его извлечение, в принципе, можно реализовать в одной функции, при этом придется решать (не очень сложную) проблему с возвращением из функции пары указателей. Зато можно сэкономить на одном проходе по правому поддереву.
http://habrahabr.ru/post/150732/
Экспериментально выяснено, что одна балансировка приходится на каждые два включения и на каждые пять исключений.
В АВЛ-дереве высоты
не меньше узлов, где — число Фибоначчи. Поскольку ,где — золотое сечение, то имеем оценку на высоту АВЛ-дерева
, где — число узлов. Следует помнить, что — мажоранта, и её можно использовать только для оценки (Например, если в дереве только два узла, значит в дереве два уровня, хотя
). Для точной оценки глубины дерева следует использовать пользовательскую подпрограмму, однако, можно использовать формулы , или
.