Фундаментальные алгоритмы и структуры данных в Delphi

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

Вспомните, что в дереве бинарного поиска все узлы в левом дочернем дереве данного узла меньше, а узлы в правом дочернем дереве больше его. (Естественно, под тем, что один узел меньше другого, подразумевается, что ключ элемента в одном узле меньше ключа элемента в другом узле. Просто проще написать, что "один узел меньше другого", нежели постоянно ссылаться на ключи узлов.) Немного проанализируем эту аксиому.

Взгляните на левый дочерний узел в дереве бинарного поиска. Что мы знаем о нем? Что ж, естественно, он имеет собственные левое и правое дочерние деревья. Он больше всех узлов в его левом дочернем дереве и меньше всех узлов в правом дочернем дереве. Более того, поскольку он является левым дочерним узлом, его родительский узел больше всех узлов в его правом дочернем дереве. Следовательно, если повернуть левый дочерний узел в позицию его родительского узла, чтобы его правое дочернее дерево стало новым левым дочерним деревом родительского узла, результирующее бинарное дерево останется допустимым. Этот поворот показан на рис. 8.3. На этом рисунке треугольники представляют дочерние деревья, которые содержат ноль или больше узлов - для алгоритма поворота точное их количество роли не играет.

Рисунок 8.3. Повышение ранга левого дочернего узла (и наоборот)

Для исходного дерева можно было бы записать следующее неравенство: (а < L < b) < P < с. Для нового дерева имеем: a< L< (b< P< c), что, конечно же, остается справедливым и при удалении круглых скобок, поскольку операция < подчиняется коммуникативному закону. (первое неравенство читается следующим образом: все узлы в дереве а меньше узла L, который меньше всех узлов в дереве b, а все это дерево в целом меньше узла P, который, в свою очередь, меньше всех узлов в дереве с. Подобным же образом можно интерпретировать и второе неравенство.)

Только что рассмотренную операцию называют поворотом вправо (right rotation). При этом говорят, что ранг левого дочернего узла L повышается, а ранг родительского узла P понижается. Иначе говоря, узел L перемещается на один уровень вверх, а узел P - на один уровень вниз. Такой поворот называется поворотом вокруг узла P.

Естественно, рассмотрев поворот вправо, легко предположить, как выполняется другой поворот, поворот влево (left rotation), который создал бы первое дерево из второго. Поворот влево повышает ранг правого дочернего узла P и понижает ранг родительского узла L. Код выполнения обеих видов поворота приведен в листинге 8.17, при этом кодирование выполняется с точки зрения того узла, ранг которого повышается.

Листинг 8.17. Повышение ранга узла

function TtdSplayTree.stPromote(aNode : PtdBinTreeNode): PtdBinTreeNode;

var

Parent : PtdBinTreeNode;

begin

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

Parent := aNode^.btParent;

{в обеих случаях необходимо разорвать и перестроить шесть связей: связь узла с его дочерним узлом и противоположную связь, связь узла с его родительским узлом и противоположную связь и связь родительского узла с его родительским узлом и противоположную связь; обратите внимание, что дочерний узел данного узла может быть пустым}

{повысить ранг левого дочернего узла, т.е. выполнить поворот родительского узла вправо}

if (Parent^.btChild[ctLeft] = aNode) then begin

Parent^.btChild[ctLeft] := aNode^.btChild[ctRight];

if (Parent^.btChild[ctLeft] <> nil) then

Parent^.btChild[ctLeft]^.btParent := Parent;

aNode^.btParent := Parent^.btParent;

if (aNode^.btParent^.btChild[ctLeft] = Parent) then

aNode^.btParent^.btChild[ctLeft] := anode else

aNode^.btParent^.btChild[ctRight] := aNode;

aNode^.btChild[ctRight] := Parent;

Parent^.btParent := aNode;

end

{повысить ранг правого дочернего узла, т.е. выполнить поворот родительского узла влево}

else begin

Parent^.btChild[ctRight] := aNode^.btChild[ctLeft];

if (Parent^.btChild[ ctRight ] <> nil) then

Parent^.btChild[ctRight]^.btParent := Parent;

aNode^.btParent := Parent^.btParent;

if (aNode^.btParent^.btChild[ctLeft] = Parent) then

aNode^.btParent^.btChild[ctLeft] := anode else

aNode^.btParent^.btChild[ctRight] := aNode/ aNode^.btChild[ctLeft] := Parent;

Parent^.btParent := aNode;

end;

{вернуть узел, ранг которого был повышен}

Result := aNode;

end;

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