小代碼 向原文學習 對AVL樹的4種情況 用字母標記整理

   /******************
 環境：http://anycodes.cn/zh/
 AVL  有高度標簽  
 紅黑樹 更有顏色標記
 http://blog.csdn.net/whucyl/article/details/17289841
 我們總是以ABC 3個結點為例子 插入元素后C總是不平衡的
 LL RR 較為簡單   交換后C還是出于下方
 LR RL 統一的一句就是  C總提出交換子樹，要翻身做了老大。
 LL LR與 RR RL是對稱的4種情況寫了前2種就能寫出后2種
 ******************/
 #ifndef HEAD_H_
#define HEAD_H_

#include <stdio.h>
#include <stdlib.h>
#define N 15
typedef int ElementType;
typedef struct AvlNode              // AVL樹的節點
{
	ElementType data;
	struct AvlNode *left;           // 左孩子
	struct AvlNode *right;          // 右孩子
	int Height;
}*Position,*AvlTree;

AvlTree MakeEmpty(AvlTree T);
Position Find(ElementType x,AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree  Insert(ElementType x,AvlTree T);
AvlTree  Delete(ElementType x,AvlTree T);
ElementType Retrieve(Position P);
void Display(AvlTree T);

#endif /* HEAD_H_ */
 
/*
 *   初始化AVL樹
 */
AvlTree MakeEmpty(AvlTree T)
{
	if( T != NULL)
	{
		MakeEmpty(T->left);
		MakeEmpty(T->right);
		free(T);
	}
	return NULL;
}

/*
 * 查找 可以像普通二叉查找樹一樣的進行，所以耗費O(log n)時間，因為AVL樹總是保持平衡的。
 * 不需要特殊的準備，樹的結構不會由于查找而改變。（這是與伸展樹查找相對立的，它會因為查找而變更樹結構。）
 */
Position Find(ElementType x,AvlTree T)
{
	if(T == NULL)		return NULL;
	if(x < T->data)		return Find(x,T->left);
	else if(x > T->data)return Find(x,T->right);
	else            	return  T;/*/遞歸中左走走 右走走 要么找不到要么返回找到的T結點/*/
}
/*
 *   FindMax，FindMin 查找最大和最小值，
 *   沒有特別的   這個就遞歸或循環找到最右下角和最左下即可
 */
Position FindMin(AvlTree T)
{
	if(T == NULL)	        return NULL;
	if( T->left == NULL)	return T;
	else            		return FindMin(T->left);
}
Position FindMax(AvlTree T)
{
	if(T != NULL)    
	{
	 while(T->right != NULL) T=T->right;   
	}
	return T;
}
/*
 *  返回節點的高度
 */
static int Height(Position P)
{
	if(P == NULL)	return -1;
	else     		return P->Height;
}
static int Max(int h2,int h3)
{
	return h2 > h3 ?h2:h3;
}
/*
 *  此函數用于k2只有一個左孩子的單旋轉，
 *  在K2和它的左孩子之間旋轉，
 *  更新高度，返回新的根節點
    frist：     
             K2
         K1    K2R
     K1L  K1R     
    then：
              K1   
        K1L       K2
              K1R      K2R
 
 */
 
static Position SingleRotateWithLeft(Position k2)    /*/ LL旋轉/*/
{
	Position k1;
	k1=k2->left;
	k2->left=k1->right;
	k1->right=k2;
	/*/ 因為比較的是左右孩子的高度，所以求父節點的高度要加1/*/
	k2->Height=Max(Height(k2->left),Height(k2->right)) + 1;
	k1->Height=Max(Height(k1->left),Height(k2->right)) + 1;
	return k1;
}
/*
 *  此函數用于k1只有一個右孩子的單旋轉，
 *  在K1和它的右孩子之間旋轉，
 *  更新高度，返回新的根節點
 frist：
             K1   
        K1L       K2
              K2L      K2R
 then：
                  K2
              K1      K2R
       K1L       K2L
 
 */
static Position SingleRotateWithRight(Position k1)  /*/ RR旋轉/*/
{
	Position k2;
	k2=k1->right;
	k1->right=k2->left;
	k2->left=k1;
	 /*結點的位置變了, 要更新結點的高度值*/
	k1->Height=Max(Height(k1->left),Height(k1->right)) + 1;
	k2->Height=Max(Height(k2->left),Height(k2->right)) + 1;
	return k2;
}
/*
 * 此函數用于當 如果 k3有一個左孩子，以及
 * 它的左孩子又有右孩子，執行這個雙旋轉
 * 更新高度，返回新的根節點
   first：
               K1
       K2             K1R
K2L         K3       
        K3L     K3R
   then：
                   K3
          K2                K1
K2L           K3L      K3R         K1R
 */
static Position DoubleRotateLeft(Position k3)    /*/ LR旋轉/*/
{
	/*/在 k3 的左孩子，執行右側單旋轉/*/
	k3->left=SingleRotateWithRight(k3->left);/*/ RR旋轉/*/
	/*/ 再對 k3 進行 左側單旋轉/*/
	return SingleRotateWithLeft(k3);         /*/ LL旋轉/*/
}
/*
 * 此函數用于當 如果 k4有一個右孩子，以及
 * 它的右孩子又有左孩子，執行這個雙旋轉
 * 更新高度，返回新的根節點
   first：
                K1
          K1L      K2
                K4   K2R
             k4L  K4R
   then：
                   K4
          K1                K2
K1L           K4L      K4R         K2R
 
 
 */
static Position DoubleRotateRight(Position k4)    /*/ RL旋轉/*/
{
	/*/在 k4 的右孩子，執行左側單旋轉/*/
	k4->right = SingleRotateWithLeft(k4->right);
	/*/ 再對 k4 進行 右側單旋轉/*/
	return SingleRotateWithRight(k4);
}
/*
 *  向AVL樹插入可以通過如同它是未平衡的二叉查找樹一樣把給定的值插入樹中，
 *  接著自底向上向根節點折回，于在插入期間成為不平衡的所有節點上進行旋轉來完成。
 *  因為折回到根節點的路途上最多有1.5乘log n個節點，而每次AVL旋轉都耗費恒定的時間，
 *  插入處理在整體上耗費O(log n) 時間。
 
                            X < CUR                         X > CUR
                       T                                       T
                     X   X                                   X   X 
                  LL    LR                              RL           RR
 */
 
 /*/4種基本的交換子樹方式 寫好后  以下進入重點/*/
AvlTree  Insert(ElementType x,AvlTree T)
{
	/*/如果T不存在，則創建一個節點樹/*/
	if(T == NULL)
	{
		T = (AvlTree)malloc(sizeof(struct AvlNode));
		{
			T->data = x;
			T->Height = 0;
			T->left = T->right = NULL;
		}
	}
	/*/ 如果要插入的元素小于當前元素/*/
	else if(x < T->data)
	{
		/*/遞歸插入/*/
		T->left=Insert(x,T->left);
		/*/插入元素之后，若 T 的左子樹比右子樹高度 之差是 2，即不滿足 AVL平衡特性，需要調整/*/
		if(Height(T->left) - Height(T->right) == 2)
		{
			/*/把x插入到了T->left的左側，只需 左側單旋轉/*/
			if(x < T->left->data)
				T = SingleRotateWithLeft(T);       /*/ LL旋轉/*/
			else
				/*/ x 插入到了T->left的右側，需要左側雙旋轉/*/
				T =  DoubleRotateLeft(T);          // LR旋轉/*/
		}
	}
/*/ 如果要插入的元素大于當前元素/*/
	else if(x > T->data)
	{
		T->right=Insert(x,T->right);
		if(Height(T->right) - Height(T->left) == 2)
		{
			if(x > T->right->data)
				T = SingleRotateWithRight(T);     /*/RR 旋轉/*/
			else
				T =  DoubleRotateRight(T);        /*/RL旋轉/*/
		}
	}
	T->Height=Max(Height(T->left),Height(T->right)) + 1;
	return T;
}
/*
 *  對單個節點進行的AVL調整
                              T
                      TL              TR
                  TLL   TLR         
                 X        
             1.LL          2.LR
                               
                              T
                      TL              TR
                                   TLL   TLR         
                                            X        
                                3.RL          4.RR
                
 
 */
AvlTree Rotate(AvlTree T)
{

	if(Height(T->left) - Height(T->right) == 2)
	{
		if(Height(T->left->left) >= Height(T->left->right))
			T = SingleRotateWithLeft(T);  /*/LL旋轉/*/
		else
			T =  DoubleRotateLeft(T);     /*/ LR旋轉/*/
	}
	if(Height(T->right) - Height(T->left) == 2)
	{
		if(Height(T->right->right) >= Height(T->right->left))
			T = SingleRotateWithRight(T);  /*/ RR旋轉/*/
		else
			T =  DoubleRotateRight(T);     /*/ RL旋轉/*/
	}
	return T;
}
/*
 * 首先定位要刪除的節點，然后用該節點的右孩子的最左孩子替換該節點，
 * 并重新調整以該節點為根的子樹為AVL樹，具體調整方法跟插入數據類似
 * 刪除處理在整體上耗費O(log n) 時間。
 */
AvlTree  Delete(ElementType x,AvlTree T)
{
	if(T == NULL)	return NULL;
	if(T->data == x)           /*/要刪除的 x 等于當前節點元素/*/
	{
		if(T->right == NULL )  /*/ 若所要刪除的節點 T 的右孩子為空,則直接刪除/*/
		{
			AvlTree tmp = T;
			T = T->left;
			free(tmp);
		}
		else                 /* 否則找到 T->right 的最左兒子代替 T */
		{
			AvlTree tmp = T->right;
			while(tmp->left)
				tmp=tmp->left;
			T->data = tmp->data;
			/* 對于替代后的T 即其字節點進行調整*/
			T->right = Delete(T->data,T->right);
			T->Height = Max(Height(T->left),Height(T->right))+1;
		}
		return T;
	}
	else if(x > T->data)                       /*/要刪除的 x 大于當前節點元素，在T的右子樹中查找刪除/*/
	{
		T->right=Delete(x,T->right);
	}
	else                                       /*/ 要刪除的 x 小于當前節點元素，在T的左子樹中查找刪除/*/
	{
		T->left=Delete(x,T->left);
	}
	/*
	 *   當刪除元素后調整平衡
	 */
	T->Height=Max(Height(T->left),Height(T->right)) + 1;
	if(T->left != NULL)
		T->left = Rotate(T->left);
	if(T->right != NULL)
		T->right = Rotate(T->right);
	if(T)
		T=Rotate(T);
	return T;
}
/*
 * 返回當前位置的元素
 */
ElementType Retrieve(Position P)
{
	return P->data;
}
/*
 * 遍歷輸出
 LDR 中序遍歷
 */
void Display(AvlTree T)
{
	static int n=0;
	if(NULL != T)
	{
		Display(T->left);
		printf("[%d] ndata=%d \n",++n,T->data);
		Display(T->right);
	}
}
 void PointAsTree(AvlTree T,int lay)
 {
     if(T)
     {
         PointAsTree(T->right,lay+1);
         for(int i=0;i<lay;i++) printf("** ");printf("%d \n",T->data);
         PointAsTree(T->left,lay+1);
     }
 }

int main()
{
    AvlTree T=NULL;
    int i;
    int j = 0;
    T = MakeEmpty( NULL );puts("數據準備 \n");
    for( i = 0; i < N; i++, j = ( j + 7 ) % 50)
    {/*插入15個數 */
    	printf("j=%d  ",j);
        T = Insert( j, T );
    }
    puts("插入 4 \n");
    T = Insert( 4, T );
    //printf("中序遍歷\n");
    //Display(T);
     
    PointAsTree(T,4);
   printf("刪除偶數值\n");
   for( i = 0; i < N; i += 2 )
   {
	   printf("delelte: %d \n",i);
        T = Delete( i, T );
   }
   printf("height=%d \n",T->Height);
   //printf("中序遍歷\n");
   
   //Display(T);
   
    PointAsTree(T,4);
puts("[1] ndata=0 中[]數字僅用于展現遞歸調用多少次\n");
    printf( "Min is %d, Max is %d\n", Retrieve( FindMin( T ) ),
    Retrieve( FindMax( T ) ) );
	return EXIT_SUCCESS;
}