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

========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

           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(logK+1(N)). Это означает, что сложность алгоритма поиска в таком дереве порядка O(log(N)). Хотя это и не так очевидно, операции вставки и удаления элемента из Б‑дерева также имеют сложность порядка O(log(N)).

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

=======172

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

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

Сбалансированное двоичное дерево с миллионом элементов имело бы высоту log2(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 порядка, то есть каждый узел имеет от трех до пяти дочерних узлов. Такое дерево, содержащее миллион записей, должно было бы иметь высоту между log5(1.000.000) и log3(1.000.000), или между 9 и 13. Чтобы найти элемент в таком дереве, программа должна выполнить от 9 до 13 обращений к диску.

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

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

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

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

=======177

Балансировка для устранения разбиения блоков

При добавлении элемента к блоку, который уже заполнен, блок разбивается на два. Этого можно избежать, если выполнить балансировку этого узла с одним из узлов на том же уровне. Например, вставка нового элемента Q в Б‑дерево, показанное слева на рис. 7.20 обычно вызывает разбиение блока. Этого можно избежать, выполнив балансировку узла, содержащего J, K, L и N и левого узла на том же уровне, содержащего B и E. При этом получается дерево, показанное на рис. 7.20 справа.

Страницы: 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