排序二叉樹有以下缺點：

同樣的關鍵字集合有可能導致不同的樹結構索引，如下圖的右圖所示，此時他的搜索性能已經是線性的了，為了解決這種"樹一邊倒的現象"，自平衡二叉樹就被提出來了。平衡二叉樹的目的是為了減少二叉查找樹層次，提高查找速度。

平衡二叉樹

定義：平衡二叉樹或為空樹,又被稱為AVL樹（有別于AVL算法）或為如下性質的二叉排序樹:
（1）左右子樹深度之差的絕對值不超過1;
（2）左右子樹仍然為平衡二叉樹.
平衡二叉樹必定是二叉搜索樹，反之則不一定。
平衡二叉樹的常用實現方法：AA樹、AVL樹、紅黑樹、樹堆Treap、伸展樹等AVL 樹是高度平衡的，頻繁的插入和刪除，會引起頻繁的reblance，導致效率下降
紅黑樹不是高度平衡的，算是一種折中，插入最多兩次旋轉，刪除最多三次旋轉。

平衡因子（平衡度）

平衡因子=左子樹高度-右子樹高度

當平衡因子為1，-1，0時，當前的樹處于平衡狀態，當平衡因子為2，-2時，當前樹處于不平衡狀態，需要進行自平衡

如何進行自平衡

• 找平衡因子=2/-2
• 找插入新結點后失去平衡的最小子樹
  該子樹要求：
  1.距離插入結點最近
  2.平衡因子絕對值為1的結點作為根
• 平衡調整（有4種情況如下）
  
  左旋和右旋？
  總結了一句口訣(主要用于寫代碼)：

左旋：其右子（若有）給其父結點的左結點 右旋：其左子（若有）給其父結點的右結點

如圖演示:

代碼實現

葉點類：

class AVLTreeNode{public int data;public AVLTreeNode left;public AVLTreeNode right;public int height;public int getData() {return data;}public void setData(int data) {this.data = data;}public AVLTreeNode getLeft() {return left;}public void setLeft(AVLTreeNode left) {this.left = left;}public AVLTreeNode getRight() {return right;}public void setRight(AVLTreeNode right) {this.right = right;}public int getheight() {return height;}public void setheight(int height) {this.height = height;}public AVLTreeNode(int data){initiateNode(data,null,null,1);}public AVLTreeNode(int data,AVLTreeNode left,AVLTreeNode right,int height){initiateNode(data,left,right,height);}public void initiateNode(int date,AVLTreeNode left,AVLTreeNode right,int height){this.setData(date);this.left=left;this.right=right;this.height=height;}// 返回左子樹的高度public int leftHeight() {if (left == null) {return 0;}return left.height();}// 返回右子樹的高度public int rightHeight() {if (right == null) {return 0;}return right.height();}//遞歸返回以該結點為根結點的樹的高度public int height() {//+1因為本身也占一層return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;} }

LL型旋轉：

/** LL型旋轉；左左對應的情況(左單旋轉)* 傳入值：旋轉前的根結點* 返回值：旋轉后的根節點*/private AVLTreeNode leftLeftRotation(AVLTreeNode root) {AVLTreeNode rootLeft=root.left;//右子結點給父結點的左結點root.left=rootLeft.right;//將原根結點作為rootLeft的右結點，讓rootLeft成為新的根結點rootLeft.right=root;//重新計算高度root.height = root.height();rootLeft.height = rootLeft.height();return rootLeft;}

private AVLTreeNode rightRightRotation(AVLTreeNode root) {AVLTreeNode rootRight=root.right;//左子結點給父結點的右結點root.right=rootRight.left;//將原根結點作為rootRight的左結點，讓rootRight成為新的根結點rootRight.left=root;//重計算高度root.height = root.height();rootRight.height=rootRight.height();return rootRight;}

LR旋轉：需要經過兩次旋轉（右旋后左旋）才能讓AVL樹恢復平衡

private AVLTreeNode leftRightRotation(AVLTreeNode root) {//先右旋再左旋root.left = rightRightRotation(root.left);return leftLeftRotation(root);}

private AVLTreeNode rightLeftRotation(AVLTreeNode root) {root.right = leftLeftRotation(root.right);return rightRightRotation(root);}

總結

以上是生活随笔為你收集整理的自平衡二叉树（Self-balancing binary search tree）的全部內容，希望文章能夠幫你解決所遇到的問題。

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