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

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

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

чем при полном переборе. Дерево решений для задачи портфеля с 20 позициями

содержит 2.097.151 узел. При полном переборе придется проверить их все, при

поиске методом ветвей и границ понадобится проверить только примерно 1.500

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