Балансировка

Если после выполнения операции добавления или удаления, коэффициент сбалансированности какого-либо узла АВЛ-дерева становиться равен 2, т. е. |h(T_i, R)-h(T_i, L)|=2, то необходимо выполнить операцию балансировки. Она осуществляется путем вращения (поворота) узлов – изменения связей в поддереве. Вращения не меняют свойств бинарного дерева поиска, и выполняются за константное время. Всего различают 4 их типа:

· малое правое вращение;

· большое правое вращение;

· малое левое вращение;

· большое левое вращение.

Оба типа больших вращений являются комбинацией малых вращений (право-левым или лево-правым вращением).

Возможны два случая нарушения сбалансированности. Первый из них исправляется 1 и 3 типом, а второй – 2 и 4. Рассмотрим первый случай. Пусть имеется следующее сбалансированное поддерево:

 

Рисунок 4.7 – Сбалансированное дерево

 

Здесь x и y – узлы, а A, B, C – поддеревья. После добавления к поддереву A узла v, баланс нарушиться, и потребуется балансировка. Она осуществляется правым поворотом (тип 1) узла y:

 

Рисунок 4.8 – Балансировка малым правым поворотом

 

Малое левое вращение выполняется симметрично малому правому. Следующие две функции выполняют малый правый и малый левый повороты.

 

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;

}

 

Второй случай дисбаланса исправляется большим правым или большим левым вращением. Пусть имеется следующее сбалансированное поддерево:

 

Рисунок 4.9 – Сбалансированное дерево

 

Вставка узлов в поддерево A или D, не нарушит сбалансированности, но добавление их в B или C приведет к необходимости произвести балансировку вращением 2-ого типа (рис. 4.10).

 

Рисунок 4.10 – Балансировка большим правым поворотом

 

Большое левое вращение выполняется симметрично большому правому. Функция 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, применяя один из типов вращения.