Работа с деревьями со ссылками

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

Предположим, что требуется добавить нового левого потомка узла 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

 

' Определить, является ли новый узел первым узлом дерева.

If child.LeftChild Is Nothing Then Set FirstNode = child

End Sub

 

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

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

Указатель на правого потомка удаляемого узла является ссылкой, которая указывает на следующий узел в дереве. Так как удаляемый узел является левым потомком своего родителя, и поскольку у него нет потомков, эта ссылка указывает на родителя, поэтому ее можно просто опустить. На рис. 6.24 показано дерево с рис. 6.23 после удаления узла F. Аналогично удаляется правый потомок.

 

Private Sub RemoveLeftChild(parent As ThreadedNode)

Dim target As ThreadedNode

 

Set target = parent.LeftChild

Set parent.LeftChild = target.LeftChild

End Sub

 

 

@Рис. 6.24. Удаление узла F из дерева со ссылками

 

=========145

 

Квадродеревья[RP12]

Квадродеревья (quadtrees) описывают пространственные отношения между элементами на площади. Например, это может быть карта, а элементы могут представлять собой положение домов или предприятий на ней.

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

 

' Потомки.

Public NWchild As QtreeNode

Public NEchild As QtreeNode

Public SWchild As QtreeNode

Public SEchild As QtreeNode

 

' Элементы узла, если это не лист.

Public Items As New Collection

 

Элементы, записанные в квадродереве, могут содержать пространственные данные любого типа. Они могут содержать информацию о положении, которую дерево может использовать для поиска элементов. Переменные в простом классе QtreeItem, который представляет элементы, состоящие из точек на местности, определяются так:

 

Public X As Single

Public Y As Single

 

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

На рис. 6.25 показано несколько элементов данных, расположенных в виде квадродерева. Каждая область разбивается до тех пор, пока она не будет содержать не более двух элементов.

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

 

====146

 

@Рис. 6.25. Квадродерево

 

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

Функция LocateLeaf класса QtreeNode использует этот подход для поиска листа дерева, который содержит выбранную точку. Программа может вызвать эту функцию в строке Set the_leaf = Root.LocateLeaf(X, Y, Gxmin, Gxmax, Gymax), где Gxmin, Gxmax, Gymin, Gymax — это границы представленной деревом области.

 

Public Function LocateLeaf (X As Single, Y As Single, _

xmin As Single, xmax As Single, ymin As Single, ymax As Single) _

As QtreeNode

 

Dim xmid As Single

Dim ymid As Single

Dim node As QtreeNode

 

If NWchild Is Nothing Then

   ' Узел не имеет потомков. Искомый узел найден.

   Set LocateLeaf = Me

   Exit Function

End If

 

' Найти соответстующего потомка.

xmid = (xmax + xmin) / 2

ymid = (ymax + ymin) / 2

If X <= xmid Then

   If Y <= ymid Then

      Set LocateLeaf = NWchild.LocateLeaf( _

          X, Y, xmin, xmid, ymin, ymid)

   Else

      Set LocateLeaf = SWchild.LocateLeaf _

          X, Y, xmin, xmid, ymid, ymax)

   End If

Else

   If Y <= ymid Then

      Set LocateLeaf = NEchild.LocateLeaf( _

          X, Y, xmid, xmax, ymin, ymid)

   Else

      Set LocateLeaf = SEchild.LocateLeaf( _

          X, Y, xmid, xmax, ymid, ymax)

   End If

End If

End Function

 

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

 

Public Sub NearPointInLeaf (X As Single, Y As Single, _

best_item As QtreeItem, best_dist As Single, comparisons As Long)

 

Dim new_item As QtreeItem

Dim Dx As Single

Dim Dy As Single

Dim new_dist As Single

 

' Начнем с заведомо плохого решения.

best_dist = 10000000

Set best_item = Nothing

 

' Остановиться если лист не содержит элементов.

If Items.Count < 1 Then Exit Sub

 

For Each new_item In Items

   comparisons = comparisons + 1

   Dx = new_item.X - X

   Dy = new_item.Y - Y

   new_dist =Dx * Dx + Dy * Dy

   If best_dist > new_dist Then

      best_dist = new_dist

      Set best_item = new_item

   End If

Next new_item

End Sub

 

 

======147-148

 

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

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

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

 

Public Sub CheckNearbyLeaves(exclude As QtreeNode, _

X As Single, Y As Single, best_item As QtreeItem, _

best_dist As Single, comparisons As Long, _

xmin As Single, xmax As Single, ymin As Single, ymax As Single)

 

Dim xmid As Single

Dim ymid As Single

