Вращение вправо‑влево

Вращение вправо‑влево (right‑left rotation) аналогично вращению влево‑вправо (). Оно используется для балансировки дерева после вставки узла в поддерево RL на рис. 7.4. На рис. 7.10 показано АВЛ‑дерево до и после вращения вправо‑влево.

Резюме

На рис. 7.11 показаны все возможные вращения АВЛ‑дерева. Все они сохраняют порядок симметричного обхода дерева, и высота дерева при этом всегда остается неизменной. После вставки нового элемента и выполнения соответствующего вращения, дерево снова оказывается сбалансированным.

Вставка узлов на языке Visual Basic

Перед тем, как перейти к обсуждению удаления узлов из АВЛ‑деревьев, в этом разделе обсуждаются некоторые детали реализации вставки узла в АВЛ‑дерево на языке Visual Basic.

Кроме обычных полей LeftChild и RightChild, класс AVLNode содержит также поле Balance, которое указывает, которое из поддеревьев узла выше. Его значение равно -1, если левое поддерево выше, 1 — если выше правое, и 0 — если оба поддерева имеют одинаковую высоту.

======161

@Рис. 7.10. До и после вращения вправо‑влево

Public LeftChild As AVLNode

Public RightChild As AVLNode

Public Balance As Integer

Чтобы сделать код более простым для чтения, можно использовать постоянные LEFT_HEAVY, RIGHT_HEAVY, и BALANCED для представления этих значений.

Global Const LEFT_HEAVY = -1

Global Const BALANCED = 0

Global Const RIGHT_HEAVY = 1

Процедура InsertItem, представленная ниже, рекурсивно спускается вниз по дереву в поиске нового местоположения элемента. Когда она доходит до нижнего уровня дерева, она создает новый узел и вставляет его в дерево.

Затем процедура InsertItem использует восходящую рекурсию для балансировки дерева. При выходе из рекурсивных вызовов процедуры, она движется назад по дереву. При каждом возврате из процедуры, она устанавливает параметр has_grown, чтобы определить, увеличилась ли высота поддерева, которое она покидает. В экземпляре процедуры InsertItem, который вызвал этот рекурсивный вызов, процедура использует этот параметр для определения того, является ли проверяемое дерево несбалансированным. Если это так, то процедура применяет для балансировки дерева соответствующее вращение.

Предположим, что процедура в настоящий момент обращается к узлу X. Допустим, что она перед этим обращалась к правому поддереву снизу от узла X и что параметр has_grown равен true, означая, что правое поддерево увеличилось. Если поддеревья узла X до этого имели одинаковую высоту, тогда правое поддерево станет теперь выше левого. В этой точке дерево сбалансировано, но поддерево с корнем в узле X выросло, так как выросло его правое поддерево.

Если левое поддерево узла X вначале было выше, чем правое, то левое и правое поддеревья теперь будут иметь одинаковую высоту. Высота поддерева с корнем в узле X не изменилась — она по‑прежнему равна высоте левого поддерева плюс 1. В этом случае процедура InsertItem установит значение переменной has_grown равным false, показывая, что дерево сбалансировано.

========162

@Рис. 7.11 Различные вращения АВЛ‑дерева

======163

В конце концов, если правое поддерево узла X было первоначально выше левого, то вставка нового узла делает дерево несбалансированным в узле X. Процедура InsertItem вызывает подпрограмму RebalanceRigthGrew для балансировки дерева. Процедура RebalanceRigthGrew выполняет левое вращение или вращение вправо‑влево, в зависимости от ситуации.

Если новый элемент вставляется в левое поддерево, то подпрограмма InsertItem выполняет аналогичную процедуру.

Public Sub InsertItem(node As AVLNode, parent As AVLNode, _

txt As String, has_grown As Boolean)

Dim child As AVLNode

' Если это нижний уровень дерева, поместить

' в родителя указатель на новый узел.

If parent Is Nothing Then

Set parent = node

parent.Balance = BALANCED

has_grown = True

Exit Sub

End If

' Продолжить с левым и правым поддеревьями.

If txt <= parent.Box.Caption Then

' Вставить потомка в левое поддерево.

Set child = parent.LeftChild

InsertItem node, child, txt, has_grown

Set parent.LeftChild = child

' Проверить, нужна ли балансировка. Она будет

' не нужна, если вставка узла не нарушила

' балансировку дерева или оно уже было сбалансировано

' на более глубоком уровне рекурсии. В любом случае

' значение переменной has_grown будет равно False.

If Not has_grown Then Exit Sub

If parent.Balance = RIGHT_HEAVY Then

' Перевешивала правая ветвь, теперь баланс

' восстановлен. Это поддерево не выросло,

' поэтому дерево сбалансировано.

parent.Balance = BALANCED

has_grown = False

ElseIf parent.Balance = BALANCED Then

' Было сбалансировано, теперь перевешивает левая ветвь.

' Поддерево все еще сбалансировано, но оно выросло,

' поэтому необходимо продолжить проверку дерева.

parent.Balance = LEFT_HEAVY

Else

' Перевешивала левая ветвь, осталось несбалансировано.

' Выполнить вращение для балансировки на уровне

' этого узла.

RebalanceLeftGrew parent

has_grown = False

End If ' Закончить проверку балансировки этого узла.

Else

' Вставить потомка в правое поддерево.

Set child = parent.RightChild

InsertItem node, child, txt, has_grown

Set parent.RightChild = child

' Проверить, нужна ли балансировка. Она будет

' не нужна, если вставка узла не нарушила

' балансировку дерева или оно уже было сбалансировано

' на более глубоком уровне рекурсии. В любом случае

' значение переменной has_grown будет равно False.

If Not has_grown Then Exit Sub

If parent.Balance = LEFT_HEAVY Then

' Перевешивала левая ветвь, теперь баланс

' восстановлен. Это поддерево не выросло,

' поэтому дерево сбалансировано.

parent.Balance = BALANCED

has_grown = False

ElseIf parent.Balance = BALANCED Then

' Было сбалансировано, теперь перевешивает правая

' ветвь. Поддерево все еще сбалансировано,

' но оно выросло, поэтому необходимо продолжить

' проверку дерева.

parent.Balance = RIGHT_HEAVY

Else

' Перевешивала правая ветвь, осталось несбалансировано.

' Выполнить вращение для балансировки на уровне

' этого узла.

RebalanceRightGrew parent

has_grown = False

End If ' Закончить проверку балансировки этого узла.

End If ' End if для левого поддерева else правое поддерево.

End Sub

========165

Private Sub RebalanceRightGrew(parent As AVLNode)

Dim child As AVLNode

Dim grandchild As AVLNode

Set child = parent.RightChild

If child.Balance = RIGHT_HEAVY Then

' Выполнить левое вращение.

Set parent.RightChild = child.LeftChild

Set child.LeftChild = parent

parent.Balance = BALANCED

Set parent = child

Else

' Выполнить вращение вправо‑влево.

Set grandchild = child.LeftChild

Set child.LeftChild = grandchild.RightChild

Set grandchild.RightChild = child

Set parent.RightChild = grandchild.LeftChild

Set grandchild.LeftChild = parent

If grandchild.Balance = RIGHT_HEAVY Then

parent.Balance = LEFT_HEAVY

Else

parent.Balance = BALANCED

End If

If grandchild.Balance = LEFT_HEAVY Then

child.Balance = RIGHT_HEAVY

Else

child.Balance = BALANCED

End If

Set parent = grandchild

End If ' End if для правого вращения else двойное правое

' вращение.

parent.Balance = BALANCED

End Sub