紅黑樹系列之旋轉

(1)概述
         二叉樹是使用非常廣泛的數據結構，但如果是常規的插入，會導致二叉樹的高度過高和出現整棵樹不平衡的情況。紅黑樹是一種平衡二叉樹，C++STL中的set,map及其擴展容器內部的數據結構都是紅黑樹。
(2)左旋轉
         比如說，需要把x旋轉為y的左結點。整個算法的思路非常清晰：從上至下，先得到y指針，講x的右指針指向y的左結點，然後利用parent函數得到x的父親結點，如果為NULL，則y為新的根，如果不為NULL，則根據x是其父親的左孩子還是右孩子，將指針指向y。最後將y的左指針指向x，完成旋轉。值得注意的是，算法是具有順序的邏輯步驟，不能夠調換順序，如果改變賦值的順序會造成內存失去指針指向，出現內存錯誤。
       代碼：注：parent為求父親結點的函數，root是始終指向根結點內存區域的指針。
[cpp]
//左旋轉，假設x->pRight!=NULL 
void left_rotate(NODE *head,NODE *x)//head是根結點，x是待左旋轉的結點 
{ 
    if(x->pRight!=NULL) 
    { 
        NODE *y=x->pRight; 
        if(y->pLeft!=NULL) 
            x->pRight=y->pLeft; 
        NODE *px=parent(x,head); 
        if(px==NULL)//如果x是根結點，那麼就把y置為根結點 
            root=y; 
        else if(px->pLeft==x) 
            px->pLeft=y; 
        else 
            px->pRight=y; 
        y->pLeft=x; 
    } 
    else 
        printf("item為%ld的結點不能夠進行左旋轉！",x->item); 
} 
 
(3)右旋轉
        方法與左旋轉基本相同，只是方向相反，不再贅述其過程。
        代碼：
[cpp]
//右旋轉，假設y->pLeft!=NULL    
void right_rotate(NODE *head,NODE *y)//head是根結點，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("item為%ld的結點不能夠進行右旋轉！",y->item); 
} 
 
[cpp]
//返回父親結點 
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 result;//沒有找到，返回NULL 
} 
        總結：旋轉的算法思路非常清晰，整個邏輯思考是重點

摘自 博觀約取,厚積薄發