Dim new_dist As Single

Dim new_item As QtreeItem

 

' Если это лист, который мы должны исключить,

' ничего не делать.

If Me Is exclude Then Exit Sub

 

' Если это лист, проверить его.

If SWchild Is Nothing Then

   NearPointInLeaf X, Y, new_item, new_dist, comparisons

   If best_dist > new_dist Then

      best_dist = new_dist

      Set best_item = new_item

   End If

   Exit Sub

End If

 

' Найти потомков, которые удалены не больше, чем на best_dist

' от выбранной точки.

xmid = (xmax + xmin) / 2

ymid = (ymax + ymin) / 2

If X - Sqr(best_dist) <= xmid Then

 

   ' Продолжаем с потомками на западе.

   If Y - Sqr(best_dist) <= ymid Then

      ' Проверить северо-западного потомка.

      NWchild.CheckNearbyLeaves _

          exclude, X, Y, best_item, _

          best_dist, comparisons, _

          xmin, xmid, ymin, ymid

   End If

   If Y + Sqr(best_dist) > ymid Then

      ' Проверить юго-западного потомка.

      SWchiId.CheckNearbyLeaves _

          exclude, X, Y, best_item, _

          best_dist, comparisons, _

          xmin, xmid, ymid, ymax

   End If

End If

If X + Sqr(best_dist) > xmid Then

   ' Продолжить с потомками на востоке.

   If Y - Sqr(best_dist) <= ymid Then

      ' Проверить северо-восточного потомка.

      NEchild.CheckNearbyLeaves _

          exclude, X, Y, best_item, _

          best_dist, comparisons, _

          xmid, xmax, ymin, ymid

   End If

   If Y + Sqr(best_dist) > ymid Then

      ' Проверить юговосточного потомка.

      SEchild.CheckNearbyLeaves _

          exclude, X, Y, best_item, _

          best_dist, comparisons, _

          xmid, xmax, ymid, ymax

   End If

End If

End Sub

 

 

=====149-150

 

Подпрограмма FindPoint использует подпрограммы LocateLeaf, NearPointInLeaf, и CheckNearbyLeaves, из класса QtreeNode для быстрого поиска элемента в квадродереве.

 

Function FindPoint(X As Single, Y As Single, comparisons As Long) _ As QtreeItem

 

Dim leaf As QtreeNode

Dim best_item As QtreeItem

Dim best_dist As Single

 

' Определить, в каком листе находится точка.

Set leaf = Root.LocateLeaf( _

   X, Y, Gxmin, Gxmax, Gymin, Gymax)

 

' Найти ближайшую точку в листе.

leaf.NearPointInLeaf _

   X, Y, best_item, best_dist, comparisons

 

' Проверить соседние листья.

Root.CheckNearbyLeaves _

   leaf, X, Y, best_item, best_dist, _

   comparisons, Gxmin, Gxmax, Gymin, Gymax

 

Set FindPoint = best_item

End Function

 

Программа Qtree использует квадродерево. При старте программа запрашивает число элементов данных, которое она должна создать, затем она создает элементы и рисует их в виде точек. Задавайте вначале небольшое (около 1000) число элементов, пока вы не определите, насколько быстро ваш компьютер может создавать элементы.

Интересно наблюдать квадродеревья, элементы которых распределены неравномерно, поэтому программа выбирает точки при помощи функции странного аттрактора (strange attractor) из теории хаоса (chaos theory). Хотя кажется, что элементы следуют в случайном порядке, они образуют интересные кластеры.

При выборе какой‑либо точки на форме при помощи мыши, программа Qtree находит ближайший к ней элемент. Она подсвечивает этот элемент и выводит число проверенных при его поиске элементов.

В меню Options (Опции) программы можно задать, должна ли программа использовать квадродеревья или нет. Если поставить галочку в пункте Use Quadtree (Использовать квадродерево), то программа выводит на экран квадродерево и использует его для поиска элементов. Если этот пункт не выбран, программа не отображает квадродерево и находит нужные элементы путем перебора.

Программа проверяет намного меньшее число элементов и работает намного быстрее при использовании квадродерева. Если этот эффект не слишком заметен на вашем компьютере, запустите программу, задав при старте 10.000 или 20.000 входных элементов. Вы заметите разницу даже на компьютере с процессором Pentium с тактовой частотой 90 МГц.

На рис. 6.26 показано окно программа Qtree на котором изображено 10.000 элементов. Маленький прямоугольник в верхнем правом углу обозначает выбранный элемент. Метка в верхнем левом углу показывает, что программа проверила всего 40 из 10.000 элементов перед тем, как найти нужный.