樹與二叉樹的應用：平衡二叉樹

• 平衡二叉樹的定義：
• • 如何計算高度為h的最小平衡二叉樹的節點數N~h~？
  • 如何判斷一顆樹為平衡二叉樹？
• 平衡二叉樹的插入：
• • 方法一、LL平衡旋轉（右單旋轉）
  • 方法二、RR平衡旋轉（左單旋轉）
  • 方法三、LR平衡旋轉（先右后左雙旋轉）
  • 方法四、RL平衡旋轉（先右后左雙旋轉）

平衡二叉樹的定義：

如何計算高度為h的最小平衡二叉樹的節點數N_h？

1、為滿足樹的高度為h，取根節點的左子樹高度為N(h-1) 2、為滿足平衡二叉樹，根節點的右子樹可以取N(h),N(h-1),N(h-2) 3、若為N~h~，則不滿足高度為h的要求 4、若為N~h-1~，則不滿足最小的要求 5、所以根節點的右子樹為N(h-2) 6、所以節點總數為N(h) = N(h-1)+N(h-2)+1 7、又因為N(0)=0；N(1)=1； 8、根據動態規劃算法或者遞歸算法即可求解

如何判斷一顆樹為平衡二叉樹？

PS： n表示高度，b表示是否平衡（n=1平衡，n=0不平衡）
代碼實現：

void Judge_AVL(BiTree bt,int &balance,int &h){ //根節點，平衡性，高度 int bl = 0;br = 0;hl = 0;hr = 0;if(bt == NULL){ //遞歸的出口h = 0;balance = 1;} else if(bt->lchild == NULL && bt->rchild == NULL){h = 1;balance = 1;}else{Judge_AVL(bt->lchild,bl,hl);Judge_AVL(bt->rchild,br,hr);if(hl > hr) //計算高度h = hl + 1;elseh = hr + 1;if(abs(hl-hr) < 2 && bl == 1 && br == 1) //判斷平衡性1balance = 1;elsebalance = 0} }

平衡二叉樹的插入：

先進行二叉排序樹的插入過程，插入完成后在進行調整
調整的前提： 每次調整最小的不平衡子樹

方法一、LL平衡旋轉（右單旋轉）

ps： BL指B的左子樹；BR指B右子樹；AR指A的右子樹

例：

方法二、RR平衡旋轉（左單旋轉）

例：

方法三、LR平衡旋轉（先右后左雙旋轉）

例：

方法四、RL平衡旋轉（先右后左雙旋轉）

例：

總結

以上是生活随笔為你收集整理的数据结构之树与二叉树的应用：平衡二叉树（AVL）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。