小代碼 向原文學(xué)習(xí) 對AVL樹的4種情況 用字母標(biāo)記整理

   /******************
 環(huán)境：http://anycodes.cn/zh/
 AVL  有高度標(biāo)簽  
 紅黑樹 更有顏色標(biāo)記
 http://blog.csdn.net/whucyl/article/details/17289841
 我們總是以ABC 3個結(jié)點為例子 插入元素后C總是不平衡的
 LL RR 較為簡單   交換后C還是出于下方
 LR RL 統(tǒng)一的一句就是  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樹的節(jié)點
{
	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樹總是保持平衡的。
 * 不需要特殊的準(zhǔn)備，樹的結(jié)構(gòu)不會由于查找而改變。（這是與伸展樹查找相對立的，它會因為查找而變更樹結(jié)構(gòu)。）
 */
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結(jié)點/*/
}
/*
 *   FindMax，F(xiàn)indMin 查找最大和最小值，
 *   沒有特別的   這個就遞歸或循環(huán)找到最右下角和最左下即可
 */
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;
}
/*
 *  返回節(jié)點的高度
 */
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;
}
/*
 *  此函數(shù)用于k2只有一個左孩子的單旋轉(zhuǎn)，
 *  在K2和它的左孩子之間旋轉(zhuǎn)，
 *  更新高度，返回新的根節(jié)點
    frist：     
             K2
         K1    K2R
     K1L  K1R     
    then：
              K1   
        K1L       K2
              K1R      K2R
 
 */
 
static Position SingleRotateWithLeft(Position k2)    /*/ LL旋轉(zhuǎn)/*/
{
	Position k1;
	k1=k2->left;
	k2->left=k1->right;
	k1->right=k2;
	/*/ 因為比較的是左右孩子的高度，所以求父節(jié)點的高度要加1/*/
	k2->Height=Max(Height(k2->left),Height(k2->right)) + 1;
	k1->Height=Max(Height(k1->left),Height(k2->right)) + 1;
	return k1;
}
/*
 *  此函數(shù)用于k1只有一個右孩子的單旋轉(zhuǎn)，
 *  在K1和它的右孩子之間旋轉(zhuǎn)，
 *  更新高度，返回新的根節(jié)點
 frist：
             K1   
        K1L       K2
              K2L      K2R
 then：
                  K2
              K1      K2R
       K1L       K2L
 
 */
static Position SingleRotateWithRight(Position k1)  /*/ RR旋轉(zhuǎn)/*/
{
	Position k2;
	k2=k1->right;
	k1->right=k2->left;
	k2->left=k1;
	 /*結(jié)點的位置變了, 要更新結(jié)點的高度值*/
	k1->Height=Max(Height(k1->left),Height(k1->right)) + 1;
	k2->Height=Max(Height(k2->left),Height(k2->right)) + 1;
	return k2;
}
/*
 * 此函數(shù)用于當(dāng) 如果 k3有一個左孩子，以及
 * 它的左孩子又有右孩子，執(zhí)行這個雙旋轉(zhuǎn)
 * 更新高度，返回新的根節(jié)點
   first：
               K1
       K2             K1R
K2L         K3       
        K3L     K3R
   then：
                   K3
          K2                K1
K2L           K3L      K3R         K1R
 */
static Position DoubleRotateLeft(Position k3)    /*/ LR旋轉(zhuǎn)/*/
{
	/*/在 k3 的左孩子，執(zhí)行右側(cè)單旋轉(zhuǎn)/*/
	k3->left=SingleRotateWithRight(k3->left);/*/ RR旋轉(zhuǎn)/*/
	/*/ 再對 k3 進行 左側(cè)單旋轉(zhuǎn)/*/
	return SingleRotateWithLeft(k3);         /*/ LL旋轉(zhuǎn)/*/
}
/*
 * 此函數(shù)用于當(dāng) 如果 k4有一個右孩子，以及
 * 它的右孩子又有左孩子，執(zhí)行這個雙旋轉(zhuǎn)
 * 更新高度，返回新的根節(jié)點
   first：
                K1
          K1L      K2
                K4   K2R
             k4L  K4R
   then：
                   K4
          K1                K2
K1L           K4L      K4R         K2R
 
 
 */
