使用 void 在 BST 中向右旋转

Question

我没有实现 AVL 树，但我需要创建一个将二叉搜索树向右旋转的方法，但是，我使用了以下代码，但解决方案不起作用。

如何实现包括旋转根节点和非根节点的旋转右方法？


void BST<T>::rotate_right(Node* node)
{
    //Node * current = node;
    Node * move_up_node = node->left;
    
    if(node == nullptr || move_up_node == nullptr)
    {
       return;
    }
    else
    {
       node->left = move_up_node->right;        
       if(node->left != nullptr)
       {
           node->left->parent = node;
       }
        //set parent edge
       move_up_node->parent = node->parent;
                   
       if(node == root_)
       {
           root_ = move_up_node;
       }
       
       else if(node == node->parent->right)
       {
           node->parent->right = move_up_node;
       }
       else if (node == node->parent->left)
       {
           node->parent->left = move_up_node;
       }
        
       node->parent = move_up_node;
       move_up_node->right = node;
        //node = move_up_node;
    }
    
    // Correct height of ancestors of node
     fix_height(root_);
}

旋转节点输入为21 当我输出它时，它什么也没做。

在我测试函数之前，输出是

 10 Height: 5
   R├──42 Height: 4
    |  R├──91 Height: 3
    |   |  L└──49 Height: 2
    |   |     R└──70 Height: 1
    |   |      |  R├──77 Height: 0
    |   |      |  L└──54 Height: 0
    |  L└──21 Height: 0
   L└──1 Height: 2
      R└──7 Height: 1
       |  L└──2 Height: 0

我测试了一下，结果是

rotate node: 21
 10 Height: 5
   R├──42 Height: 4
    |  R├──91 Height: 3
    |   |  L└──49 Height: 2
    |   |     R└──70 Height: 1
    |   |      |  R├──77 Height: 0
    |   |      |  L└──54 Height: 0
    |  L└──21 Height: 0
   L└──1 Height: 2
      R└──7 Height: 1
       |  L└──2 Height: 0

Answer 1

外部 else 块中存在这些问题：

move_up_node->parent->right = node是不对的，因为move_up_node是node->left，所以move_up_node->parent是node，这意味着你实际上设置 node->right = node，这会创建一个循环。你真正想要的是 node->left->parent = node
if(node == node->parent->right) 如果不先验证 node 是否有父项，则不安全。所以把它设为 else if.
node->right = move_up_node 是不对的（顾名思义，它不会移动那个节点 up）。应该是node->parent->right = move_up_node。下一个块出现同样的错误。

这是对外部 else 块的更正：

        // Set edge between node and its current inner grandchild:
        node->left = move_up_node->right;
        if (node->left != nullptr) {
            node->left->parent = node;  // <---
        }
        // Set edge between parent of node and the node that moves up
        move_up_node->parent = node->parent;
        if(node == root_)
        {
            root_ = move_up_node;
        }
        else if(node == node->parent->right)  // <-- else!
        {
            node->parent->right = move_up_node; // <--
        }
        else // <-- no need for another `if`
        {
            node->parent->left = move_up_node; // <--
        }
        // Set edge between node and move_up_node (was OK):
        node->parent = move_up_node;
        move_up_node->right = node;

使用 void 在 BST 中向右旋转

Rotate right in a BST using void

c++

rotation

binary-search-tree

void