紅黑樹核心操作詳解：左旋與右旋算法實現

概述

二叉搜尋樹 (BST) 退化為鏈表時查詢效率降為 O(n)。紅黑樹 (Red-Black Tree) 作為一種自平衡二叉搜尋樹，透過「旋轉」與「重新著色」維持近似平衡，保證查詢、插入、刪除均為 O(log n)。C++ STL std::map、std::set 底層皆採用紅黑樹。

旋轉是紅黑樹調整結構的核心原語，分為左旋與右旋，兩者互為逆操作。

左旋

場景與目標

將節點 x 向左旋轉，使其右子節點 y 升為父節點，x 降為 y 的左子節點。y 原左子樹 (y->left) 成為 x 的新右子樹。

前提：x->right != NULL。

算法步驟 (順序嚴謹，不可顛倒)

1. 取 y = x->right。
2. 將 y->left 掛到 x->right (處理 y 原左子樹)。
3. 找 x 的父節點 px。
4. 將 y 掛到 px 相應位置 (若 px==NULL 則 y 成為新根)。
5. 將 x 設為 y->left，完成旋轉。

C++ 實現代碼

// 節點結構假設包含 pLeft, pRight, item 等成員
// parent(x, head) 為查找父節點輔助函數
// root 為指向樹根的全域/類成員指標

void left_rotate(NODE *head, NODE *x)
{
    if (x->pRight != NULL)
    {
        NODE *y = x->pRight;          // 1. 目標節點
        if (y->pLeft != NULL)         // 2. 轉移 y 的左子樹
            x->pRight = y->pLeft;

        NODE *px = parent(x, head);   // 3. 找父節點

        if (px == NULL)               // 4. 掛接到父節點或更新根
            root = y;
        else if (px->pLeft == x)
            px->pLeft = y;
        else
            px->pRight = y;

        y->pLeft = x;                 // 5. 完成旋轉
    }
    else
    {
        printf("節點 %ld 無右子，無法左旋！\n", x->item);
    }
}

右旋

邏輯鏡像對稱：將 y 向右旋，x = y->left 升為父節點。

C++ 實現代碼

void right_rotate(NODE *head, NODE *y)
{
    if (y->pLeft != NULL)
    {
        NODE *x = y->pLeft;
        if (x->pRight != NULL)
            y->pLeft = x->pRight;

        NODE *py = parent(y, head);

        if (py == NULL)
            root = x;
        else if (py->pLeft == y)
            py->pLeft = x;
        else
            py->pRight = x;

        x->pRight = y;
    }
    else
    {
        printf("節點 %ld 無左子，無法右旋！\n", y->item);
    }
}

輔助函數：查找父節點

遞歸遍歷樹查找目標節點的父節點。

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

        if (head->pLeft != NULL)
        {
            result = parent(pNode, head->pLeft);
            if (result != NULL) return result;
        }
        if (head->pRight != NULL)
        {
            result = parent(pNode, head->pRight);
            if (result != NULL) return result;
        }
    }
    return NULL; // 未找到
}

關鍵總結

• 指標操作順序至關重要：先處理子樹轉移，再處理父節點連接，最後建立新父子關係。順序錯誤會導致記憶體洩漏或斷鏈。
• 根節點特判：旋轉節點為根時，需更新樹根指標 root。
• 旋轉不改變中序遍歷序列：僅調整樹高結構，保持 BST 性質。

掌握旋轉，即掌握了紅黑樹、AVL樹等所有平衡樹的結構調整核心。