0

所以我有我的功能来在 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);

}

并说我找到了一个要旋转到树根的节点。我将如何编写一个函数来做到这一点？

4

1 回答 1

1

注意：以下代码根本没有经过测试。这也说明了这些想法。代码一直在底部。

假设：

  • 节点没有父链接，非根节点无法判断它是其父节点的左孩子还是右孩子。否则，算法可以稍微简化。
  • 一个节点有一个左链接和一个右链接，这从您的代码中可以看出。
  • 该算法没有考虑最终的树是否平衡。如果您需要平衡，那么您可以停止阅读此答案，您可能想查看 Splay Trees：http ://en.wikipedia.org/wiki/Splay_tree

我将假设您通过某种搜索例程获得一个节点。现在，想法是，简单地维护：

  1. 您在搜索中看到的一堆节点
  2. 搜索中遍历的链接方向

例如，给定这棵树：

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

我们搜索了 key 19，它在树里面。现在，我们要一直旋转 19 到顶部。

NodeStack，从栈底到栈顶的一堆节点：[15, 35, 28, 19]<--栈顶

DirStack, 遍历的链接方向栈：[RIGHT, LEFT, LEFT]<--栈顶

我们假设搜索点击这里。所以我们应该做的第一件事是检索 的最顶层元素NodeStack，也就是我们要旋转到顶部的节点。在这种情况下，它是具有 key 的节点19。在这一步之后，两个堆栈看起来像：

NodeStack: [15, 35, 28]<-- 栈顶

DirStack: [RIGHT, LEFT, LEFT]<-- 栈顶

接下来，主循环运行直到DirStack为空。我们从两个堆栈中弹出一个元素。弹出的元素NodeStack是我们希望旋转到顶部的节点的父节点，弹出的元素DirStack表示从我们刚刚弹出的节点到未来根节点的链接方向。

在循环的第一次迭代中，我们有节点28和链接方向LEFT，因此节点19是节点的左孩子28。

不难看出，我们应该与我们刚刚弹出的方向相反旋转，所以如果方向是，我们应该向左旋转父节点，如果方向是RIGHT，我们应该向右旋转父节点LEFT。由于这里的方向是，我们向右LEFT旋转父节点。这可以通过调用node 上的函数来实现。28 rotate_with_left_child28

树变成

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

注意它28变成了一个正确的孩子，因此这是一个正确的旋转。我很确定这是正确的术语。由于维基百科现在已经关闭，我无法验证这一点，但这个问题表明我使用了正确的术语：

解释二叉树旋转的代码（左或右）

现在的堆栈状态：

NodeStack: [15, 35]<-- 栈顶

DirStack: [RIGHT, LEFT]<-- 栈顶

堆栈不是空的，所以我们从两个堆栈中弹出35和。我们使用 node 上的rotate_with_left_child函数LEFT执行右旋转，得到这棵树：35

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

我们的节点现在更接近成为根节点。现在堆叠：

NodeStack：[15]

DirStack：[RIGHT]

我们弹出节点15和方向RIGHT。现在，我们使用node 上的函数执行左旋转，我们得到了这棵最终的树：rotate_with_right_child15

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

塔达！我们现在完成了。这是代码，使用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);
        }
    }
}

希望有帮助=)

于 2013-11-07T03:13:11.553 回答