|
VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования' Сохранить текущие значения. SaveValues Depth, Dx, Dy, 4 ' Подготовиться к рекурсии. Depth = Depth - 1 ' Dx и Dy остаются без изменений. pc = 1 Перейти в начало рекурсивного вызова. Else ' Условие остановки. ' Достаточно глубокий уровень рекурсии. ' Продолжить с 4 блоком кода. pc = 4 End If Case 4 HilbertPicture.Line -Step(-Dx, -Dy) If Depth > 1 Then ' Рекурсия. ' Сохранить текущие значения. SaveValues Depth, Dx, Dy, 0 ' Подготовиться к рекурсии. Depth = Depth - 1 tmp = Dx Dx = -Dy Dy = -tmp pc = 1 Перейти в начало рекурсивного вызова. Else ' Условие остановки. ' Достаточно глубокий уровень рекурсии. ' Конец этого рекурсивного вызова. pc = 0 End If Case 0 ' Возврат из рекурсии. If TopOfStack > 0 Then RestoreValues Depth, Dx, Dy, pc Else ' Стек пуст. Выход. Exit Do End If End Select Loop End Sub ======111 Время выполнения этого алгоритма может быть нелегко оценить непосредственно. Поскольку методы преобразования рекурсивных процедур в нерекурсивные не изменяют время выполнения алгоритма, эта процедура так же, как и предыдущая версия, имеет время выполнения порядка O(N4). Программа Hilbert2 демонстрирует нерекурсивный алгоритм построения кривых Гильберта. Задавайте вначале построение несложных кривых (меньше 6 порядка), пока не узнаете, насколько быстро будет выполняться эта программа на вашем компьютере. Нерекурсивное построение кривых Серпинского Приведенный ранее алгоритм построения кривых Серпинского включает в себя косвенную и множественную рекурсию. Так как алгоритм состоит из четырех подпрограмм, которые вызывают друг друга, то нельзя просто пронумеровать важные строки, как это можно было сделать в случае алгоритма построения кривых Гильберта. С этой проблемой можно справиться, слегка изменив алгоритм. Рекурсивная версия этого алгоритма состоит из четырех подпрограмм SierpA, SierpB, SierpC и SierpD. Подпрограмма SierpA выглядит так: Private Sub SierpA(Depth As Integer, Dist As Single) If Depth = 1 Then Line -Step(-Dist, Dist) Line -Step(-Dist, 0) Line -Step(-Dist, -Dist) Else SierpA Depth - 1, Dist Line -Step(-Dist, Dist) SierpB Depth - 1, Dist Line -Step(-Dist, 0) SierpD Depth - 1, Dist Line -Step(-Dist, -Dist) SierpA Depth - 1, Dist End If End Sub Три другие процедуры аналогичны. Несложно объединить эти четыре процедуры в одну подпрограмму. Private Sub SierpAll(Depth As Integer, Dist As Single, Func As Integer) Select Case Punc Case 1 ' SierpA Case 2 ' SierpB Case 3 ' SierpC Case 4 ' SierpD End Select End Sub ======112 Параметр Func сообщает подпрограмме, какой блок кода выполнять. Вызовы подпрограмм заменяются на вызовы процедуры SierpAll с соответствующим значением Func. Например, вызов подпрограммы SierpA заменяется на вызов процедуры SierpAll с параметром Func, равным 1. Таким же образом заменяются вызовы подпрограмм SierpB, SierpC и SierpD. Полученная процедура рекурсивно вызывает себя в 16 различных точках. Эта процедура намного сложнее, чем процедура Hilbert, но в других отношениях она имеет такую же структуру и поэтому к ней можно применить те же методы устранения рекурсии. Можно использовать первую цифру меток pc, для определения номера блока кода, который должен выполняться. Перенумеруем строки в коде SierpA числами 11, 12, 13 и т.д. Перенумеруем строки в коде SierpB числами 21, 22, 23 и т.д. Теперь можно пронумеровать ключевые строки кода внутри каждого из блоков. Для кода подпрограммы SierpA ключевыми строками будут: ' Код SierpA. 11 If Depth = 1 Then Line -Step(-Dist, Dist) Line -Step(-Dist, 0) Line -Step(-Dist, -Dist) Else SierpA Depth - 1, Dist 12 Line -Step(-Dist, Dist) SierpB Depth - 1, Dist 13 Line -Step(-Dist, 0) SierpD Depth - 1, Dist 14 Line -Step(-Dist, -Dist) SierpA Depth - 1, Dist End If Типичная «рекурсия» из кода подпрограммы SierpA в код подпрограммы SierpB выглядит так: SaveValues Depth, 13 ' Продолжить с шага 13 после завершения. Depth = Depth - 1 pc = 21 ' Передать управление на начало кода SierpB. ======113 Метка 0 зарезервирована для обозначения выхода из «рекурсии». Следующий код демонстрирует нерекурсивную версию процедуры SierpAll. Код для подпрограмм SierpB, SierpC, и SierpD аналогичен коду для SierpA, поэтому он опущен. Private Sub SierpAll(Depth As Integer, pc As Integer) Do Select Case pc ' ********** ' * SierpA * ' ********** Case 11 If Depth " & Format$(ToNode(link)) Next link @Рис. 6.6. Программа Nary =======123 На рис. 6.7 показано дерево и его представление нумерацией связей. Связи, выходящие из 3 узла (обозначенного буквой D) это связи от FirstLink(3) до FirstLink(4)-1. Значение FirstLink(3) равно 9, а FirstLink(4) = 11, поэтому это связи с номерами 9 и 10. Записи ToNode для этих связей равны ToNode(9) = 10 и ToNode(10) = 11, поэтому узлы 10 и 11 будут дочерними для 3 узла. Это узлы, обозначенные буквами K и L. Это означает, что связи, покидающие узел D, ведут к узлам K и L. Представление дерева нумерацией связей компактно и основано на массиве, поэтому деревья, представленные таким образом, можно легко считывать из файлов и записывать в файл. Операции для работы с массивами, которые используются при таком представлении, также могут быть быстрее, чем операции, нужные для использования узлов, содержащих коллекции дочерних узлов. По этим причинам большая часть литературы по сетевым алгоритмам использует представление нумерацией связей. Например, многие статьи, касающиеся вычисления кратчайшего пути, предполагают, что данные находятся в подобном формате. Если вам когда-либо придется изучать эти алгоритмы в журналах, таких как “Management Science” или “Operations Research”, вам необходимо разобраться в этом представлении. @Рис. 6.7. Дерево и его представление нумерацией связей =======123 Используя представление нумерацией связей, можно быстро найти связи, выходящие из определенного узла. С другой стороны, очень сложно изменять структуру данных, представленных в таком виде. Чтобы добавить к узлу A на рис. 6.7 еще одного потомка, придется изменить почти все элементы в обоих массивах FirstLink и ToNode. Во-первых, каждый элемент в массиве ToNode нужно сдвинуть на одну позицию вправо, чтобы освободить место под новый элемент. Затем, нужно вставить новую запись в массив ToNode, которая указывает на новый узел. И, наконец, нужно обойти массив ToNode, обновив каждый элемент, чтобы он указывал на новое положение соответствующей записи ToNode. Поскольку все записи в массиве ToNode сдвинулись на одну позицию вправо, чтобы освободить место для новой связи, потребуется добавить единицу ко всем затронутым записям FirstLink. На рис. 6.8 показано дерево после добавления нового узла. Записи, которые изменились, закрашены серым цветом. Удаление узла из начала представления нумерацией связей так же сложно, как и вставка узла. Если удаляемый узел имеет потомков, процесс занимает еще больше времени, поскольку придется удалять и все дочерние узлы. Относительно простой класс с открытой коллекцией дочерних узлов лучше подходит, если нужно часто модифицировать дерево. Обычно проще понимать и отлаживать процедуры, которые оперируют деревьями в этом представлении. С другой стороны, представление нумерацией связей иногда обеспечивает более высокую производительность для сложных алгоритмов работы с деревьями. Оно также являются стандартной структурой данных, обсуждаемой в литературе, поэтому вам следует ознакомиться с ним, если вы хотите продолжить изучение алгоритмов работы с сетями и деревьями. @Рис. 6.8. Вставка узла в дерево, представленное нумерацией связей =======124 Программа Fstar использует представление нумерацией связей для работы с деревом, имеющим узлы разного порядка. Она аналогична программе NAry, за исключением того, что она использует представление на основе массива, а не коллекций. Если вы посмотрите на код программы Fstar, вы увидите, насколько сложно в ней добавлять и удалять узлы. Следующий код демонстрирует удаление узла из дерева. Sub FreeNodeAndChildren(ByVal parent As Integer, _ ByVal link As Integer, ByVal node As Integer) ' Recursively remove the node's children. Do While FirstLink(node) < FirstLink(node + 1) FreeNodeAndChildren node, FirstLink(node), _ ToNode(FirstLink(node)) Loop ' Удалить связь. RemoveLink parent, link ' Удалить сам узел. RemoveNode node End Sub Sub RemoveLink(node As Integer, link As Integer) Dim i As Integer ' Обновить записи массива FirstLink. For i = node + 1 To NumNodes FirstLink(i) = FirstLink(i) - 1 Next i ' Сдвинуть массив ToNode чтобы заполнить пустую ячейку. For i = link + 1 To NumLinks - 1 ToNode(i - 1) = ToNode(i) Next i ' Удалить лишний элемент из ToNode. NumLinks = NumLinks - 1 If NumLinks > 0 Then ReDim Preserve ToNode(0 To NumLinks - 1) End Sub Sub RemoveNode(node As Integer) Dim i As Integer ' Сдвинуть элементы массива FirstLink, чтобы заполнить ' пустую ячейку. For i = node + 1 To NumNodes FirstLink(i - 1) = FirstLink(i) Next i ' Сдвинуть элементы массива NodeCaption. For i = node + 1 To NumNodes - 1 NodeCaption(i - 1) = NodeCaption(i) Next i ' Обновить записи массива ToNode. For i = 0 To NumLinks - 1 If ToNode(i) >= node Then ToNode(i) = ToNode(i) - 1 Next i ' Удалить лишнюю запись массива FirstLink. NumNodes = NumNodes - 1 ReDim Preserve FirstLink(0 To NumNodes) ReDim Preserve NodeCaption(0 To NumNodes - 1) Unload FStarForm.NodeLabel(NumNodes) End Sub Это намного сложнее, чем соответствующий код в программе NAry: Public Function DeleteDescendant(target As NAryNode) As Boolean Dim i As Integer Dim child As NAryNode ' Является ли узел дочерним узлом. For i = 1 To Children.Count If Children.Item(i) Is target Then Children.Remove i DeleteDescendant = True Exit Function End If Next i ' Если это не дочерний узел, рекурсивно ' проверить остальных потомков. For Each child In Children If child.DeleteDescendant(target) Then DeleteDescendant = True Exit Function End If Next child End Function =======125-126 Полные деревья Полное дерево (complete tree) содержит максимально возможное число узлов на каждом уровне, кроме нижнего. Все узлы на нижнем уровне сдвигаются влево. Например, каждый уровень троичного дерева содержит в точности три дочерних узла, за исключением листьев, и возможно, одного узла на один уровень выше листьев. На рис. 6.9 показаны полные двоичное и троичное деревья. Полные деревья обладают рядом важных свойств. Во-первых, это кратчайшие деревья, которые могут содержать заданное число узлов. Например, двоичное дерево на рис. 6.9 — одно из самых коротких двоичных деревьев с шестью узлами. Существуют другие двоичные деревья с шестью узлами, но ни одно из них не имеет высоту меньше 3. Во-вторых, если полное дерево порядка D состоит из N узлов, оно будет иметь высоту порядка O(logD(N)) и O(N) листьев. Эти факты имеют большое значение, поскольку многие алгоритмы обходят деревья сверху вниз или в противоположном направлении. Время выполнения алгоритма, выполняющего одно из этих действий, будет порядка O(N). Чрезвычайно полезное свойство полных деревьев заключается в том, что они могут быть очень компактно записаны в массивах. Если пронумеровать узлы в «естественном» порядке, сверху вниз и слева направо, то можно поместить элементы дерева в массив в этом порядке. На рис. 6.10 показано, как можно записать полное дерево в массиве. Корень дерева находится в нулевой позиции. Дочерние узлы узла I находятся на позициях 2 * I + 1 и 2 * I + 2. Например, на рис. 6.10, потомки узла в позиции 1 (узла B), находятся в позициях 3 и 4 (узлы D и E). Легко обобщить это представление на полные деревья более высокого порядка D. Корень дерева также будет находиться в позиции 0. Потомки узла I занимают позиции от D * I + 1 до D * I +(I - 1). Например, в троичном дереве, потомки узла в позиции 2, будут занимать позиции 7, 8 и 9. На рис. 6.11 показано полное троичное дерево и его представление в виде массива. @Рис. 6.9. Полные деревья =========127 @Рис. 6.10. Запись полного двоичного дерева в массиве При использовании этого метода записи дерева в массиве легко и просто получить доступ к потомкам узла. При этом не требуется дополнительной памяти для коллекций дочерних узлов или меток в случае представления нумерацией связей. Чтение и запись дерева в файл сводится просто к сохранению или чтению массива. Поэтому это несомненно лучшее представление дерева для программ, которые сохраняют данные в полных деревьях. Обход дерева Последовательное обращение ко всем узлам называется обходом (traversing) дерева. Существует несколько последовательностей обхода узлов двоичного дерева. Три простейших из них — прямой (preorder), симметричный (inorder), и обратный (postorder)обход, описываются простыми рекурсивными алгоритмами. Для каждого заданного узла алгоритмы выполняют следующие действия: Прямой обход: 1. Обращение к узлу. 2. Рекурсивный прямой обход левого поддерева. 3. Рекурсивный прямой обход правого поддерева. Симметричный обход: 1. Рекурсивный симметричный обход левого поддерева. 2. Обращение к узлу. 3. Рекурсивный симметричный обход левого поддерева. Обратный обход: 1. Рекурсивный обратный обход левого поддерева. 2. Рекурсивный обратный обход правого поддерева. 3. Обращение к узлу. @Рис. 6.11. Запись полного троичного дерева в массиве =======128 Все три порядка обхода являются примерами обхода в глубину (depth-first traversal). Обход начинается с прохода вглубь дерева до тех пор, пока алгоритм не достигнет листьев. При возврате из рекурсивного вызова подпрограммы, алгоритм перемещается по дереву в обратном направлении, просматривая пути, которые он пропустил при движении вниз. Обход в глубину удобно использовать в алгоритмах, которые должны вначале обойти листья. Например, метод ветвей и границ, описанный в 8 главе, как можно быстрее пытается достичь листьев. Он использует результаты, полученные на уровне листьев для уменьшения времени поиска в оставшейся части дерева. Четвертый метод перебора узлов дерева — это обход в ширину (breadth-first traversal). Этот метод обращается ко всем узлам на заданном уровне дерева, перед тем, как перейти к более глубоким уровням. Алгоритмы, которые проводят полный поиск по дереву, часто используют обход в ширину. Алгоритм поиска кратчайшего маршрута с установкой меток, описанный в 12 главе, представляет собой обход в ширину, дерева кратчайшего пути в сети. На рис. 6.12 показано небольшое дерево и порядок, в котором перебираются узлы во время прямого, симметричного и обратного обхода, а также обхода в ширину. @Рис. 6.12. Обходы дерева ======129 Для деревьев больше, чем 2 порядка, все еще имеет смысл определять прямой, обратный обход, и обход в ширину. Симметричный обход определяется неоднозначно, так как обращение к каждому узлу может происходить после обращения к одному, двум, или трем его потомкам. Например, в троичном дереве, обращение к узлу может происходить после обращения к его первому потомку или после обращения ко второму потомку. Детали реализации обхода зависят от того, как записано дерево. Для обхода дерева на основе коллекций дочерних узлов, программа должна использовать несколько другой алгоритм, чем для обхода дерева, записанного при помощи нумерации связей. Особенно просто обходить полные деревья, записанные в массиве. Алгоритм обхода в ширину, который требует дополнительных усилий в других представлениях деревьев, для представлений на основе массива тривиален, так как узлы записаны в таком же порядке. Следующий код демонстрирует алгоритмы обхода полного двоичного дерева: Dim NodeLabel() As String ' Запись меток узлов. Dim NumNodes As Integer ' Инициализация дерева. : Private Sub Preorder(node As Integer) Print NodeLabel (node) ' Узел. ' Первый потомок. If node * 2 + 1 0 node = queue.Item(1) queue.Remove 1 ' Обращение к узлу. Print NodeLabel(node) ' Поместить в очередь потомков узла. For Each child In node.Children queue.Add child Next child Loop End Sub =====132 Программа Trav2 демонстрирует обход деревьев, использующих коллекции дочерних узлов. Программа является объединением программ Nary, которая оперирует деревьями порядка N, и программы Trav1, которая демонстрирует обходы деревьев. Выберите узел, и нажмите на кнопку Add Child (Добавить дочерний узел), чтобы добавить к узлу потомка. Нажмите на кнопки Preorder, Inorder, Postorder или Breadth First, чтобы увидеть примеры соответствующих обходов. На рис. 6.14 показана программа Trav2, которая отображает обратный обход. Упорядоченные деревья Двоичные деревья часто являются естественным способом представления и обработки данных в компьютерных программах. Поскольку многие компьютерные операции являются двоичными, они естественно преобразуются в операции с двоичными деревьями. Например, можно преобразовать двоичное отношение «меньше» в двоичное дерево. Если использовать внутренние узлы дерева для обозначения того, что «левый потомок меньше правого» вы можете использовать двоичное дерево для записи упорядоченного списка. На рис. 6.15 показано двоичное дерево, содержащее упорядоченный список с числами 1, 2, 4, 6, 7, 9. @Рис. 6.14. Пример обратного обхода дерева в программе Trav2 ======133 @Рис. 6.15. Упорядоченный список: 1, 2, 4, 6, 7, 9. Добавление элементов Алгоритм вставки нового элемента в дерево такого типа достаточно прост. Начнем с корневого узла. По очереди сравним значения всех узлов со значением нового элемента. Если значение нового элемента меньше или равно значению узла, перейдем вниз по левой ветви дерева. Если новое значение больше, чем значение узла, перейдем вниз по правой ветви. Когда этот процесс дойдет до листа, элемент помещается в эту точку. Чтобы поместить значение 8 в дерево, показанное на рис. 6.15, мы начинаем с корня, который имеет значение 4. Поскольку 8 больше, чем 4, переходим по правой ветви к узлу 9. Поскольку 8 меньше 9, переходим затем по левой ветви к узлу 7. Поскольку 8 больше 7, снова пытаемся пойти по правой ветви, но у этого узла нет правого потомка. Поэтому новый элемент вставляется в этой точке, и получается дерево, показанное на рис. 6.16. Следующий код добавляет новое значение ниже узла в упорядоченном дереве. Программа начинает вставку с корня, вызывая процедуру InsertItem Root, new_value. Private Sub InsertItem(node As SortNode, new_value As Integer) Dim child As SortNode If node Is Nothing Then ' Мы дошли до листа. ' Вставить элемент здесь. Set node = New SortNode node.Value = new_value MaxBox = MaxBox + 1 Load NodeLabel(MaxBox) Set node.Box = NodeLabel(MaxBox) With NodeLabel(MaxBox) .Caption = Format$(new_value) .Visible = True End With ElseIf new_value node.Value Then ' Продолжить для правого поддерева. Set child = node.RightChild DeleteItem child, target_value Set node.RightChild = child Else ' Искомый узел найден. Set target = node If target.LeftChild Is Nothing Then ' Заменить искомый узел его правым потомком. Set node = node.RightChild ElseIf target.RightChild Is Nothing Then ' Заменить искомый узел его левым потомком. Set node = node.LeftChild Else ' Вызов подпрограмы ReplaceRightmost для замены ' искомого узла самым правым узлом ' в его левой ветви. Set child = node.LeftChild ReplaceRightmost node, child Set node.LeftChild = child End If End If End Sub Private Sub ReplaceRightmost(target As SortNode, repl As SortNode) Dim old_repl As SortNode Dim child As SortNode If Not (repl.RightChild Is Nothing) Then ' Продолжить движение вправо и вниз. Set child = repl.RightChild ReplaceRightmost target, child Set repl.RightChild = child Else ' Достигли дна. ' Запомнить заменяющий узел repl. Set old_repl = repl ' Заменить узел repl его левым потомком. Set repl = repl.LeftChild ' Заменить искомый узел target with repl. Set old_repl.LeftChild = target.LeftChild Set old_repl.RightChild = target.RightChild Set target = old_repl End If End Sub ======137-138 Алгоритм использует в двух местах прием передачи параметров в рекурсивные подпрограммы по ссылке. Во-первых, подпрограмма DeleteItem использует этот прием для того, чтобы родитель искомого узла указывал на заменяющий узел. Следующие операторы показывают, как вызывается подпрограмма DeleteItem: Set child = node.LeftChild DeleteItem child, target_value Set node.LeftChild = child Когда процедура обнаруживает искомый узел (узел 8 на рис. 6.19), она получает в качестве параметра узла указатель родителя на искомый узел. Устанавливая параметр на замещающий узел (узел 7), подпрограмма DeleteItem задает дочерний узел для родителя так, чтобы он указывал на новый узел. Следующие операторы показывают, как процедура ReplaceRightMost рекурсивно вызывает себя: Set child = repl.RightChild ReplaceRightmost target, child Set repl.RightChild = child Когда процедура находит самый правый узел в левой от удаляемого узла ветви (узел 7), в параметре repl находится указатель родителя на самый правый узел. Когда процедура устанавливает значение repl равным repl.LeftChild, она автоматически соединяет родителя самого правого узла с левым дочерним узлом самого правого узла (узлом 5). Программа TreeSort использует эти процедуры для работы с упорядоченными двоичными деревьями. Введите целое число, и нажмите на кнопку Add, чтобы добавить элемент к дереву. Введите целое число, и нажмите на кнопку Remove, чтобы удалить этот элемент из дерева. После удаления узла, дерево автоматически переупорядочивается для сохранения порядка «меньше». Обход упорядоченных деревьев Полезное свойство упорядоченных деревьев состоит в том, что их порядок совпадает с порядком симметричного обхода. Например, при симметричном обходе дерева, показанного на рис. 6.20, обращение к узлам происходит в порядке 2-4-5-6-7-8-9. @Рис. 6.20. Симметричный обход упорядоченного дерева: 2, 4, 5, 6, 7, 8, 9 =========139 Это свойство симметричного обхода упорядоченных деревьев приводит к простому алгоритму сортировки: 1. Добавить элемент к упорядоченному дереву. 2. Вывести элементы, используя симметричный обход. Этот алгоритм обычно работает достаточно хорошо. Тем не менее, если добавлять элементы к дереву в определенном порядке, то дерево может стать высоким и тонким. На рис. 6.21 показано упорядоченное дерево, которое получается при добавлении к нему элементов в порядке 1, 6, 5, 2, 3, 4. Другие последовательности также могут приводить к появлению высоких и тонких деревьев. Чем выше становится упорядоченное дерево, тем больше времени требуется для добавления новых элементов в нижнюю часть дерева. В наихудшем случае, после добавления N элементов, дерево будет иметь высоту порядка O(N). Полное время вставки всех элементов в дерево будет при этом порядка O(N2). Поскольку для обхода дерева требуется время порядка O(N), полное время сортировки чисел с использованием дерева будет равно O(N2)+O(N)=O(N2). Если дерево остается достаточно коротким, оно имеет высоту порядка O(log(N)). В этом случае для вставки элемента в дерево потребуется всего порядка O(log(N)) шагов. Вставка всех N элементов в дерево потребует порядка O(N * log(N)) шагов. Тогда сортировка элементов при помощи дерева потребует времени порядка O(N * log(N)) + O(N) = O(N * log(N)). Время выполнения порядка O(N * log(N)) намного меньше, чем O(N2). Например, построение высокого и тонкого дерева, содержащего 1000 элементов, потребует выполнения около миллиона шагов. Построение короткого дерева с высотой порядка O(log(N)) займет всего около 10.000 шагов. Если элементы первоначально расположены в случайном порядке, форма дерева будет представлять что-то среднее между этими двумя крайними случаями. Хотя его высота может оказаться несколько больше, чем log(N), оно, скорее всего, не будет слишком тонким и высоким, поэтому алгоритм сортировки будет выполняться достаточно быстро. @Рис. 6.21. Дерево, полученное добавлением элементов в порядке 1, 6, 5, 2, 3, 4 ==========140 В 7 главе описываются способы балансировки деревьев, для того, чтобы они не становились слишком высокими и тонкими, независимо от того, в каком порядке в них добавляются новые элементы. Тем не менее, эти методы достаточно сложны, и их не имеет смысла применять в алгоритме сортировки при помощи дерева. Многие из алгоритмов сортировки, описанных в 9 главе, более просты в реализации и обеспечивают при этом лучшую производительность. Деревья со ссылками Во 2 главе показано, как добавление ссылок к связным спискам позволяет упростить вывод элементов в разном порядке. Вы можете использовать тот же подход для упрощения обращения к узлам дерева в различном порядке. Например, помещая ссылки в листья двоичного дерева, вы можете облегчить выполнение симметричного и обратного обходов. Для упорядоченного дерева, это обход в прямом и обратном порядке сортировки. Для создания ссылок, указатели на предыдущий и следующий узлы в порядке симметричного обхода помещаются в неиспользуемых указателях на дочерние узлы. Если не используется указатель на левого потомка, то ссылка записывается на его место, указывая на предыдущий узел при симметричном обходе. Если не используется указатель на правого потомка, то ссылка записывается на его место, указывая на следующий узел при симметричном обходе. Поскольку ссылки симметричны, и ссылки левых потомков указывают на предыдущие, а правых — на следующие узлы, этот тип деревьев называется деревом с симметричными ссылками (symmetrically threaded tree). На рис. 6.22 показано дерево с симметричными ссылками, которые обозначены пунктирными линиями. Поскольку ссылки занимают место указателей на дочерние узлы дерева, нужно как-то различать ссылки и обычные указатели на потомков. Проще всего добавить к узлам новые переменные HasLeftChild и HasRightChild типа Boolean, которые будут равны True, если узел имеет левого или правого потомка соответственно. Чтобы использовать ссылки для поиска предыдущего узла, нужно проверить указатель на левого потомка узла. Если этот указатель является ссылкой, то ссылка указывает на предыдущий узел. Если значение указателя равно Nothing, значит это первый узел дерева, и поэтому он не имеет предшественников. В противном случае, перейдем по указателю к левому дочернему узлу. Затем проследуем по указателям на правый дочерний узел потомков, до тех пор, пока не достигнем узла, в котором на месте указателя на правого потомка находится ссылка. Этот узел (а не тот, на который указывает ссылка) является предшественником исходного узла. Этот узел является самым правым в левой от исходного узла ветви дерева. Следующий код демонстрирует поиск предшественника: @Рис. 6.22. Дерево с симметричными ссылками ==========141 Private Function Predecessor(node As ThreadedNode) As ThreadedNode Dim child As ThreadedNode If node.LeftChild Is Nothing Then ' Это первый узел в порядке симметричного обхода. Set Predecessor = Nothing Else If node.HasLeftChild Then ' Это указатель на узел. ' Найти самый правый узел в левой ветви. Set child = node.LeftChild Do While child.HasRightChild Set child = child.RightChild Loop Set Predecessor = child Else ' Ссылка указывает на предшественника. Set Predecessor = node.LeftChild End If End Function Аналогично выполняется поиск следующего узла. Если указатель на правый дочерний узел является ссылкой, то она указывает на следующий узел. Если указатель имеет значение Nothing, то это последний узел дерева, поэтому он не имеет последователя. В противном случае, переходим по указателю к правому потомку узла. Затем перемещаемся по указателям дочерних узлов до тех, пор, пока очередной указатель на левый дочерний узел не окажется ссылкой. Тогда найденный узел будет следующим за исходным. Это будет самый левый узел в правой от исходного узла ветви дерева. Удобно также ввести функции для нахождения первого и последнего узлов дерева. Чтобы найти первый узел, просто проследуем по указателям на левого потомка вниз от корня до тех пор, пока не достигнем узла, значение указателя на левого потомка для которого равно Nothing. Чтобы найти последний узел, проследуем по указателям на правого потомка вниз от корня до тех пор, пока не достигнем узла, значение указателя на правого потомка для которого равно Nothing. Private Function FirstNode() As ThreadedNode Dim node As ThreadedNode Set node = Root Do While Not (node.LeftChild Is Nothing) Set node = node.LeftChild Loop Set PirstNode = node End Function Private Function LastNode() As ThreadedNode Dim node As ThreadedNode Set node = Root Do While Not (node.RightChild Is Nothing) Set node = node.RightChild Loop Set FirstNode = node End Function =========142 При помощи этих функций вы можете легко написать процедуры, которые выводят узлы дерева в прямом или обратном порядке: Private Sub Inorder() Dim node As ThreadedNode ' Найти первый узел. Set node = FirstNode() ' Вывод списка. Do While Not (node Is Nothing) Print node.Value Set node = Successor(node) Loop End Sub Private Sub PrintReverseInorder() Dim node As ThreadedNode ' Найти последний узел Set node = LastNode ' Вывод списка. Do While Not (node Is Nothing) Print node. Value Set node = Predecessor(node) Loop End Sub Процедура вывода узлов в порядке симметричного обхода, приведенная ранее в этой главе, использует рекурсию. Для устранения рекурсии вы можете использовать эти новые процедуры, которые не используют ни рекурсию, ни системный стек. Каждый указатель на дочерние узлы в дереве содержит или указатель на потомка, или ссылку на предшественника или последователя. Так как каждый узел имеет два указателя на дочерние узлы, то, если дерево имеет N узлов, то оно будет содержать 2 * N ссылок и указателей. Эти алгоритмы обхода обращаются ко всем ссылкам и указателям дерева один раз, поэтому они потребуют выполнения O(2 * N) = O(N) шагов. Можно немного ускорить выполнение этих подпрограмм, если отслеживать указатели на первый и последний узлы дерева. Тогда вам не понадобится выполнять поиск первого и последнего узлов перед тем, как вывести список узлов по порядку. Так как при этом алгоритм обращается ко всем N узлам дерева, время выполнения этого алгоритма также будет порядка O(N), но на практике он будет выполняться немного быстрее. ========143 Работа с деревьями со ссылками Для работы с деревом со ссылками, нужно, чтобы можно было добавлять и удалять узлы из дерева, сохраняя при этом его структуру. Предположим, что требуется добавить нового левого потомка узла A. Так как это место не занято, то на месте указателя на левого потомка узла A находится ссылка, которая указывает на предшественника узла A. Поскольку новый узел займет место левого потомка узла A, он станет предшественником узла A. Узел A будет последователем нового узла. Узел, который был предшественником узла A до этого, теперь становится предшественником нового узла. На рис. 6.23 показано дерево с рис. 6.22 после добавления нового узла X в качестве левого потомка узла H. Если отслеживать указатель на первый и последний узлы дерева, то требуется также проверить, не является ли теперь новый узел первым узлом дерева. Если ссылка на предшественника для нового узла имеет значение Nothing, то это новый первый узел дерева. @Рис. 6.23. Добавление узла X к дереву со ссылками =========144 Учитывая все вышеизложенное, легко написать процедуру, которая добавляет нового левого потомка к узлу. Вставка правого потомка выполняется аналогично. Private Sub AddLeftChild(parent As ThreadedNode, child As ThreadedNode) ' Предшественник родителя становится предшественником нового узла. Set child. LeftChild = parent.LeftChild child.HasLeftChild = False ' Вставить узел. Set parent.LeftChild = child parent.HasLeftChild = True ' Родитель является последователем нового узла. Set child.RightChild = parent child.HasRightChild = False ' Определить, является ли новый узел первым узлом дерева. |
|
