Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

        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.

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

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

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

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

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

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

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

========167

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

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

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

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

Реализация удаления узлов на языке 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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82