Преобразование лозы в сбалансированное двоичное дерево.

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

Пусть есть лоза, которая состоит из 2ⁿ-1 вершин для какого-либо натурального n. Для примера возьмем n=4, тогда лоза будет содержать 15 вершин. Преобразуем данную лозу в сбалансированное дерево за три операции перестроения.

На первой операции пройдем по лозе сверху вниз, начиная в корне, и раскрасим каждую вершину соответственно в серый или черный цвет (условимся, что корень будет серого цвета). Затем возьмем каждую серую вершину, кроме самой нижней, сделаем ее правым ребенком черной вершины, являющейся ее левым ребенком. Т.е. выполним малый правый поворот относительно каждой серой вершины, кроме самой нижней (на рисунке приведен пример малого правого поворота относительно вершины X).

Таким образом, вместо лозы, состоящей из 15 вершин, мы получим дерево, состоящее из 7 черных вершин и 8 серых вершин.

Для второго перестроения сначала перекрасим серые вершины в белые. Далее перекрасим каждую вторую черную вершину в серый цвет, начиная в корне. Теперь, как и раньше, выполним малый правый поворот относительно каждой серой вершины, кроме самой нижней.

Третье перестроение аналогично первым двум. Вершины 12 и 4 перекрашиваются в серый цвет, затем выполняется малый правый поворот относительно вершины 12. В результате получается сбалансированное дерево.

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

Пусть лоза состоит из m вершин. Тогда существует такое n, что (2ⁿ-1) < m < (2ⁿ⁺¹-1). Необходимо укоротить главную лозу на m - (2ⁿ-1) вершин. После этого можно перестроить получившееся дерево аналогично способу, описанному выше. В результате получится сбалансированное дерево с m - (2ⁿ-1) листьями.

Для примера разберем случай, когда лоза состоит из 9 вершин. Отсюда следует, что n=3, т.к. (2³-1)=7<9<15=(2⁴-1). Следовательно, необходимо укоротить главную лозу на 9-(2³-1)=2. После этого перестраиваем дерево аналогично примеру, приведенному выше. В результате у нас должно получиться сбалансированное дерево.