Вставка узлов на языке 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

 

Удаление узла из АВЛ‑дерева

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

 

======166

 

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

Левое вращение

Предположим, что мы удаляем узел из левого поддерева узла X. Также предположим, что правое поддерево либо уравновешено, либо высота его правой половины на единицу больше, чем высота левой. Тогда левое вращение, показанное на рис. 7.12, приведет к балансировке дерева в узле X.

Нижний уровень поддерева T₂ закрашен серым цветом, чтобы показать, что поддерево T_B либо уравновешено (T₂ и T₃ имеют одинаковую высоту), либо его правая половина выше (T₃ выше, чем T₂). Другими словами, закрашенный уровень может существовать в поддереве T₂ или отсутствовать.

Если T₂ и T₃ имеют одинаковую высоту, то высота поддерева T_X с корнем в узле X не меняется после удаления узла. Высота T_X при этом остается равной высоте поддерева T₂ плюс 2. Так как эта высота не меняется, то дерево выше этого узла остается сбалансированным.

Если T₃ выше, чем T₂, то поддерево T_X становится ниже на единицу. В этом случае, дерево может быть несбалансированным выше узла X, поэтому необходимо продолжить проверку дерева, чтобы определить, выполняется ли свойство АВЛ‑деревьев для предков узла X.

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

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

Если левое или правое поддеревья T₂ или T₃ выше, то вращение вправо‑влево приведет к балансировке поддерева T_X, и уменьшит при этом высоту T_X на единицу. Это значит, что дерево выше узла X может быть несбалансированным, поэтому необходимо продолжить проверку выполнения свойства АВЛ‑деревьев для предков узла X.

 

@Рис. 7.12. Левое вращение при удалении узла

 

========167

 

@Рис. 7.13. Вращение вправо‑влево при удалении узла

 

Другие вращения

Остальные вращения выполняются аналогично. В этом случае удаляемый узел находится в правом поддереве узла X. Эти четыре вращения — те же самые, которые использовались для балансировки дерева при вставке узла, за одним исключением.

Если новый узел вставляется в дерево, то первое выполняемое вращение осуществляет балансировку поддерева T_X, не изменяя его высоту. Это значит, что дерево выше узла T_X будет при этом оставаться сбалансированным. Если же эти вращения используются после удаления узла из дерева, то вращение может уменьшить высоту поддерева T_X на единицу. В этом случае, нельзя быть уверенным, что дерево выше узла X осталось сбалансированным. Нужно продолжить проверку выполнения свойства АВЛ‑деревьев вверх по дереву.