static Position DoubleRotateRight(Position k4)    /*/ RL旋轉(zhuǎn)/*/
{
	/*/在 k4 的右孩子，執(zhí)行左側(cè)單旋轉(zhuǎn)/*/
	k4->right = SingleRotateWithLeft(k4->right);
	/*/ 再對 k4 進行 右側(cè)單旋轉(zhuǎn)/*/
	return SingleRotateWithRight(k4);
}
/*
 *  向AVL樹插入可以通過如同它是未平衡的二叉查找樹一樣把給定的值插入樹中，
 *  接著自底向上向根節(jié)點折回，于在插入期間成為不平衡的所有節(jié)點上進行旋轉(zhuǎn)來完成。
 *  因為折回到根節(jié)點的路途上最多有1.5乘log n個節(jié)點，而每次AVL旋轉(zhuǎn)都耗費恒定的時間，
 *  插入處理在整體上耗費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不存在，則創(chuàng)建一個節(jié)點樹/*/
	if(T == NULL)
	{
		T = (AvlTree)malloc(sizeof(struct AvlNode));
		{
			T->data = x;
			T->Height = 0;
			T->left = T->right = NULL;
		}
	}
	/*/ 如果要插入的元素小于當(dāng)前元素/*/
	else if(x < T->data)
	{
		/*/遞歸插入/*/
		T->left=Insert(x,T->left);
		/*/插入元素之后，若 T 的左子樹比右子樹高度 之差是 2，即不滿足 AVL平衡特性，需要調(diào)整/*/
		if(Height(T->left) - Height(T->right) == 2)
		{
			/*/把x插入到了T->left的左側(cè)，只需 左側(cè)單旋轉(zhuǎn)/*/
			if(x < T->left->data)
				T = SingleRotateWithLeft(T);       /*/ LL旋轉(zhuǎn)/*/
			else
				/*/ x 插入到了T->left的右側(cè)，需要左側(cè)雙旋轉(zhuǎn)/*/
				T =  DoubleRotateLeft(T);          // LR旋轉(zhuǎn)/*/
		}
	}
/*/ 如果要插入的元素大于當(dāng)前元素/*/
	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 旋轉(zhuǎn)/*/
			else
				T =  DoubleRotateRight(T);        /*/RL旋轉(zhuǎn)/*/
		}
	}
	T->Height=Max(Height(T->left),Height(T->right)) + 1;
	return T;
}
/*
 *  對單個節(jié)點進行的AVL調(diào)整
                              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旋轉(zhuǎn)/*/
		else
			T =  DoubleRotateLeft(T);     /*/ LR旋轉(zhuǎn)/*/
	}
	if(Height(T->right) - Height(T->left) == 2)
	{
		if(Height(T->right->right) >= Height(T->right->left))
			T = SingleRotateWithRight(T);  /*/ RR旋轉(zhuǎn)/*/
		else
			T =  DoubleRotateRight(T);     /*/ RL旋轉(zhuǎn)/*/
	}
	return T;
}
/*
 * 首先定位要刪除的節(jié)點，然后用該節(jié)點的右孩子的最左孩子替換該節(jié)點，
 * 并重新調(diào)整以該節(jié)點為根的子樹為AVL樹，具體調(diào)整方法跟插入數(shù)據(jù)類似
 * 刪除處理在整體上耗費O(log n) 時間。
 */
AvlTree  Delete(ElementType x,AvlTree T)
{
	if(T == NULL)	return NULL;
	if(T->data == x)           /*/要刪除的 x 等于當(dāng)前節(jié)點元素/*/
	{
		if(T->right == NULL )  /*/ 若所要刪除的節(jié)點 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 即其字節(jié)點進行調(diào)整*/
			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 大于當(dāng)前節(jié)點元素，在T的右子樹中查找刪除/*/
	{
		T->right=Delete(x,T->right);
	}
	else                                       /*/ 要刪除的 x 小于當(dāng)前節(jié)點元素，在T的左子樹中查找刪除/*/
	{
		T->left=Delete(x,T->left);
	}
	/*
	 *   當(dāng)刪除元素后調(diào)整平衡
	 */
	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;
}
/*
 * 返回當(dāng)前位置的元素
 */
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("數(shù)據(jù)準(zhǔn)備 \n");
    for( i = 0; i < N; i++, j = ( j + 7 ) % 50)
    {/*插入15個數(shù) */
    	printf("j=%d  ",j);
        T = Insert( j, T );
    }
    puts("插入 4 \n");
    T = Insert( 4, T );
    //printf("中序遍歷\n");
    //Display(T);
     
    PointAsTree(T,4);
   printf("刪除偶數(shù)值\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 中[]數(shù)字僅用于展現(xiàn)遞歸調(diào)用多少次\n");
    printf( "Min is %d, Max is %d\n", Retrieve( FindMin( T ) ),
    Retrieve( FindMax( T ) ) );
	return EXIT_SUCCESS;
}