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

Б‑деревья

Б‑деревья (B‑trees) являются другой формой сбалансированных деревьев, немного более наглядной, чем АВЛ‑деревья. Каждый узел в Б‑дереве может содержать несколько ключей данных и несколько указателей на дочерние узлы. Поскольку каждый узел содержит несколько элементов, такие узлы иногда называются блоками.

 

=======171

 

@Рис. 7.14. Программа AVL

 

Между каждой парой соседних указателей находится ключ, который можно использовать для определения ветви, по которой нужно следовать при вставке или поиске элемента. Например, в дереве, показанном на рис. 7.15, корневой узел содержит два ключа: G и R. Чтобы найти элемент со значением, которое идет перед G, нужно искать в первой ветви. Чтобы найти элемент, имеющий значение между G и R, проверяется вторая ветвь. Чтобы найти элемент, который следует за R, выбирается третья ветвь.

Б‑дерево порядка K обладает следующими свойствами:

· Каждый узел содержит не более 2 * K ключей.

· Каждый узел, кроме может быть корневого, содержит не менее K ключей.

· Внутренний узел, имеющий M ключей, имеет M + 1 дочерних узлов.

· Все листья дерева находятся на одном уровне.

Б‑дерево на рис. 7.15 имеет 2 порядок. Каждый узел может иметь до 4 ключей. Каждый узел, кроме может быть корневого, должен иметь не менее двух ключей. Для удобства, узлы Б‑дерева обычно имеют четное число ключей, поэтому порядок дерева обычно является целым числом.

Выполнение требования, чтобы каждый узел Б­дерева порядка K содержал от K до 2 * K ключей, поддерживает дерево сбалансированным. Так как каждый узел должен иметь не менее K ключей, он должен при этом иметь не менее K + 1 дочерних узлов, поэтому дерево не может стать слишком высоким и тонким. Наибольшая высота Б‑дерева, содержащего N узлов, может быть равна O(log_K+1(N)). Это означает, что сложность алгоритма поиска в таком дереве порядка O(log(N)). Хотя это и не так очевидно, операции вставки и удаления элемента из Б‑дерева также имеют сложность порядка O(log(N)).

 

@Рис. 7.15. Б‑дерево

 

=======172

 

Производительность Б‑деревьев

Применение Б‑деревьев особенно полезно при разработке больших приложений, работающих с базами данных. При достаточно большом порядке Б‑дерева, любой элемент в дереве можно найти после проверки всего нескольких узлов. Например, высота Б‑дерева 10 порядка, содержащего миллион записей, не может быть больше log₁₁(1.000.000), или выше шести уровней. Чтобы найти определенный элемент, потребуется проверить не более шести узлов.

Сбалансированное двоичное дерево с миллионом элементов имело бы высоту log₂(1.000.000), или около 20. Тем не менее, узлы двоичного дерева содержат всего по одному ключевому значению. Для поиска элемента в двоичном дереве, пришлось бы проверить 20 узлов и 20 значений. Для поиска элемента в Б‑дереве пришлось бы проверить 5 узлов и 100 ключей.

Применение Б‑деревьев может обеспечить более высокую скорость работы, если проверка ключей выполняется относительно просто, в отличие от проверки узлов. Например, если база данных находится на диске, чтение данных с диска может происходить достаточно медленно. Когда же данные находятся в памяти, их проверка может происходить очень быстро.

Чтение данных с диска происходит большими блоками, и считывание целого блока занимает столько же времени, сколько и чтение одного байта. Если узлы Б‑дерева не слишком велики, то чтение узла Б‑дерева с диска займет не больше времени, чем чтение узла двоичного дерева. В этом случае, для поиска 5 узлов в Б‑дереве потребуется выполнить 5 медленных обращений к диску, плюс 100 быстрых обращений к памяти. Поиск 20 узлов в двоичном дереве потребует 20 медленных обращений к диску и 20 быстрых обращений к памяти, при этом поиск в двоичном дереве будет более медленным, поскольку время, затраченное на 15 лишних обращений к диску будет намного больше, чем сэкономленное время 80 обращений к памяти. Вопросы, связанные с обращением к диску, позднее обсуждаются в этой главе более подробно.

Вставка элементов в Б‑дерево

