Изменение двоичного дерева поиска

Question

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

Из-за того, что элементы появляются в неуравновешенном дереве, мне кажется, что существует некоторая связь между обходным порядком (слева, по середине, справа).

Answer 1

void unbalance(Node **pp) { 
    Node *p; 
    while ((p = *pp)) { 
     if (!p->left) { 
      pp = &p->right; 
     } else { 
      Node *tmp = p->left->right; 
      *pp = p->left; 
      p->left->right = p; 
      p->left = tmp; 
     } 
    } 
} 

... 
Node *tree = ...; 
unbalance(&tree); 

Этот код основан на ответе @ templatetypedef. Он использует указатель на указатель, чтобы избежать сиротских узлов (который также избавляется от finalRoot, единственной целью которого является избегать сирот первоначального корня, переданного вызывающим).

Идея состоит в том, чтобы спуститься по дереву вдоль самой правой ветви. Если никогда не осталось детей, мы вводим только первую часть инструкции if и выходим, ничего не делая.

Часть else используется, когда имеется левое поддерево. В этом случае мы поворачиваем дерево справа.

Это приводит к вытягиванию одного узла из левого поддерева, то есть наше левое поддерево теперь на один узел меньше. Мы повторяем это до тех пор, пока левое поддерево полностью не исчезнет, ​​и в этот момент мы снова войдем в первую часть if. Затем мы переходим к остальной правой поддереве и повторяем все это.

Указатели на указатели часто полезны при изменении структуры связанного списка или дерева. Они позволяли нам работать непосредственно с оригинальными указателями, а не копировать их. В этом случае назначение *pp = ... изменяет указатель в другом месте (на который указывает pp). Это либо исходный корень (как передается вызывающим), либо один из указателей right внутри дерева (как установлено pp = &p->right). Это повторное назначение необходимо, потому что вращение дерева в ветке else перемещает узлы вокруг, поэтому то, что раньше было корнем поддерева, перемещается дальше вниз, а прежний левый узел подтягивается, чтобы стать новым корнем. Мы обновляем *pp, чтобы сохранить инвариант, указатель выше (либо переменная tree в нашем вызывающем абоненте, либо член right нашего родительского узла) указывает на (новый) корень поддерева.

Answer 2

Один из способов сделать это итеративно - использовать вращения деревьев. Идея выглядит примерно так:

1. Если корневой узел имеет левый дочерний элемент, поверните корневой узел вправо.
2. В противном случае корневой узел не имеет левого дочернего элемента. Спуститесь направо и повторите этот процесс.

В псевдокоде:

Node finalRoot = null; 
while (currNode != null) { 
    if (currNode.left != null) { 
     currNode = rotateRight(currNode); 
    } else { 
     if (finalRoot == null) finalRoot = currNode; 
     currNode = currNode.right; 
    } 
} 
return finalRoot; 

Этот подход адаптирован из алгоритма День-Стаут-Уоррен, который делает это в качестве первого шага. Он работает во времени O (n).