紅黑樹系列之旋轉操作詳解：左旋、右旋與父節點查找實現

概述

紅黑樹是自平衡二叉搜索樹，C++ STL set/map 底層即紅黑樹。普通 BST 插入易退化成鏈表，旋轉操作是維持平衡的核心。

左旋

將節點 x 旋轉為其右子 y 的左孩子。步驤順序嚴格不可亂：

1. 獲取 y = x->right。
2. x->right = y->left（若 y->left 存在）。
3. 找 x 的父節點 px，將 px 對應子指針指向 y（或更新根）。
4. y->left = x。

代碼實現

void left_rotate(NODE *head, NODE *x) {
    if (!x->pRight) { printf("Node %ld cannot left rotate!\n", x->item); return; }
    NODE *y = x->pRight;
    if (y->pLeft) x->pRight = y->pLeft;
    NODE *px = parent(x, head);
    if (!px) root = y;
    else if (px->pLeft == x) px->pLeft = y;
    else px->pRight = y;
    y->pLeft = x;
}

右旋

鏡像操作，將 y 旋轉為其左子 x 的右孩子。

代碼實現

void right_rotate(NODE *head, NODE *y) {
    if (!y->pLeft) { printf("Node %ld cannot right rotate!\n", y->item); return; }
    NODE *x = y->pLeft;
    if (x->pRight) y->pLeft = x->pRight;
    NODE *py = parent(y, head);
    if (!py) root = x;
    else if (py->pLeft == y) py->pLeft = x;
    else py->pRight = x;
    x->pRight = y;
}

父節點查找

遞歸查找，找到即返回，避免繼續搜索。

NODE *parent(NODE *pNode, NODE *head) {
    if (!head) return NULL;
    if (head->pLeft == pNode || head->pRight == pNode) return head;
    NODE *res = NULL;
    if (head->pLeft) {
        res = parent(pNode, head->pLeft);
        if (res) return res;
    }
    if (head->pRight) {
        res = parent(pNode, head->pRight);
        if (res) return res;
    }
    return NULL;
}

總結

旋轉邏輯清晰，關鍵在於指針修改順序：先處理子樹接管，再更新父節點指向，最後建立新父子關係。順序錯誤會導致內存斷鏈。

摘自 博觀約取,厚積薄發