Чтобы вставить новый элемент в Б‑дерево, найдем лист, в который он должен быть помещен. Если этот узел содержит менее, чем 2 * K ключей, то в этом узле остается место для добавления нового элемента. Вставим новый узел на место так, чтобы порядок элементов внутри узла не нарушился.

Если узел уже содержит 2 * K элементов, то места для нового элемента в узле уже не остается. Разобьем тогда узел на два новых узла, поместив в каждый из них K элементов в правильном порядке. Затем средний элемент переместим в родительский узел.

Например, предположим, что мы хотим поместить новый элемент Q в Б‑дерево, показанное на рис. 7.15. Этот новый элемент должен находиться во втором листе, который уже заполнен. Для разбиения этого узла, разделим элементы J, K, L, N и Q между двумя новыми узлами. Поместим элементы J и K в левый узел, а элементы N и Q — в правый. Затем переместим средний элемент, L[RV13] в родительский узел. На рис. 7.16 показано новое дерево.

 

@Рис. 7.16. Б‑дерево после вставки элемента Q

 

=========173

 

Разбиение узла на два называется разбиением блока. Когда оно происходит, к родительскому узлу добавляется новый ключ и новый указатель. Если родительский узел уже заполнен, то это также может привести к его разбиению. Это, в свою очередь, потребует добавления новой записи на более высоком уровне и так далее. В наихудшем случае, вставка элемента вызовет «цепную реакцию», которая приведет к изменениям на всех вышележащих уровнях вплоть до разбиения корневого узла.

Когда происходит разбиение корневого узла, Б‑дерево становится выше. Это единственный случай, при котором его высота увеличивается. Поэтому Б‑деревья обладают необычным свойством — они всегда растут от листьев к корню.

Удаление элементов из Б‑дерева

Теоретически, удалить узел из Б‑дерева так же просто, как и вставить его. На практике, детали этого процесса достаточно сложны.

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

Чтобы удалить элемент из листа, вначале нужно при необходимости сдвинуть все другие элементы влево, чтобы заполнить образовавшееся пространство. Помните, что каждый узел в Б‑дереве порядка K должен иметь от K до 2 * K элементов. После удаления элемента из листа, может оказаться, что он содержит всего K - 1 элементов.

В этом случае, можно попробовать взять несколько элементов из узлов на том же уровне. Затем можно распределить элементы в двух узлах так, чтобы они оба имели не меньше K элементов. На рис. 7.17 элемент удаляется из самого левого листа дерева, при этом в нем остается всего один элемент. После перераспределения элементов между узлом и правым узлом на том же уровне, оба узла имеют не меньше двух ключей. Заметьте, что средний элемент J перемещается в родительский узел.

 

@Рис. 7.17. Балансировка после удаления элемента

 

=======174

 

@Рис. 7.18. Слияние после удаления элемента

 

При попытке сбалансировать дерево таким образом, может оказаться, что соседний узел на том же уровне содержит всего K элементов. Тогда два узла вместе содержат всего 2 * K - 1 элементов, что недостаточно для заполнения двух узлов. В этом случае, все элементы из обоих узлов могут поместиться в одном узле, поэтому их можно слить. Удалим ключ, который отделяет два узла от родителя. Поместим этот элемент и 2 * K - 1 элементов из двух узлов в один общий узел. Этот процесс называется слиянием узлов (bucket merge или bucket join). На рис. 7.18 показано слияние двух узлов.

При слиянии двух узлов, из родительского узла удаляется ключ, при этом в родительском узле может остаться K - 1 элементов. В этом случае, может потребоваться балансировка или слияние родителя с одним из узлов на его уровне. Это также может привести к тому, что в узле на более высоком уровне также останется K - 1 элементов, и процесс повторится. В наихудшем случае, удаление приведет к «цепной реакции» слияний блоков, которая может дойти до корневого узла.

При удалении последнего элемента из корневого узла, два его оставшихся дочерних узла сливаются, образуя новый корень, и дерево при этом становится короче на один уровень. Единственный способ уменьшения высоты Б‑дерева — слияние двух дочерних узлов корня и образование нового корня.

