Реализация удаления узлов на языке Visual Basic

Подпрограмма DeleteItem удаляет элементы из дерева. Она рекурсивно спускается по дереву в поиске удаляемого элемента и когда она находит искомый узел, то удаляет его. Если у этого узла нет потомков, то процедура завершается. Если есть только один потомок, то процедура заменяет узел его потомком.

Если узел имеет двух потомков, процедура DeleteItem вызывает процедуру ReplaceRightMost для замены искомого узла самым правым узлом в его левой ветви. Процедура ReplaceRightMost выполняется примерно так же, как и процедура из 6 главы, которая удаляет элементы из обычного (неупорядоченного) дерева. Основное отличие возникает при возврате из процедуры и рекурсивном проходе вверх по дереву. При этом процедура ReplaceRightMost использует восходящую рекурсию, чтобы убедиться, что дерево остается сбалансированным для всех узлов.

При каждом возврате из процедуры, экземпляр процедуры ReplaceRightMost вызывает подпрограмму RebalanceRightShrunk, чтобы убедиться, что дерево в этой точке сбалансировано. Так как процедура ReplaceRightMost опускается по правой ветви, то она всегда использует для выполнения балансировки подпрограмму RebalanceRightShrunk, а не RebalanceLeftShrunk.

При первом вызове подпрограммы ReplaceRightMost процедура DeleteItem направляет ее по левой от удаляемого узла ветви. При возврате из первого вызова подпрограммы ReplaceRightMost, процедура DeleteItem использует подпрограмму RebalanceLeftShrunk, чтобы убедиться, что дерево сбалансировано в этой точке.

=========168

После этого, один за другим происходят рекурсивные возвраты из процедуры DeleteItem при проходе дерева в обратном направлении. Так же, как и процедура ReplaceRightmost, процедура DeleteItem вызывает подпрограммы RebalanceRightShrunk или RebalanceLeftShrunk в зависимости от того, по какому пути происходит спуск по дереву.

Подпрограмма RebalanceLeftShrunk аналогична подпрограмме RebalanceRightShrunk, поэтому она не показана в следующем коде.

Public Sub DeleteItem(node As AVLNode, txt As String, shrunk As Boolean)

Dim child As AVLNode

Dim target As AVLNode

If node Is Nothing Then

Beep

MsgBox "Элемент " & txt & " не содержится в дереве."

shrunk = False

Exit Sub

End If

If txt < node.Box.Caption Then

Set child = node.LeftChild

DeleteItem child, txt, shrunk

Set node.LeftChild = child

If shrunk Then RebalanceLeftShrunk node, shrunk

ElseIf txt > node.Box.Caption Then

Set child = node.RightChild

DeleteItem child, txt, shrunk

Set node.RightChild = child

If shrunk Then RebalanceRightShrunk node, shrunk

Else

Set target = node

If target.RightChild Is Nothing Then

' Потомков нет или есть только правый.

Set node = target.LeftChild

shrunk = True

ElseIf target.LeftChild Is Nothing Then

' Есть только правый потомок.

Set node = target.RightChild

shrunk = True

Else

' Есть два потомка.

Set child = target.LeftChild

ReplaceRightmost child, shrunk, target

Set target.LeftChild = child

If shrunk Then RebalanceLeftShrunk node, shrunk

End If

End If

End Sub

Private Sub ReplaceRightmost(repl As AVLNode, shrunk As Boolean, target As AVLNode)

Dim child As AVLNode

If repl.RightChild Is Nothing Then

target.Box.Caption = repl.Box.Caption

Set target = repl

Set repl = repl.LeftChild

shrunk = True

Else

Set child = repl.RightChild

ReplaceRightmost child, shrunk, target

Set repl.RightChild = child

If shrunk Then RebalanceRightShrunk repl, shrunk

End If

End Sub

Private Sub RebalanceRightShrunk(node As AVLNode, shrunk As Boolean)

Dim child As AVLNode

Dim child_bal As Integer

Dim grandchild As AVLNode

Dim grandchild_bal As Integer

If node.Balance = RIGHT_HEAVY Then

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

node.Balance = BALANCED

ElseIf node.Balance = BALANCED Then

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

node.Balance = LEFT_HEAVY

shrunk = False

Else

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

Set child = node.LeftChild

child_bal = child.Balance

If child_bal <= 0 Then

' Правое вращение.

Set node.LeftChild = child.RightChild

Set child.RightChild = node

If child_bal = BALANCED Then

node.Balance = LEFT_HEAVY

child.Balance = RIGHT_HEAVY

shrunk = False

Else

node.Balance = BALANCED

child.Balance = BALANCED

End If

Set node = child

Else

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

Set grandchild = child.RightChild

grandchild_bal = grandchild.Balance

Set child.RightChild = grandchild.LeftChild

Set grandchild.LeftChild = child

Set node.LeftChild = grandchild.RightChild

Set grandchild.RightChild = node

If grandchild_bal = LEFT_HEAVY Then

node.Balance = RIGHT_HEAVY

Else

node.Balance = BALANCED

End If

If grandchild_bal = RIGHT_HEAVY Then

child.Balance = LEFT_HEAVY

Else

child.Balance = BALANCED

End If

Set node = grandchild

grandchild.Balance = BALANCED

End If

End If

End Sub

Программа AVL оперирует АВЛ‑деревом. Введите текст и нажмите на кнопку Add, чтобы добавить элемент к дереву. Введите значение, и нажмите на кнопку Remove, чтобы удалить этот элемент из дерева. На рис. 7.14 показана программа AVL.