Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
Новый узел может быть вставлен в любое из четырех поддеревьев узла X, изображенных в виде треугольников. Если вы вставляете узел в одно из этих поддеревьев, то для балансировки дерева потребуется выполнить соответствующее вращение. Помните, что иногда балансировка не нужна, если вставка нового узла не нарушает упорядоченность дерева.
Правое вращение
Вначале предположим, что новый узел вставляется в поддерево R на рис. 7.4. В этом случае не нужно изменять два правых поддерева узла X, поэтому их можно объединить, изобразив одним треугольником, как показано на рис. 7.5. Новый узел вставляется в дерево T1, при этом поддерево TA с корнем в узле A становится не менее, чем на два уровня выше, чем поддерево T3.
На самом деле, поскольку до вставки нового узла дерево было АВЛ‑деревом, то TA должно было быть выше поддерева T3 не больше, чем на один уровень. После вставки одного узла TA должно быть выше поддерева T3 ровно на два уровня.
Также известно, что поддерево T1 выше поддерева T2 не больше, чем на один уровень. Иначе узел X не был бы самым нижним узлом с несбалансированными поддеревьями. Если бы T1 было на два уровня выше, чем T2, то дерево было бы несбалансированным в узле A.
@Рис. 7.4. Анализ несбалансированного АВЛ‑дерева
========158
@Рис. 7.5. Вставка нового узла в поддерево R
В этом случае, можно переупорядочить узлы при помощи правого вращения (right rotation), как показано на рис. 7.6. Это вращение называется правым, так как узлы A и X как бы вращаются вправо.
Заметим, что это вращение сохраняет порядок «меньше» расположения узлов дерева. При симметричном обходе любого из таких деревьев обращение ко всем поддеревьям и узлам дерева происходит в порядке T1, A, T2, X, T3. Поскольку симметричный обход обоих деревьев происходит одинаково, то и порядок расположения элементов в них будет одинаковым.
Важно также заметить, что высота поддерева, с которым мы работаем, остается неизменной. Перед тем, как был вставлен новый узел, высота поддерева была равна высоте поддерева T2 плюс 2. После вставки узла и выполнения правого вращения, высота поддерева также остается равной высоте поддерева T2 плюс 2. Все части дерева, лежащие ниже узла X при этом также остаются сбалансированными, поэтому не требуется продолжать балансировку дерева дальше.
Левое вращение
Левое вращение (left rotation) выполняется аналогично правому. Оно используется, если новый узел вставляется в поддерево L, показанное на рис. 7.4. На рис. 7.7 показано АВЛ‑дерево до и после левого вращения.
@Рис. 7.6. Правое вращение
========159
@Рис. 7.7. До и после левого вращения
Вращение влево‑вправо
Если узел вставляется в поддерево LR, показанное на рис. 7.4, нужно рассмотреть еще один нижележащий уровень. На рис. 7.8. показано дерево, в котором новый узел вставляется в левую часть T2 поддерева LR. Так же легко можно вставить узел в правое поддерево T3. В обоих случаях, поддеревья TA и TC останутся АВЛ‑поддеревьями, но поддерево TX уже не будет таковым.
Так как дерево до вставки узла было АВЛ‑деревом, то TA было выше T4 не больше, чем на один уровень. Поскольку добавлен только один узел, то TA вырастет только на один уровень. Это значит, что TA теперь будет точно на два уровня выше T4.
Также известно, что поддерево T2 не более, чем на один уровень выше, чем T3. Иначе TC не было бы сбалансированным, и узел X не был бы самым нижним в дереве узлом с несбалансированными поддеревьями.
Поддерево T1 должно иметь ту же глубину, что и T3. Если бы оно было короче, то поддерево TA было бы не сбалансировано, что снова противоречит предположению о том, что узел X — самый нижний узел в дереве, имеющий несбалансированные поддеревья. Если бы поддерево T1 имело большую глубину, чем T3, то глубина поддерева T1 была бы на 2 уровня больше, чем глубина поддерева T4. В этом случае дерево было бы несбалансированным до вставки в него нового узла.
Все это означает, что нижние части деревьев выглядят в точности так, как показано на рис. 7.8. Поддерево T2 имеет наибольшую глубину, глубина T1 и T3 на один уровень меньше, а T4 расположено еще на один уровень выше, чем T3 и T3.
@Рис. 7.8. Вставка нового узла в поддерево LR
==========160
@Рис. 7.9. Вращение влево‑вправо
Используя эти факты, можно сбалансировать дерево, как показано на рис. 7.9. Это называется вращением влево‑вправо (left‑right rotation), так как при этом вначале узлы A и C как бы вращаются влево, а затем узлы C и X вращаются вправо.
Как и другие вращения, вращение этого типа не изменяет порядок элементов в дереве. При симметричном обходе дерева до и после вращения обращение к узлам и поддеревьям происходит в порядке: T1, A, T2, C, T3, X, T4.
Высота дерево после балансировки также не меняется. До вставки нового узла, правое поддерево имело высоту поддерева T1 плюс 2. После балансировки дерева, высота этого поддерева снова будет равна высоте T1 плюс 2. Это значит, что остальная часть дерева также остается сбалансированной, и нет необходимости продолжать балансировку дальше.
Вращение вправо‑влево
Вращение вправо‑влево (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
Удаление узла из АВЛ‑дерева
В 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. Вращение вправо‑влево при удалении узла
Страницы: 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
