平衡二叉搜索樹詳解

平衡二叉搜索樹

平衡二叉搜索樹(英語：Balanced Binary Search Tree)是一種結構平衡的[二叉搜索樹] ，它是一種每個節點的左右兩子[樹] 高度差都不超過一的[二叉樹] 。它能在O(logn)內完成插入、查找和刪除操作，最早被發明的平衡二叉搜索樹為[AVL樹] 。

之前的BST已經可以解決很多查找問題，而且時間復雜度在O(logN),但是如果出現單支樹的情況，時間復雜度就會退化到O(N),也就是類似于單鏈表的查詢。

AVL樹

AVL樹是最早被發明的自平衡二叉查找樹。在AVL樹中，任一節點對應的兩棵子樹的最大高度差為1，因此它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下的時間復雜度都是O(logn)。增加和刪除元素的操作則可能需要借由一次或多次樹旋轉，以實現樹的重新平衡。

平衡因子

它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。若將二叉樹上結點的平衡因子BF(Balance Factor)定義為LH-RH，那么BF只能是-1,0,1。只要|BF|>=1，則二叉樹就是不平衡的。

平衡二叉樹

不平衡的二叉樹

旋轉

OK，現在我們一眼可以看出哪種是平衡，哪種是不平衡的。如果不平衡的二叉樹，就需要做旋轉

哪些操作會導致原來平衡的二叉樹，變得不平衡?插入一個新的節點，或者刪除一個節點，都有可能導致二叉樹的平衡結構被破壞。此時就會需要通過自身旋轉，來修復。

假設平衡因子是左子樹的高度減去右子樹的高度所得到的值，又假設由于在二叉排序樹上插入節點而失去平衡的最小子樹根節點的指針為a(即a是離插入點最近，且平衡因子絕對值超過1的祖先節點)，則失去平衡后進行的規律可歸納為下列四種情況：

單向右旋平衡處理LL：由于在*a的左子樹根節點的左子樹上插入節點，a的平衡因子由1增至2，致使以a為根的子樹失去平衡，則需進行一次右旋轉操作;

單向左旋平衡處理RR：由于在*a的右子樹根節點的右子樹上插入節點，a的平衡因子由-1變為-2，致使以a為根的子樹失去平衡，則需進行一次左旋轉操作;

雙向旋轉(先左后右)平衡處理LR：由于在*a的左子樹根節點的右子樹上插入節點，a的平衡因子由1增至2，致使以a為根的子樹失去平衡，則需進行兩次旋轉(先左旋后右旋)操作。

雙向旋轉(先右后左)平衡處理RL：由于在*a的右子樹根節點的左子樹上插入節點，a的平衡因子由-1變為-2，致使以a為根的子樹失去平衡，則需進行兩次旋轉(先右旋后左旋)操作。