Бакнелл Джулиан М.
Шрифт:
Взгляните на левый дочерний узел в дереве бинарного поиска. Что мы знаем о нем? Что ж, естественно, он имеет собственные левое и правое дочерние деревья. Он больше всех узлов в его левом дочернем дереве и меньше всех узлов в правом дочернем дереве. Более того, поскольку он является левым дочерним узлом, его родительский узел больше всех узлов в его правом дочернем дереве. Следовательно, если повернуть левый дочерний узел в позицию его родительского узла, чтобы его правое дочернее дерево стало новым левым дочерним деревом родительского узла, результирующее бинарное дерево останется допустимым. Этот поворот показан на рис. 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, учитывающий две возможности.
Два рассмотренных вида поворота реорганизуют дерево на локальном уровне, но основное свойство упорядоченности узлов дерева бинарного поиска остается неизменным. В случае выполнения поворота вправо все узлы дерева а перемещаются на один уровень ближе к корневому узлу, те, которые расположены в дереве b, остаются на том же уровне, а расположенные в дереве с, перемещаются на один уровень вниз. При выполнении поворота влево все узлы дерева а перемещаются на один уровень дальше от корневого узла, узлы дерева b остаются на том же уровне, а узлы дерева с перемещаются на один уровень вверх. Несложно догадаться, что, управляя некоторым общим алгоритмом балансировки, с помощью последовательности этих двух поворотов можно было бы восстановить баланс в дереве бинарного поиска.