c++ - 将节点旋转到 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

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);
        }
    }
}

希望对您有所帮助 =)