欧美一级特黄大片做受成人-亚洲成人一区二区电影-激情熟女一区二区三区-日韩专区欧美专区国产专区

小代碼向原文學(xué)習(xí)對(duì)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個(gè)結(jié)點(diǎn)為例子 插入元素后C總是不平衡的
 LL RR 較為簡(jiǎn)單   交換后C還是出于下方
 LR RL 統(tǒng)一的一句就是  C總提出交換子樹，要翻身做了老大。
 LL LR與 RR RL是對(duì)稱的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é)點(diǎn)
{
	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;
}

/*
 * 查找 可以像普通二叉查找樹一樣的進(jìn)行，所以耗費(fèi)O(log n)時(shí)間，因?yàn)锳VL樹總是保持平衡的。
 * 不需要特殊的準(zhǔn)備，樹的結(jié)構(gòu)不會(huì)由于查找而改變。（這是與伸展樹查找相對(duì)立的，它會(huì)因?yàn)椴檎叶兏鼧浣Y(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é)點(diǎn)/*/
}
/*
 *   FindMax，F(xiàn)indMin 查找最大和最小值，
 *   沒(méi)有特別的   這個(gè)就遞歸或循環(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é)點(diǎn)的高度
 */
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只有一個(gè)左孩子的單旋轉(zhuǎn)，
 *  在K2和它的左孩子之間旋轉(zhuǎn)，
 *  更新高度，返回新的根節(jié)點(diǎn)
    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;
	/*/ 因?yàn)楸容^的是左右孩子的高度，所以求父節(jié)點(diǎn)的高度要加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只有一個(gè)右孩子的單旋轉(zhuǎn)，
 *  在K1和它的右孩子之間旋轉(zhuǎn)，
 *  更新高度，返回新的根節(jié)點(diǎn)
 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é)點(diǎn)的位置變了, 要更新結(jié)點(diǎn)的高度值*/
	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有一個(gè)左孩子，以及
 * 它的左孩子又有右孩子，執(zhí)行這個(gè)雙旋轉(zhuǎn)
 * 更新高度，返回新的根節(jié)點(diǎn)
   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)/*/
	/*/ 再對(duì) k3 進(jìn)行 左側(cè)單旋轉(zhuǎn)/*/
	return SingleRotateWithLeft(k3);         /*/ LL旋轉(zhuǎn)/*/
}
/*
 * 此函數(shù)用于當(dāng) 如果 k4有一個(gè)右孩子，以及
 * 它的右孩子又有左孩子，執(zhí)行這個(gè)雙旋轉(zhuǎn)
 * 更新高度，返回新的根節(jié)點(diǎn)
   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);
	/*/ 再對(duì) k4 進(jìn)行 右側(cè)單旋轉(zhuǎn)/*/
	return SingleRotateWithRight(k4);
}
/*
 *  向AVL樹插入可以通過(guò)如同它是未平衡的二叉查找樹一樣把給定的值插入樹中，
 *  接著自底向上向根節(jié)點(diǎn)折回，于在插入期間成為不平衡的所有節(jié)點(diǎn)上進(jìn)行旋轉(zhuǎn)來(lái)完成。
 *  因?yàn)檎刍氐礁?jié)點(diǎn)的路途上最多有1.5乘log n個(gè)節(jié)點(diǎn)，而每次AVL旋轉(zhuǎn)都耗費(fèi)恒定的時(shí)間，
 *  插入處理在整體上耗費(fèi)O(log n) 時(shí)間。
 
                            X < CUR                         X > CUR
                       T                                       T
                     X   X                                   X   X 
                  LL    LR                              RL           RR
 */
 
 /*/4種基本的交換子樹方式 寫好后  以下進(jìn)入重點(diǎn)/*/
AvlTree  Insert(ElementType x,AvlTree T)
{
	/*/如果T不存在，則創(chuàng)建一個(gè)節(jié)點(diǎn)樹/*/
	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;
}
/*
 *  對(duì)單個(gè)節(jié)點(diǎn)進(jìn)行的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ǎng)h除的節(jié)點(diǎn)，然后用該節(jié)點(diǎn)的右孩子的最左孩子替換該節(jié)點(diǎn)，
 * 并重新調(diào)整以該節(jié)點(diǎn)為根的子樹為AVL樹，具體調(diào)整方法跟插入數(shù)據(jù)類似
 * 刪除處理在整體上耗費(fèi)O(log n) 時(shí)間。
 */
AvlTree  Delete(ElementType x,AvlTree T)
{
	if(T == NULL)	return NULL;
	if(T->data == x)           /*/要?jiǎng)h除的 x 等于當(dāng)前節(jié)點(diǎn)元素/*/
	{
		if(T->right == NULL )  /*/ 若所要?jiǎng)h除的節(jié)點(diǎn) 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;
			/* 對(duì)于替代后的T 即其字節(jié)點(diǎn)進(jìn)行調(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)                       /*/要?jiǎng)h除的 x 大于當(dāng)前節(jié)點(diǎn)元素，在T的右子樹中查找刪除/*/
	{
		T->right=Delete(x,T->right);
	}
	else                                       /*/ 要?jiǎng)h除的 x 小于當(dāng)前節(jié)點(diǎn)元素，在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個(gè)數(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;
}

網(wǎng)頁(yè)標(biāo)題：小代碼向原文學(xué)習(xí)對(duì)AVL樹的4種情況用字母標(biāo)記整理
分享路徑：http://aaarwkj.com/article10/gppddo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供建站公司、軟件開(kāi)發(fā)、標(biāo)簽優(yōu)化、品牌網(wǎng)站建設(shè)、自適應(yīng)網(wǎng)站、定制開(kāi)發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

手機(jī)網(wǎng)站建設(shè)
国产一区二区三区高潮爽| 日韩欧美精品在线观看免费| 久久久av在线免费观看| 午夜影院在线观看网站| 亚洲av欧美日韩国产| 色婷婷狠狠久久综合中文一本| 国产免费不卡午夜福利在线| 丝袜美腿美女日韩在线| 成人黄色av网站在线观看| 不卡一区二区福利日本| 中国女人内射91熟女| 免费看真人性生活视频| 欧美一级特黄大片做受另类| 免费av不卡一区二区| 在线不卡日本v二区到六区| 国产精品午夜福利亚洲综合网| 欧美精品三级不卡在线| 亚洲国产精品一区性色| 国产精品日韩欧美亚洲| 亚洲av欧美日韩国产| 国产精品亚洲精品日韩在线| 国产成人原创免费观看| 色综合色综合色综合色综合| 日本国产精品免费在线观看| 少妇太爽高潮在线播放| 久久亚洲一区二区内射| 国产自拍免费在线观看视频| 日韩精品在线另类亚洲| 人妻91一区二区三区| 熟女少妇精品一区二区三区| 日韩欧美亚洲福利在线| 91午夜福利国产在线观看| 久久午夜人妻一区二区| 中文字幕日韩精品国产| 人妻一少妇一区二区三区| 国产高清视频不卡在线| 精品毛片久久久久久久久| 国产精品呻吟久久人妻| 国产精品极品网站91青青| 在线日韩中文字幕二区| 男女午夜激情四射视频|