java - 红黑树 - 如果根是祖 parent ，如何轮换？

Question

我正在自己编写红黑树。但是当我测试涉及旋转根的旋转时，它有点失去引用。

树结构:

          45             
        /    \
      40x      70        
     /  \     /
    7   41   50           
   / \
  6  39

旋转逻辑说:“以 45(root) 为顶部旋转，沿提高 X 的方向(即 40)”

所以这意味着向右旋转，结果应该是这样的:

     40x  
    /   \
   7     45
 / \     / \
 6  39  41  70
           /
          50

假设节点 45 是祖父节点，7 是父节点，41 是当前节点。 (我知道这个顺序没有意义但是请忽略，这是因为我已经轮换了一次)

代码:

  //current is node 45
    //parent is node 7
    //grandparent is node 45 (root)

    //first detach cross node (i.e. 41)
    Node crossNode2 = grandparent.left.right;
    grandparent.left.right = null; //detach


                   45             
                /     \
              40x      70        
             /  \      /
            7   null   50           
           / \
          6  39

    grandparent.left = null;




                   45             
                 /    \
               null   70        
                      /
                    50           

    current.right = grandparent;

          40
        /    \
      7        45
     /  \     /  \
   6    39   null 70
                  /
                 50

    grandparent.left = crossNode2; //attach


         40  
        /   \
       7     45
     / \     / \
     6  39  41  70
               /
              50

但不知何故这段代码不起作用。当我测试时:

preorder
45, 39, 70, 50
breadth-first
45, 39, 70, 50

所以我认为结果实际上是:

  45
 /  \
39  70
     /
    50

谁能告诉我轮换代码有什么问题？

Answer 1

在节点Q上做右旋转的步骤:

1. 令 P = Q 的左 child 。
2. Q的左 child =P的右 child
3. P 取代 Q 作为其父级的子级
4. P的右 child =Q

您在提供的代码中遗漏了加粗的步骤。我认为您的问题是您将涉及根节点的旋转视为特例。显然，如果 Q 是根并且其父级是 null，则您不能这样做。尝试创建一个“头”节点，右节点是根节点。这允许涉及根的旋转使用正常算法工作。

public static void rotateRight(Node node) {
    assert(!node.isLeaf() && !node.left.isLeaf());
    final Node child = node.left;
    node.setLeft(child.right);
    if (node.isRightChild())
         node.parent.setRight(child);
    else node.parent.setLeft(child);
    child.setRight(node);
}

setRight 和 setLeft 保持 parent 引用更新以及更新 right 和 的节点左边。 node.isRightNode() 调用可以只是 (node.parent.right == node)。