C++平衡二叉树RL旋转代码

在C++中，平衡二叉树，如AVL树或红黑树，通常需要维护其高度平衡的性质，其中旋转操作是一种常见的调整策略。当插入或删除元素导致树失去平衡时，可能会进行左旋（LL、LR）或右旋（RR、RL）。以下是基本的左旋（LL）和右旋（RR）的伪代码示例：

// 左旋 (LL) - 针对右孩子的右儿子不平衡的情况
void leftRotate(Node* &root, Node* x) {
    Node* y = x->right; // y is the right child of x
    x->right = y->left; // Rotate to make y become root's left child

    if (y->left != NULL)
        y->left->parent = x; // Update parent pointers after rotation

    y->parent = x->parent;
    if (x->parent == NULL) // If x was the root
        root = y; // New root becomes y
    else if (x == x->parent->left) // Otherwise update grandparent's left child pointer
        x->parent->left = y;
    else
        x->parent->right = y;

    y->left = x; // Make x become y's right child
}

// 右旋 (RR) - 针对左孩子的左儿子不平衡的情况
void rightRotate(Node* &root, Node* y) {
    Node* x = y->left; // x is the left child of y
    y->left = x->right; // Rotate to make x become y's right child

    if (x->right != NULL)
        x->right->parent = y; // Update parent pointers after rotation

    x->parent = y->parent;
    if (y->parent == NULL) // If y was the root
        root = x; // New root becomes x
    else if (y == y->parent->left) // Otherwise update grandparent's left child pointer
        y->parent->left = x;
    else
        y->parent->right = x;

    x->right = y; // Make y become x's left child
}