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

Полные деревья обладают рядом важных свойств. Во‑первых, это кратчайшие деревья, которые могут содержать заданное число узлов. Например, двоичное дерево на рис. 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 <= NumNodes Then Preorder node * 2 + 1

    ' Второй потомок.

    If node * 2 + 2 <= NumNodes Then Preorder node * 2 + 2

End Sub

Private Sub Inorder(node As Integer)

    ' Первый потомок.

    If node * 2 + 1 <= NumNodes Then Inorder node * 2 + 1

    Print NodeLabel (node)               ' Узел.

    ' Второй потомок.

    If node * 2 + 2 <= NumNodes Then Inorder node * 2 + 2

End Sub

Private Sub Postorder(node As Integer)

    ' Первый потомок.

    If node * 2 + 1 <= NumNodes Then Postorder node * 2 + 1

    ' Второй потомок.

    If node * 2 + 2 <= NumNodes Then Postorder node * 2 + 2

    Print NodeLabel (node)               ' Узел.

End Sub

Private Sub BreadthFirstPrint()

Dim i As Integer

    For i = 0 To NumNodes

        Print NodeLabel(i)

    Next i

End Sub

======130

Программа Trav1 демонстрирует прямой, симметричный и обратный обходы, а также обход в ширину для двоичных деревьев на основе массивов. Введите высоту дерева, и нажмите на кнопку Create Tree (Создать дерево) для создания полного двоичного дерева. Затем нажмите на кнопки Preorder (Прямой обход), Inorder (Симметричный обход), Postorder (Обратный обход) или Breadth-First (Обход в ширину) для того, чтобы увидеть, как происходит обход дерева. На рис. 6.13 показано окно программы, в котором отображается прямой обход дерева 4 порядка.

Прямой и обратный обход для других представлений дерева осуществляется так же просто. Следующий код демонстрирует процедуру прямого обхода для дерева, записанного в формате с нумерацией связей:

Private Sub PreorderPrint(node As Integer)

Dim link As Integer

    Print NodeLabel(node)

    For link = FirstLink(node) To FirstLink(node + 1) - 1

        PreorderPrint ToNode (link)

    Next link

End Sub

@Рис. 6.13. Пример прямого обхода дерева в программе Trav1

=======131

Как упоминалось ранее, сложно дать определение симметричного обхода для деревьев больше 2 порядка. Тем не менее, после того, как вы поймете, что имеется в виду под симметричным обходом, реализовать его достаточно просто. Следующий код демонстрирует процедуру симметричного обхода, которая обращается к половине потомков узла (с округлением в большую сторону), затем к самому узлу, а потом — к остальным потомкам.

Private Sub InorderPrint(node As Integer)

Dim mid_link As Integer

Dim link As Integer

    ' Найти средний дочерний узел.

    mid_link - (FirstLink(node + 1) - 1 + FirstLink(node)) \ 2

    ' Обход первой группы потомков.

    For link = FirstLink(node) To mid_link

        InorderPrint ToNode(link)

    Next link

    ' Обращение к узлу.

    Print NodeLabel(node)

    ' Обход второй группы потомков.

    For link = mid_link + 1 To FirstLink(node + 1) - 1

        InorderPrint ToNode(link)

    Next link

End Sub

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

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

Dim Root As TreeNode

' Инициализация дерева.

    :

Private Sub BreadthFirstPrint(}

Dim queue As New Collection ' Очередь на основе коллекций.

Dim node As TreeNode

Dim child As TreeNode

    ' Начать с корня дерева в очереди.

    queue.Add Root

    ' Многократная обработка первого элемента

    ' в очереди, пока очередь не опустеет.

    Do While queue.Count > 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.LeftChild

        InsertItem child, new_value

        Set node.LeftChild = child

    Else

        ' Перейти по правой ветви.

        Set child = node.RightChild

        InsertItem child, new_value

        Set node.RightChild = child

    End If

End Sub

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

Когда процедура InsertItem рекурсивно вызывает сама себя, она передает указатель на дочерний узел в дереве. Например, в следующих операторах процедура передает указатель на правого потомка узла в качестве параметра узла процедуры InsertItem. Если вызываемая процедура изменяет значение параметра узла, указатель на потомка также автоматически обновляется в вызывающей процедуре. Затем в последней строке кода значение правого потомка устанавливается равным новому значению, так что созданный новый узел добавляется к дереву.

Set child = node.RightChild

Insertltem child, new_value

Set node.RightChild = child

Удаление элементов

Удаление элемента из упорядоченного дерева немного сложнее, чем его вставка. После удаления элемента, программе может понадобиться переупорядочить другие узлы, чтобы соотношение «меньше» продолжало выполняться для всего дерева. При этом нужно рассмотреть несколько случаев.

=====134-135

@Рис. 6.17. Удаление узла с единственным потомком

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

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

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

Чтобы решить эту проблему, удаленный узел заменяется самым правым узлом из левой ветви. Другими словами, нужно сдвинуться на один шаг вниз по левой ветви, выходившей из удаленного узла. Затем нужно двигаться по правым ветвям вниз до тех пор, пока не найдется узел, который не имеет правой ветви. Это самый правый узел на ветви слева от удаляемого узла. В дереве, показанном слева на рис. 6.18, узел 3 является самым правым узлом в левой от узла 4 ветви. Можно заменить узел 4 листом 3, сохранив при этом порядок дерева.

@Рис. 6.18. Удаление узла, который имеет два дочерних

=======136

@Рис. 6.19. Удаление узла, если заменяющий его узел имеет потомка

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

Эта сложная ситуация показана на рис. 6.19. В этом примере удаляется узел 8. Самый правый элемент в его левой ветви — это узел 7, который имеет потомка — узел 5. Чтобы сохранить порядок дерева после удаления узла 8, заменим узел 8 узлом 7, а узел 7 — узлом 5. Заметьте, что узел 7 получает новых потомков, а узел 5 сохраняет своих.

Следующий код удаляет узел из упорядоченного двоичного дерева:

Private Sub DeleteItem(node As SortNode, target_value As Integer)

Dim target As SortNode

Dim child As SortNode

    ' Если узел не найден, вывести сообщение.

    If node Is Nothing Then

        Beep

        MsgBox "Item " & Format$(target_value) & _

           " не найден в дереве."

        Exit Sub

    End If

    If target_value < node.Value Then

        ' Продолжить для левого поддерева.

        Set child = node.LeftChild

        DeleteItem child, target_value

        Set node.LeftChild = child

    ElseIf target_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 главе, более просты в реализации и обеспечивают при этом лучшую производительность.

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