Поворот узла Чтобы Корень BST

Question

Так у меня есть свои функции, чтобы повернуть мои узлы в BST:

void BST::rotate_with_left_child(BNode *&t){ 

    BNode *t1 = t->left; 
    t->left = t1->right; 
    t1->right = t; 
    t->node_height = max(height(t->left),height(t->right))+1; 
    t1->node_height = max(height(t1->left),t->node_height)+1; 
    t = t1; 

} 

void BST::double_rotate_with_left_child(BNode *&t){ 

    rotate_with_right_child(t->left); 
    rotate_with_left_child(t); 

} 

void BST::rotate_with_right_child(BNode *&t){ 

    BNode *t1 = t->right; 
    t->right = t1->left; 
    t1->left = t; 
    t->node_height = max(height(t->right),height(t->left))+1; 
    t1->node_height = max(height(t1->right),t->node_height)+1; 
    t = t1; 

} 

void BST::double_rotate_with_right_child(BNode *&t){ 

    rotate_with_left_child(t->right); 
    rotate_with_right_child(t); 

} 

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

Answer 1

ПРИМЕЧАНИЕ: Следующий код не проверен вообще. Это просто иллюстрирует идеи. Код находится полностью внизу.

Предположение:

• Узлы не имеет родительскую ссылки, а не корневой узел не может сказать, является ли левым ребенком или права ребенка своего родителя. В противном случае алгоритм может быть слегка упрощен.
• Узел имеет левую ссылку и ссылку справа, что видно из вашего кода.
• Этот алгоритм не учитывает, сбалансировано ли окончательное дерево. Если вам требуется, чтобы это было сбалансировано, то вы можете перестать читать этот ответ, и вы можете захотеть взглянуть на расширяющееся дерево: http://en.wikipedia.org/wiki/Splay_tree

я буду считать, что вы получите узел по какой-то поиск рутина. Теперь эта идея, просто поддерживать:

1. стек из узлов, которые вы видели на поиск
2. направление связей, проходимых в поисках

Например, учитывая это дерево:

 
      15 
      /\ 
      2 35 
      /\ 
      28 42 
      /\ 
      19 31 

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

NodeStack, стопка узлов из нижней части стека вверх: [15, 35, 28, 19] < - вершина стека

DirStack, стопка направлениях линии проходится: [RIGHT, LEFT, LEFT] < - вершина стека

Мы предполагая, что поиск попал сюда. Итак, первое, что мы должны сделать, это получить самый верхний элемент NodeStack, который является узлом, который мы хотим повернуть вверх. В этом случае это узел с ключом 19. После этого шага, как стеки выглядеть так:

NodeStack: [15, 35, 28] < - вершина стека

DirStack: [RIGHT, LEFT, LEFT] < - вершина стека

Далее, основной цикл выполняется до тех пор, DirStack не опустеет. Мы выталкиваем один элемент из обоих стеков. Элемент, который выскочил из NodeStack, является родительским элементом узла, который мы хотим повернуть вверх, а элемент, вставленный с DirStack, указывает направление ссылки с узла, который мы только что выскочили на будущий корневой узел.

В первой итерации цикла, мы имеем узел 28 и направление линии связи LEFT, так что узел 19 является левым дочерним узлом 28.

Это не должно быть трудно понять, что мы должны вращаться против направления, которые мы только что появившегося, так что мы должны повернуть родительский узел влево, если направление RIGHT и поверните родительский узел вправо, если направление LEFT. Так как направление здесь LEFT, мы поворачиваем родительский узел 28правый. Этого можно достичь, вызвав функцию rotate_with_left_child на узле 28.

Дерево становится

 
      15 
      /\ 
      2 35 
      /\ 
      19 42 
       \ 
       28 
       \ 
       31 

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

Code with explanation for binary tree rotation (left OR right)

Состояние стопок Сейчас:

NodeStack: [15, 35] < - вершина стека

DirStack: [RIGHT, LEFT] < - вершина стека

ЗБ acks не пустые, поэтому мы выталкиваем 35 и LEFT из двух стеков. Мы выполняем правое вращение с помощью rotate_with_left_child функции на узле 35, чтобы это дерево:

 
      15 
      /\ 
      2 19 
       \ 
       35 
       /\ 
       28 42 
       \ 
       31 

Наш узел теперь ближе, чтобы стать корнем. Стеки Сейчас:

NodeStack: [15]

DirStack: [RIGHT]

Мы выскочить узел 15 и направление RIGHT. Сейчас мы проводим левое вращение с помощью функции rotate_with_right_child на узле 15, и мы получаем это последнее дерево:

 
      19 
      /\ 
      15 35 
     / /\ 
     2  28 42 
       \ 
       31 

Tadah! Теперь мы закончили. Вот код, используя std::stack от STL.

// NOTE: None of the code here is tested, so some errors are expected. 

// Used to indicate direction of links traversed during the search 
enum Direction { 
    LEFT, RIGHT 
}; 

// This function rotates the node at the top of nodeStack to the root of the tree. 
// It assumes that the nodeStack is non-empty, and that nodeStack has one more 
// element than dirStack 
// 
// nodeStack - stack of nodes encountered during search 
// dirStack - direction of links traversed during search 
void rotate_to_top(stack<BSTNode *>& nodeStack, stack<Direction>& dirStack) { 
    // remove the future root node. actually this assignment is not needed 
    // NOTE: You might also want to check if the nodeStack is empty before doing this 
    BSTNode* root = nodeStack.top(); 
    nodeStack.pop(); 

    // main loop. this is done until the dirStack is empty 
    while (!dirStack.empty()) { 
     Direction d = dirStack.top(); 
     dirStack.pop(); 
     BSTNode *par = nodeStack.top(); 
     nodeStack.top(); 
     // perform the proper rotation 
     if (d == LEFT) { 
      rotate_with_left_child(par); 
     } else { 
      rotate_with_right_child(par); 
     } 
    } 
} 

Надежда, что помогает =)