Rotate Node To Root Of BST

Question

So I have my functions to rotate my nodes in a 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);

}

and say I found a node that I want to rotate to the root of the tree. How would I go about writing a function to do this?

Answer 1

NOTE: Following code is not tested at all. It's just too illustrate the ideas. Code is all the way at the bottom.

Assumptions:

• Nodes have no parent link, and a non-root node cannot tell whether it is the left child or right child of its parent. Otherwise, the algorithm can be slightly simplified.
• A node has a left link and a right link, which is evident from your code.
• This algorithm does not take into account of whether the final tree is balanced. If you require it to be balanced, then you can stop reading this answer and you might want to look at Splay Trees: http://en.wikipedia.org/wiki/Splay_tree

I will assume that you obtain a node by some kind of search routine. Now, the idea is, simply maintain:

1. a stack of the nodes you have seen on the search
2. direction of the links traversed in the search

For example, given this tree:

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

and we searched for the key 19, which is inside the tree. Now, we want to rotate 19 all the way to the top.

NodeStack, a stack of nodes from bottom of stack to top: [15, 35, 28, 19] <-- top of stack

DirStack, a stack of link directions traversed: [RIGHT, LEFT, LEFT] <-- top of stack

We are assuming as search hit here. So the first thing we should do is to retrieve the topmost element of NodeStack, which is the node we want to rotate to the top. In this case, it is the node with key 19. After this step, both stacks look like:

NodeStack: [15, 35, 28] <-- top of stack

DirStack: [RIGHT, LEFT, LEFT] <-- top of stack

Next, the main loop runs until DirStack is empty. We pop one element from both stacks. The element popped from NodeStack is the parent of the node we wish to rotate to the top, and the element popped from DirStack indicates the direction of the link from the node we just popped to the future root node.

At the first iteration of the loop, we have the node 28 and link direction LEFT, so node 19 is the left child of node 28.

It should not be hard to see that we should rotate opposite to the direction that we just popped, so we should rotate the parent node left if the direction is RIGHT, and rotate the parent node right if the direction is LEFT. Since the direction here is LEFT, we rotate the parent node 28 right. This can be achieved by calling the rotate_with_left_child function on node 28.

The tree becomes

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

notice that 28 becomes a right child, hence this is a right rotation. I'm pretty sure this is the correct terminology. As wikipedia is down right now, I cannot verify this, but this question shows that I'm using the correct terminology:

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

State of the stacks now:

NodeStack: [15, 35] <-- top of stack

DirStack: [RIGHT, LEFT] <-- top of stack

The stacks are not empty, so we pop 35 and LEFT from the two stacks. We perform a right rotation using the rotate_with_left_child function on the node 35, to get this tree:

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

Our node is now closer to becoming root. Stacks now:

NodeStack: [15]

DirStack: [RIGHT]

We pop node 15 and direction RIGHT. Now, we perform a left rotation using the rotate_with_right_child function on node 15, and we obtain this final tree:

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

Tadah! We are now done. Here's the code, using std::stack from 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);
        }
    }
}

Hope that helps =)