|
VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования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 Квадродеревья Квадродеревья (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 показано несколько АВЛ-деревьев. Хотя АВЛ-дерево может быть несколько выше, чем полное дерево с тем же числом узлов, оно также имеет высоту порядка O(log(N)). Это означает, что поиск узла в АВЛ-дереве занимает время порядка O(log(N)), что достаточно быстро. Не столь очевидно, что можно вставить или удалить элемент из АВЛ- дерева за время порядка O(log(N)), сохраняя при этом порядок дерева. ======156 @Рис. 7.2. АВЛ-деревья Процедура, которая вставляет в дерево новый узел, рекурсивно спускается вниз по дереву, чтобы найти местоположение узла. После вставки элемента, происходят возвраты из рекурсивных вызовов процедуры и обратный проход вверх по дереву. При каждом возврате из процедуры, она проверяет, сохраняется ли все еще свойство АВЛ-деревьев на верхнем уровне. Этот тип обратной рекурсии, когда процедура выполняет важные действия при выходе из цепочки рекурсивных вызовов, называется восходящей (bottom-up) рекурсией. При обратном проходе вверх по дереву, процедура также проверяет, не изменилась ли высота поддерева, с которым она работает. Если процедура доходит до точки, в которой высота поддерева не изменилась, то высота следующих поддеревьев также не могла измениться. В этом случае, снова требуется балансировка дерева, и процедура может закончить проверку. Например, дерево слева на рис. 7.3 является сбалансированным АВЛ-деревом. Если добавить к дереву новый узел E, то получится среднее дерево на рисунке. Затем выполняется проход вверх по дереву от нового узла E. В самом узле E дерево сбалансировано, так как оба его поддерева пустые и имеют одинаковую высоту 0. В узле D дерево также сбалансировано, так как его левое поддерево пустое, и имеет поэтому высоту 0. Правое поддерево содержит единственный узел E, и поэтому его высота равна 1. Высоты поддеревьев отличаются не больше, чем на единицу, поэтому дерево сбалансировано в узле D. В узле C дерево уже не сбалансировано. Левое поддерево узла C имеет высоту 0, а правое — высоту 2. Эти поддеревья можно сбалансировать, как показано на рис. 7.3 справа, при этом узел C заменяется узлом D. Теперь поддерево с корнем в узле D содержит узлы C, D и E, и имеет высоту 2. Заметьте, что высота поддерева с корнем в узле C, которое ранее находилось в этом месте, также была равна 2 до вставки нового узла. Так как высота поддерева не изменилась, то дерево также окажется сбалансированным во всех узлах выше D. Вращения АВЛ-деревьев При вставке узла в АВЛ-дерево, в зависимости от того, в какую часть дерева добавляется узел, существует четыре варианта балансировки. Эти способы называются правым и левым вращением, и вращением влево-вправо и вправо- влево, и обозначаются R, L, LR и RL. Предположим, что в АВЛ-дерево вставляется новый узел, и теперь дерево становится несбалансированным в узле X, как показано на рис. 7.4. На рисунке изображены только узел X и два его дочерних узла, а остальные части дерева обозначены треугольниками, так как их не требуется рассматривать подробно. Новый узел может быть вставлен в любое из четырех поддеревьев узла X, изображенных в виде треугольников. Если вы вставляете узел в одно из этих поддеревьев, то для балансировки дерева потребуется выполнить соответствующее вращение. Помните, что иногда балансировка не нужна, если вставка нового узла не нарушает упорядоченность дерева. Правое вращение Вначале предположим, что новый узел вставляется в поддерево R на рис. 7.4. В этом случае не нужно изменять два правых поддерева узла X, поэтому их можно объединить, изобразив одним треугольником, как показано на рис. 7.5. Новый узел вставляется в дерево T1, при этом поддерево TA с корнем в узле A становится не менее, чем на два уровня выше, чем поддерево T3. На самом деле, поскольку до вставки нового узла дерево было АВЛ-деревом, то TA должно было быть выше поддерева T3 не больше, чем на один уровень. После вставки одного узла TA должно быть выше поддерева T3 ровно на два уровня. Также известно, что поддерево T1 выше поддерева T2 не больше, чем на один уровень. Иначе узел X не был бы самым нижним узлом с несбалансированными поддеревьями. Если бы T1 было на два уровня выше, чем T2, то дерево было бы несбалансированным в узле A. @Рис. 7.4. Анализ несбалансированного АВЛ-дерева ========158 @Рис. 7.5. Вставка нового узла в поддерево R В этом случае, можно переупорядочить узлы при помощи правого вращения (right rotation), как показано на рис. 7.6. Это вращение называется правым, так как узлы A и X как бы вращаются вправо. Заметим, что это вращение сохраняет порядок «меньше» расположения узлов дерева. При симметричном обходе любого из таких деревьев обращение ко всем поддеревьям и узлам дерева происходит в порядке T1, A, T2, X, T3. Поскольку симметричный обход обоих деревьев происходит одинаково, то и порядок расположения элементов в них будет одинаковым. Важно также заметить, что высота поддерева, с которым мы работаем, остается неизменной. Перед тем, как был вставлен новый узел, высота поддерева была равна высоте поддерева T2 плюс 2. После вставки узла и выполнения правого вращения, высота поддерева также остается равной высоте поддерева T2 плюс 2. Все части дерева, лежащие ниже узла X при этом также остаются сбалансированными, поэтому не требуется продолжать балансировку дерева дальше. Левое вращение Левое вращение (left rotation) выполняется аналогично правому. Оно используется, если новый узел вставляется в поддерево L, показанное на рис. 7.4. На рис. 7.7 показано АВЛ-дерево до и после левого вращения. @Рис. 7.6. Правое вращение ========159 @Рис. 7.7. До и после левого вращения Вращение влево-вправо Если узел вставляется в поддерево LR, показанное на рис. 7.4, нужно рассмотреть еще один нижележащий уровень. На рис. 7.8. показано дерево, в котором новый узел вставляется в левую часть T2 поддерева LR. Так же легко можно вставить узел в правое поддерево T3. В обоих случаях, поддеревья TA и TC останутся АВЛ-поддеревьями, но поддерево TX уже не будет таковым. Так как дерево до вставки узла было АВЛ-деревом, то TA было выше T4 не больше, чем на один уровень. Поскольку добавлен только один узел, то TA вырастет только на один уровень. Это значит, что TA теперь будет точно на два уровня выше T4. Также известно, что поддерево T2 не более, чем на один уровень выше, чем T3. Иначе TC не было бы сбалансированным, и узел X не был бы самым нижним в дереве узлом с несбалансированными поддеревьями. Поддерево T1 должно иметь ту же глубину, что и T3. Если бы оно было короче, то поддерево TA было бы не сбалансировано, что снова противоречит предположению о том, что узел X — самый нижний узел в дереве, имеющий несбалансированные поддеревья. Если бы поддерево T1 имело большую глубину, чем T3, то глубина поддерева T1 была бы на 2 уровня больше, чем глубина поддерева T4. В этом случае дерево было бы несбалансированным до вставки в него нового узла. Все это означает, что нижние части деревьев выглядят в точности так, как показано на рис. 7.8. Поддерево T2 имеет наибольшую глубину, глубина T1 и T3 на один уровень меньше, а T4 расположено еще на один уровень выше, чем T3 и T3. @Рис. 7.8. Вставка нового узла в поддерево LR ==========160 @Рис. 7.9. Вращение влево-вправо Используя эти факты, можно сбалансировать дерево, как показано на рис. 7.9. Это называется вращением влево-вправо (left-right rotation), так как при этом вначале узлы A и C как бы вращаются влево, а затем узлы C и X вращаются вправо. Как и другие вращения, вращение этого типа не изменяет порядок элементов в дереве. При симметричном обходе дерева до и после вращения обращение к узлам и поддеревьям происходит в порядке: T1, A, T2, C, T3, X, T4. Высота дерево после балансировки также не меняется. До вставки нового узла, правое поддерево имело высоту поддерева T1 плюс 2. После балансировки дерева, высота этого поддерева снова будет равна высоте T1 плюс 2. Это значит, что остальная часть дерева также остается сбалансированной, и нет необходимости продолжать балансировку дальше. Вращение вправо-влево Вращение вправо-влево (right-left rotation) аналогично вращению влево- вправо (). Оно используется для балансировки дерева после вставки узла в поддерево RL на рис. 7.4. На рис. 7.10 показано АВЛ-дерево до и после вращения вправо-влево. Резюме На рис. 7.11 показаны все возможные вращения АВЛ-дерева. Все они сохраняют порядок симметричного обхода дерева, и высота дерева при этом всегда остается неизменной. После вставки нового элемента и выполнения соответствующего вращения, дерево снова оказывается сбалансированным. Вставка узлов на языке Visual Basic Перед тем, как перейти к обсуждению удаления узлов из АВЛ-деревьев, в этом разделе обсуждаются некоторые детали реализации вставки узла в АВЛ-дерево на языке Visual Basic. Кроме обычных полей LeftChild и RightChild, класс AVLNode содержит также поле Balance, которое указывает, которое из поддеревьев узла выше. Его значение равно -1, если левое поддерево выше, 1 — если выше правое, и 0 — если оба поддерева имеют одинаковую высоту. ======161 @Рис. 7.10. До и после вращения вправо-влево Public LeftChild As AVLNode Public RightChild As AVLNode Public Balance As Integer Чтобы сделать код более простым для чтения, можно использовать постоянные LEFT_HEAVY, RIGHT_HEAVY, и BALANCED для представления этих значений. Global Const LEFT_HEAVY = -1 Global Const BALANCED = 0 Global Const RIGHT_HEAVY = 1 Процедура InsertItem, представленная ниже, рекурсивно спускается вниз по дереву в поиске нового местоположения элемента. Когда она доходит до нижнего уровня дерева, она создает новый узел и вставляет его в дерево. Затем процедура InsertItem использует восходящую рекурсию для балансировки дерева. При выходе из рекурсивных вызовов процедуры, она движется назад по дереву. При каждом возврате из процедуры, она устанавливает параметр has_grown, чтобы определить, увеличилась ли высота поддерева, которое она покидает. В экземпляре процедуры InsertItem, который вызвал этот рекурсивный вызов, процедура использует этот параметр для определения того, является ли проверяемое дерево несбалансированным. Если это так, то процедура применяет для балансировки дерева соответствующее вращение. Предположим, что процедура в настоящий момент обращается к узлу X. Допустим, что она перед этим обращалась к правому поддереву снизу от узла X и что параметр has_grown равен true, означая, что правое поддерево увеличилось. Если поддеревья узла X до этого имели одинаковую высоту, тогда правое поддерево станет теперь выше левого. В этой точке дерево сбалансировано, но поддерево с корнем в узле X выросло, так как выросло его правое поддерево. Если левое поддерево узла X вначале было выше, чем правое, то левое и правое поддеревья теперь будут иметь одинаковую высоту. Высота поддерева с корнем в узле X не изменилась — она по-прежнему равна высоте левого поддерева плюс 1. В этом случае процедура InsertItem установит значение переменной has_grown равным false, показывая, что дерево сбалансировано. ========162 @Рис. 7.11 Различные вращения АВЛ-дерева ======163 В конце концов, если правое поддерево узла X было первоначально выше левого, то вставка нового узла делает дерево несбалансированным в узле X. Процедура InsertItem вызывает подпрограмму RebalanceRigthGrew для балансировки дерева. Процедура RebalanceRigthGrew выполняет левое вращение или вращение вправо-влево, в зависимости от ситуации. Если новый элемент вставляется в левое поддерево, то подпрограмма InsertItem выполняет аналогичную процедуру. Public Sub InsertItem(node As AVLNode, parent As AVLNode, _ txt As String, has_grown As Boolean) Dim child As AVLNode ' Если это нижний уровень дерева, поместить ' в родителя указатель на новый узел. If parent Is Nothing Then Set parent = node parent.Balance = BALANCED has_grown = True Exit Sub End If ' Продолжить с левым и правым поддеревьями. If txt node.Box.Caption Then Set child = node.RightChild DeleteItem child, txt, shrunk Set node.RightChild = child If shrunk Then RebalanceRightShrunk node, shrunk Else Set target = node If target.RightChild Is Nothing Then ' Потомков нет или есть только правый. Set node = target.LeftChild shrunk = True ElseIf target.LeftChild Is Nothing Then ' Есть только правый потомок. Set node = target.RightChild shrunk = True Else ' Есть два потомка. Set child = target.LeftChild ReplaceRightmost child, shrunk, target Set target.LeftChild = child If shrunk Then RebalanceLeftShrunk node, shrunk End If End If End Sub Private Sub ReplaceRightmost(repl As AVLNode, shrunk As Boolean, target As AVLNode) Dim child As AVLNode If repl.RightChild Is Nothing Then target.Box.Caption = repl.Box.Caption Set target = repl Set repl = repl.LeftChild shrunk = True Else Set child = repl.RightChild ReplaceRightmost child, shrunk, target Set repl.RightChild = child If shrunk Then RebalanceRightShrunk repl, shrunk End If End Sub Private Sub RebalanceRightShrunk(node As AVLNode, shrunk As Boolean) Dim child As AVLNode Dim child_bal As Integer Dim grandchild As AVLNode Dim grandchild_bal As Integer If node.Balance = RIGHT_HEAVY Then ' Правая часть перевешивала, теперь баланс восстановлен. node.Balance = BALANCED ElseIf node.Balance = BALANCED Then ' Было сбалансировано, теперь перевешивает левая часть. node.Balance = LEFT_HEAVY shrunk = False Else ' Левая часть перевешивала, теперь не сбалансировано. Set child = node.LeftChild child_bal = child.Balance If child_bal = SkillLevel Then best_value = VALUE_UNKNOWN Exit Sub End If ' Если игра завершается, то результат известен. pl = Winner() If pl <> PLAYER_NONE Then ' Преобразовать вес для победителя pl в вес для игрока pl1. If pl = pl1 Then best_value = VALUE_WIN ElseIf pl = pl2 Then best_value = VALUE_LOSE Else best_value = VALUE_DRAW End If Exit Sub End If ' Проверить все допустимые ходы. good_i = -1 good_value = VALUE_HIGH For i = 1 To NUM_SQUARES ' Проверить ход, если он разрешен правилами. If Board(i) = PLAYER_NONE Then ' Найти вес полученного положения для противника. If ShowTrials Then _ MoveLabel.Caption = _ MoveLabel.Caption & Format$(i) ' Сделать ход. Board(i) = pl1 BoardValue enemy_i, enemy_value, pl2, pl1, Depth + 1 ' Отменить ход. Board(i) = PLAYER_NONE If ShowTrials Then _ MoveLabel.Caption = _ Left$(MoveLabel.Caption, Depth) ' Меньше ли этот вес, чем предыдущий. If enemy_value < good_value Then good_i = i good_value = enemy_value ' Если мы выигрываем, то лучшего решения нет, ' поэтому выбирается этот ход. If good_value MaxItem Then For i = 0 To MaxItem best_solution(i) = test_solution(i) best_profit = test_profit best_cost = test_cost Next i Exit Sub End If ' Иначе перейти по ветви вниз по ветвям потомка. ' Вначале попытаться добавить эту позицию. Убедиться, ' что она не превышает ограничение по цене. If test_cost + Items(item_num).Cost best_profit Then BranchAndBound item_num + 1 unassigned_profit = unassigned_profit + Items(item_num).Profit End Sub Программа BandB использует метод полного перебора и метод ветвей и границ для решения задачи о формировании портфеля. Введите максимальную и минимальную стоимость и цену, которые вы хотите присвоить позициям, а также число позиций, которое требуется создать. Затем нажмите на кнопку Randomize (Рандомизировать), чтобы создать список позиций. Затем при помощи переключателя внизу формы выберите либо Exhaustive Search (Полный перебор), либо Branch and Bound (Метод ветвей и границ). Когда вы нажмете на кнопку Go (Начать), то программа найдет наилучшее решение при помощи выбранного метода. Затем она выведет на экран это решение, а также число узлов в полном дереве решений и число узлов, которые программа в действительности проверила. На рис. 8.7 показано окно программы BindB после решения задачи портфеля для 20 позиций. Перед тем, как выполнить полный перебор для 20 позиций, попробуйте вначале запустить примеры меньшего размера. На компьютере с процессором Pentium с тактовой частотой 90 МГц поиск решения задачи портфеля для 20 позиций методом полного перебора занял более 30 секунд. |
|
