Когда процедура 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 главе, более просты в реализации и обеспечивают при этом лучшую производительность.
Во 2 главе показано, как добавление ссылок к связным спискам позволяет упростить вывод элементов в разном порядке. Вы можете использовать тот же подход для упрощения обращения к узлам дерева в различном порядке. Например, помещая ссылки в листья двоичного дерева, вы можете облегчить выполнение симметричного и обратного обходов. Для упорядоченного дерева, это обход в прямом и обратном порядке сортировки.
Для создания ссылок, указатели на предыдущий и следующий узлы в порядке симметричного обхода помещаются в неиспользуемых указателях на дочерние узлы. Если не используется указатель на левого потомка, то ссылка записывается на его место, указывая на предыдущий узел при симметричном обходе. Если не используется указатель на правого потомка, то ссылка записывается на его место, указывая на следующий узел при симметричном обходе. Поскольку ссылки симметричны, и ссылки левых потомков указывают на предыдущие, а правых — на следующие узлы, этот тип деревьев называется деревом с симметричными ссылками (symmetrically threaded tree). На рис. 6.22 показано дерево с симметричными ссылками, которые обозначены пунктирными линиями.