АВЛ-дерево – структура данных, изобретенная в 1968 году двумя советскими математиками: Евгением Михайловичем Ландисом и Георгием Максимовичем Адельсон-Вельским. Прежде чем дать конструктивное определение АВЛ-дереву, сделаем это для сбалансированного двоичного дерева поиска.
Сбалансированным называется такое двоичное дерево поиска, в котором высота каждого из поддеревьев, имеющих общий корень, отличается не более чем на некоторую константу k, и при этом выполняются условия характерные для двоичного дерева поиска.
АВЛ-дерево – сбалансированное двоичное дерево поиска с k=1. Для его узлов определен коэффициент сбалансированности (balance factor). Balance factor – это разность высот правого и левого поддеревьев, принимающая одно значение из множества {-1, 0, 1}. Ниже изображен пример АВЛ-дерева, каждому узлу которого поставлен в соответствие его реальный коэффициент сбалансированности.
Положим Bi – коэффициент сбалансированности узла Ti (i – номер узла, отсчитываемый сверху вниз от корневого узла по уровням слева направо). Balance factor узла Ti рассчитывается следующим образом. Пусть функция h() с параметрами Tiи L возвращает высоту левого поддерева L узла Ti, а с Ti и R – правого. Тогда Bi=h(Ti, R)-h(Ti, L). Например, B4=-1, так как h(T4, R)-h(T4, L)=0-1=-1.
Сбалансированное дерево эффективно в обработке, что следует из следующих рассуждений. Максимальное количество шагов, которое может потребоваться для обнаружения нужного узла, равно количеству уровней самого бинарного дерева поиска. А так как поддеревья сбалансированного дерева, «растущие» из произвольного корня, практически симметричны, то и его листья расположены на сравнительно невысоком уровне, т. е. высота дерева сводиться к оптимальному минимуму. Поэтому критерий баланса положительно сказывается на общей производительности. Но в процессе обработки АВЛ-дерева, балансировка может нарушиться, тогда потребуется осуществить операцию балансировки. Помимо нее, над АВЛ-деревом определены операции вставки и удаления элемента. Именно выполнение последних может привести к дисбалансу дерева.
Доказано, что высота АВЛ-дерева, имеющего N узлов, примерно равна log2N. Беря в виду это, а также то, то, что время выполнения операций добавления и удаления напрямую зависит от операции поиска, получим временную сложность трех операций для худшего и среднего случая – O(logN).
Прежде чем рассматривать основные операции над АВЛ-деревом, определим структуру для представления его узлов, а также три специальные функции:
struct Node
{
int key;
char height;
Node *right;
Node *left;
Node(int k) { key=k; height=1; left=right=0; }
};
char height(Node *p)
{
if (p) return p->height;
else return 0;
}
int BF(Node *p)
{ return height(p->right)-height(p->left); }
void OverHeight(Node *p)
{
char hleft=height(p->left);
char hright=height(p->right);
p->height=(hleft>hright ? hleft : hright)+1;
}
Структура Node описывает узлы АВЛ-дерева. Ее поля right и left являются указателями на правое и левое поддеревья. Поле key хранит ключ узла, height – высоту поддерева. Функция-конструктор создает новый узел. Функции height и BF вычисляют коэффициент сбалансированности узла, а OverHeight – корректирует значение поля height, затронутое в процессе балансировки.
Балансировка.
Если после выполнения операции добавления или удаления, коэффициент сбалансированности какого-либо узла АВЛ-дерева становиться равен 2, т. е. |h(Ti, R)-h(Ti, L)|=2, то необходимо выполнить операцию балансировки. Она осуществляется путем вращения (поворота) узлов – изменения связей в поддереве. Вращения не меняют свойств бинарного дерева поиска, и выполняются за константное время. Всего различают 4 их типа:
- малое правое вращение;
- большое правое вращение;
- малое левое вращение;
- большое левое вращение.
Оба типа больших вращений являются комбинацией малых вращений (право-левым или лево-правым вращением).
Возможны два случая нарушения сбалансированности. Первый из них исправляется 1 и 3 типом, а второй – 2 и 4. Рассмотрим первый случай. Пусть имеется следующее сбалансированное поддерево:
Здесь x и y – узлы, а A, B, C – поддеревья. После добавления к поддереву A узла v, баланс нарушиться, и потребуется балансировка. Она осуществляется правым поворотом (тип 1) узла y:
Малое левое вращение выполняется симметрично малому правому. Следующие две функции выполняют малый правый и малый левый повороты.
Node* RightRotation(Node *x)
{
Node *y=x->left;
x->left=y->right;
y->right=x;
OverHeight(x);
OverHeight(y);
return y;
}
Node *LeftRotation(Node *y)
{
Node *x=y->right;
y->right=x->left;
x->left=y;
OverHeight(y);
OverHeight(x);
return x;
}
Второй случай дисбаланса исправляется большим правым или большим левым вращением. Пусть имеется следующее сбалансированное поддерево:
Вставка узлов в поддерево A или D, не нарушит сбалансированности, но добавление их в B или C приведет к необходимости произвести балансировку вращением 2-ого типа:
Большое левое вращение выполняется симметрично большому правому. Функция Balance выполняет балансировку узла путем вращения его поддеревьев:
Node *Balance(Node *x)
{
OverHeight(x);
if (BF(x)==2)
{
if (BF(x->right)<0) x->right=RightRotation(x->right);
return LeftRotation(x);
}
if (BF(x)==-2)
{
if (BF(x->left)>0) x->left=LeftRotation(x->left);
return RightRotation(x);
}
return x;
}
Данная функция проверяет условия, и в зависимости от результата балансирует узел x, применяя один из типов вращения.
Добавление узлов
Операция вставки нового узла в АВЛ-дерево выполняется рекурсивно. По ключу данного узла, производиться поиск места вставки: спускаясь вниз по дереву, алгоритм сравнивает ключ добавляемого узла со встречающимися ключами, далее происходит вставка нового элемента; по возвращению из рекурсии, выполняется проверка всех показателей сбалансированности узлов и, в случае необходимости, выполняется балансировка. Для осуществления балансировки следует знать, с каким из рассмотренных выше случаев дисбаланса имеем дело. Допустим, мы добавили узел x в левое поддерево, для которого выполнялось h(Ti, R) < h(Ti, L), т. е. высота левого поддерева изначально превышала высоту правого. Если левое поддерево этого узла выше правого, то потребуется большое вращение, иначе – малое.
Функция добавления узла:
Node *Insert(Node *x, int k)
{
if (!x) return new Node(k);
if (k<x->key) x->left=Insert(x->left, k);
else x->right=Insert(x->right, k);
return Balance(x);
}
Удаление узлов.
Также как и вставку узла, его удаление удобно задать рекурсивно. Пусть x – удаляемый узел, тогда если x – лист (терминальный узел), то алгоритм удаления сводиться к простому исключению узла x, и подъему к корню с переопределением balance factor’ов узлов. Если же x не является листом, то он либо имеет правое поддерево, либо не имеет его. Во втором случае, из свойства АВЛ-дерева, следует, что левое поддерево имеет высоту 1, и здесь алгоритм удаления сводиться к тем же действиям, что и при терминальном узле. Остается ситуация когда у x есть правое поддерево. В таком случае нужно в правом поддереве отыскать следующий по значению за x узел y, заменить x на y, и рекурсивно вернуться к корню, переопределяя коэффициенты сбалансированности узлов. Из свойства двоичного дерева поиска следует, что узел y имеет наименьшее значение среди всех узлов правого поддерева узла x.
Для программной реализации операции удаления узла опишем функцию Delete:
Node *Delete(Node *x, int k)
{
if (!x) return 0;
if (k<x->key) x->left=Delete(x->left, k);
else if (k>x->key) x->right=Delete(x->right, k);
else
{
Node *y=x->left;
Node *z=x->right;
delete x;
if (!z) return y;
Node* min=SearchMin(z);
min->right=DeleteMin(z);
min->left=y;
return Balance(min);
}
return Balance(x);
}
Из нее вызываются вспомогательные функции: SearchMin и DeleteMin. Первая ищет минимальный элемент в правом поддереве, вторая удаляет его. Опишем эти вспомогательные функции:
Node *SearchMin(Node *x)
{
if (x->left) return SearchMin(x->left);
else return x;
}
Node *DeleteMin(Node *x)
{
if (x->left==0) return x->right;
x->left=DeleteMin(x->left);
return Balance(x);
}
Операция удаления реализуется определенно сложнее, чем операция добавления. Да и последствия ее выполнения могут потребовать поворота в каждом узле. Но какова вероятность возникновения ситуации, при которой появится потребность в поворотах? Этим вопросом задается Никлаус Вирт в своей книге «Алгоритмы и структуры», и отвечает на него: «Удивительный результат эмпирических проверок показал, что в то время как один поворот вызывается приблизительно каждыми двумя включениями, тем не менее, при удалении мы имеем дело с одним поворотом на целых пять удалений».