Перекомпоновка дерева бинарного поиска

Перекомпоновка дерева бинарного поиска

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

Проблема этого вырождения заключается не в том, что дерево перестает корректно функционировать (элементы продолжают храниться в отсортированном порядке), а в том, что в данном случае эффективности древовидной структуры наносится, по сути, смертельный удар. Для идеально сбалансированного дерева (в котором все родительские узлы имеют по два дочерних узла, а все листья размещаются на одном уровне, плюс-минус один) время поиска, время вставки и время удаления соответствуют O(log(n)). Иначе говоря, если для выполнения основной операции в дереве с 1000 узлов требуется время, равное t, для ее выполнения в дереве с 1000000 узлов потребуется время равное всего лишь 2t. С другой стороны время выполнения базовых операций в вырожденном дереве пропорционально O(n), и, следовательно, для выполнения этой же операции в дереве с 1 000 000 узлов потребовалось бы время, равное 1000t.

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

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

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

Часто эти два вида поворота объединяются попарно и используются в формах так называемых спаренных двухсторонних поворотов (zig-zag) и спаренных односторонних поворотов (zig-zig). Существуют две операции спаренного двустороннего поворота и две операции спаренного одностороннего поворота. Операция спаренного двустороннего поворота состоит либо из поворота вправо, за которым следует поворот влево, либо из поворота влево, за которым следует поворот вправо, причем конечным результатом обеих операций является повышение ранга узла на два уровня. И напротив, операции спаренного одностороннего поворота состоят из двух выполняемых последовательно поворотов вправо или влево. Цель выполнения всех этих спаренных операций состоит в повышении ранга узла на два уровня.

На рис. 8.4 показана операция спаренного двустороннего поворота, которая начинается с поворота влево вокруг узла P. В результате ранг узла R повышается, а ранг узла P понижается. На следующем шаге выполняется вращение вправо вокруг узла G, в результате которого ранг узла R снова повышается, а ранг узла G понижается. Общим результатом операции спаренного двустороннего поворота будет локальная балансировка дерева.

Рисунок 8.4. Операция спаренного двустороннего поворота

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

Рисунок 8.5. Операция спаренного одностороннего поворота