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

Предположим, что удаляемый узел является левым потомком своего родителя.

Его указатель на левого потомка является ссылкой, указывающей на предыдущий

узел в дереве. После удаления узла, его предшественник становится

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

заменяем указатель на левого потомка его родителя на указатель на левого

потомка удаляемого узла.

Указатель на правого потомка удаляемого узла является ссылкой, которая

указывает на следующий узел в дереве. Так как удаляемый узел является левым

потомком своего родителя, и поскольку у него нет потомков, эта ссылка

указывает на родителя, поэтому ее можно просто опустить. На рис. 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

Квадродеревья

Квадродеревья (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 new_dist Then

best_dist = new_dist

Set best_item = new_item

End If

Next new_item

End Sub

======147-148

Элемент, который находит процедура NearPointLeaf, обычно и есть элемент,

который пользователь пытался выбрать. Тем не менее, если элемент находится

вблизи границы между двумя узлами, может оказаться, что ближайший к

выбранной точке элемент находится в другом узле.

Предположим, что Dmin — это расстояние между выбранной пользователем точкой

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

чем расстояние от выбранной точки до края листа, то поиск закончен.

Населенный пункт находится при этом слишком далеко от края листа, чтобы в

каком-либо другом листе мог существовать пункт, расположенный ближе к

заданной точке.

В противном случае нужно снова начать с корня и двигаться по дереву,

проверяя все узлы квадродеревьев, которые находятся на расстоянии меньше,

чем Dmin от заданной точки. Если найдутся элементы, которые расположены

ближе, изменим значение Dmin и продолжим поиск. После завершения проверки

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

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

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

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 элементов перед тем, как найти нужный.

Изменение MAX_PER_NODE

Интересно поэкспериментировать с программой Qtree, изменяя значение

MAX_PER_NODE, определенное в разделе Declarations класса QtreeNode. Это

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

без его разбиения. Программа обычно использует значение MAX_PER_NODE = 100.

======151

@Рис. 6.26. Программа Qtree

Если вы уменьшите это число, например, до 10, то в каждом узле будет

находиться меньше элементов, поэтому программа будет проверять меньше

элементов, чтобы найти ближайший к выбранной вами точке. Поиск будет

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

больше узлов квадродерева, поэтому она займет больше памяти.

Наоборот, если вы увеличите MAX_PER_NODE до 1000, программа создаст намного

меньше узлов. При этом потребуется больше времени на поиск элементов, но

дерево будет меньше, и займет меньше памяти.

Это пример компромисса между временем и пространством. Использование

большего числа узлов квадродерева ускоряет поиск, но занимает больше

памяти. В этом примере, при значении переменной MAX_PER_NODE примерно

равном 100, достигается равновесие между скоростью и использованием памяти.

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

различными значениями переменной MAX_PER_NODE, чтобы найти оптимальное.

Использование псевдоуказателей в квадродеревьях

Программа Qtree использует большое число классов и коллекций. Каждый

внутренний узел квадродерева содержит четыре ссылки на дочерние узлы.

Листья включают большие коллекции, в которых находятся элементы узла. Все

эти объекты и коллекции замедляют работу программы, если она содержит

большое числе элементов. Создание объектов отнимает много времени и памяти.

Если программа создает множество объектов, она может начать обращаться к

файлу подкачки, что сильно замедлит ее работу.

К сожалению, выигрыш от использования квадродеревьев будет максимальным,

если программа содержит много элементов. Чтобы улучшить производительность

больших приложений, вы можете использовать методы работы с

псевдоуказателями, описанные во 2 главе.

=====152

Программа Qtree2 создает квадродерево при помощи псевдоуказателей. Узлы и

элементы находятся в массивах определенных пользователем структур данных. В

качестве указателей, эта программа использует индексы массивов вместо

ссылок на объекты. В одном из тестов на компьютере с процессором Pentium с

тактовой частотой 90 МГц, программе Qtree потребовалось 25 секунд для

построения квадродерева, содержащего 30.000 элементов. Программе Qtree2

понадобилось всего 3 секунды для создания того же дерева.

Восьмеричные деревья

Восьмеричные деревья (octtrees) аналогичны квадродеревьям, но они разбивают

область не двумерного, а трехмерного пространства. Восьмеричные деревья

содержат не четыре потомка, как квадродеревья, а восемь, разбивая объем

области на восемь частей — верхнюю северо-западную, нижнюю северо-западную,

верхнюю северо-восточную, нижнюю северо-восточную и так далее.

Восьмеричные деревья полезны при работе с объектами, расположенными в

пространстве. Например, робот может использовать восьмеричное дерево для

отслеживания близлежащих объектов. Программа рейтрейсинга может

использовать восьмеричное дерево для того, чтобы быстро оценить, проходит

ли луч поблизости от объекта перед тем, как начать медленный процесс

вычислений точного пересечения объекта и луча.

Восьмеричные деревья можно строить, используя примерно те же методы, что и

для квадродеревьев.

Резюме

Существует множество способов представления деревьев. Наиболее эффективным

и компактным из них является запись полных деревьев в массивах.

Представление деревьев в виде коллекций дочерних узлов упрощает работу с

ними, но при этом программа выполняется медленнее и использует больше

памяти. Представление нумерацией связей позволяет быстро выполнять обход

дерева и использует меньше памяти, чем коллекции потомков, но его сложно

модифицировать. Тем не менее, его важно представлять, потому что оно часто

используется в сетевых алгоритмах.

=====153

Глава 7. Сбалансированные деревья

При работе с упорядоченным деревом, вставке и удалении узлов, дерево может

стать несбалансированным. Когда это происходит, то алгоритмы, работы с

деревом становятся менее эффективными. Если дерево становится сильно

несбалансированным, оно практически представляет всего лишь сложную форму

связного списка, и программа, использующая такое дерево, может иметь очень

низкую производительность.

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

балансировки деревьев, даже если узлы удаляются и добавляются с течением

времени. Балансировка дерева позволяет ему оставаться при этом достаточно

эффективным.

Глава начинается с описания того, что понимается под несбалансированным

деревом и демонстрации ухудшения производительности для несбалансированных

деревьев. Затем в ней обсуждаются АВЛ-деревья, высота левого и правого

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

Сохраняя это свойство АВЛ-деревьев, можно поддерживать такое дерево

сбалансированным.

Затем в главе описываются Б-деревья и Б+деревья, в которых все листья имеют

одинаковую глубину. Если число ветвей, выходящих из каждого узла находится

в определенных пределах, такие деревья остаются сбалансированными. Б-

деревья и Б+деревья обычно используются при программировании баз данных.

Последняя программа, описанная в этой главе, использует Б+дерево для

реализации простой, но достаточно мощной базы данных.

Сбалансированность дерева

Как упоминалось в 6 главе, форма упорядоченного дерева зависит от порядка

вставки в него новых узлов. На рис. 7.1 показано два различных дерева,

созданных при добавлении одних и тех же элементов в разном порядке.

Высокие и тонкие деревья, такие как левое дерево на рис. 7.1, могут иметь

глубину порядка O(N). Вставка или поиск элемента в таком несбалансированном

дереве может занимать порядка O(N) шагов. Даже если новые элементы

вставляются в дерево в случайном порядке, в среднем они дадут дерево с

глубиной N / 2, что также порядка O(N).

Предположим, что строится упорядоченное двоичное дерево, содержащее 1000

узлов. Если дерево сбалансировано, то высота дерева будет порядка

log2(1000), или примерно равна 10. Вставка нового элемента в дерево займет

всего 10 шагов. Если дерево высокое и тонкое, оно может иметь высоту 1000.

В этом случае, вставка элемента в конец дерева займет 1000 шагов.

======155

@Рис. 7.1. Деревья, построенные в различном порядке

Предположим теперь, что мы хотим добавить к дереву еще 1000 узлов. Если

дерево остается сбалансированным, то все 1000 узлов поместятся на следующем

уровне дерева. При этом для вставки новых элементов потребуется около

10 * 1000 = 10.000 шагов. Если дерево было не сбалансировано и остается

таким в процессе роста, то при вставке каждого нового элемента оно будет

становиться все выше. Вставка элементов при этом потребует порядка

1000 + 1001 + … +2000 = 1,5 миллиона шагов.

Хотя нельзя быть уверенным, что элементы будут добавляться и удаляться из

дерева в нужном порядке, можно использовать методы, которые будут

поддерживать сбалансированность дерева, независимо от порядка вставки или

удаления элементов.

АВЛ-деревья

АВЛ-деревья (AVL trees) были названы в честь русских математиков Адельсона-

Вельского и Лэндиса, которые их изобрели. Для каждого узла АВЛ-дерева,

высота левого и правого поддеревьев отличается не больше, чем на единицу.

На рис. 7.2 показано несколько АВЛ-деревьев.

Хотя АВЛ-дерево может быть несколько выше, чем полное дерево с тем же

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