(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
}
總結：旋轉的算法思路非常清晰，整個邏輯思考是重點
摘自 博觀約取,厚積薄發