Программа Btree позволяет вам оперировать Б‑деревом. Введите текст, и нажмите на кнопку Add, чтобы добавить элемент в дерево. Для удаления элемента введите его значение и нажмите на кнопку Remove. На рис. 7.19 показано окно программы Btree с Б‑деревом 2 порядка.

 

@Рис. 7.19. Программа Btree

 

========175

 

Разновидности Б‑деревьев

Существует несколько разновидностей Б‑деревьев, из которых здесь описаны только некоторые. Нисходящие Б‑деревья (top‑down B‑trees) немного иначе управляют структурой Б‑дерева. За счет разбиения встречающихся полных узлов, эта разновидность алгоритма использует при вставке элементов более наглядную нисходящую рекурсию вместо восходящей. Эта также уменьшает вероятность возникновения длительной последовательности разбиений блоков.

Другой разновидностью Б‑деревьев являются Б+деревья (B+trees). В Б+деревьях внутренние узлы содержат только ключи данных, а сами записи находятся в листьях. Это позволяет Б+деревьям хранить в каждом блоке больше элементов, поэтому такие деревья короче, чем соответствующие Б‑деревья.

Нисходящие Б‑деревья

Подпрограмма, которая добавляет новый элемент в Б‑дерево, вначале выполняет рекурсивный поиск по дереву, чтобы найти блок, в который его нужно поместить. Когда она пытается вставить новый элемент на его место, ей может понадобиться разбить блок и переместить один из элементов узла в его родительский узел.

При возврате из рекурсивных вызовов процедуры, вызывающая процедура проверяет, требуется ли разбиение родительского узла. Если да, то элемент помещается в родительский узел. При каждом возврате из рекурсивного вызова, вызывающая процедура должна проверять, не требуется ли разбиение следующего предка. Так как эти разбиения блоков происходят при возврате из рекурсивных вызовов процедура, это восходящая рекурсия, поэтому иногда Б‑деревья, которыми манипулируют таким образом, называются восходящими Б‑деревьями (bottom‑up B‑trees).

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

Когда процедура доходит до листа, в который нужно поместить элемент, то в его родительском узле всегда есть свободное место, и если программе нужно разбить лист, то всегда можно поместить средний элемент в родительский узел. Так как при этом процедура работает с деревом сверху вниз, Б‑деревья такого типа иногда называются нисходящими Б‑деревьями (top‑down B‑trees).

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

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

 

==========176

 

Б+деревья

Б+деревья часто используются для хранения больших записей. Типичное Б‑дерево может содержать записи о сотрудниках, каждая из которых может занимать несколько килобайт памяти. Записи могли бы располагаться в Б‑дереве в соответствии с ключевым полем, например фамилией сотрудника или его идентификационным номером.

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

Чтобы избежать перемещения больших блоков данных, программа может записывать во внутренних узлах Б‑дерева только ключи. При этом узлы также содержат ссылки на сами записи данных, которые записаны в другом месте. Теперь, если программе требуется переупорядочить блоки, то нужно переместить только ключи и указатели, а не сами записи. Этот тип Б‑дерева называется Б+деревом (B+tree).

То, что элементы в Б+дереве достаточно малы, также позволяет программе хранить больше ключей в каждом узле. При том же размере узла, программа может увеличить порядок дерева и сделать его более коротким.

Например, предположим, что имеется Б‑дерево 2 порядка, то есть каждый узел имеет от трех до пяти дочерних узлов. Такое дерево, содержащее миллион записей, должно было бы иметь высоту между log₅(1.000.000) и log₃(1.000.000), или между 9 и 13. Чтобы найти элемент в таком дереве, программа должна выполнить от 9 до 13 обращений к диску.

Теперь допустим, что те же миллион записей находятся в Б+дереве, узлы которого имеют примерно тот же размер в байтах. Поскольку в узлах Б+дерева содержатся только ключи, то в каждом узле дерева может храниться до 20 ключей к записям. В этом случае, каждый узел будет иметь от 11 до 21 дочерних узлов, поэтому высота дерева будет от log₂₁(1.000.000) до log₁₁(1.000.000), или между 5 и 6. Чтобы найти элемент, программе понадобится всего 6 обращений к диску для нахождения его ключа, и еще одно обращение к диску, чтобы считать сам элемент.

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

Улучшение производительности Б‑деревьев

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

 

=======177