マホガニーシリーズの回転

(1)概要 
         二叉樹は非常に広いデータ構造を使用していますが、通常の挿入であれば、二叉樹の高さが高すぎて、ツリー全体がアンバランスになることがあります.赤と黒の木は、バランスのとれた二叉の木で、C＋＋STLのセット、mapおよび拡張容器内部のデータ構造はすべて赤と黒の木です.
(2)左回転
         例えば、xをyの左結点に回転させる必要があります.全体のアルゴリズムの考えは非常に明確である:上から下までyポインタを得て、xの右のポインタはyの左の結点を指して、その後parent関数を利用してxの父の結点を得て、NULLであれば、yは新しい根であり、NULLでなければ、xは父の左の子供か右の子供かによって、ポインタをyに向ける.最後にyの左ポインタをxに向けて回転を完了します.なお、アルゴリズムは順序を持つ論理ステップであり、順序を変えることができず、賦値の順序を変えるとメモリがポインタを失ってメモリエラーが発生する.
       コード:注:parentは父の結点の関数を求めて、rootは常にルートの結点メモリ領域を指す指針です.

//   ，  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)右回転
        方法は左回転と基本的に同じであるが、方向が反対であるだけで、そのプロセスについてはもはや説明しない.
        コード:

//   ，  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);

}

//      

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

}

総括:回転のアルゴリズムの考え方はとてもはっきりしていて、全体のロジックの思考は重点です.