通過之前對二叉搜尋樹介紹可知，将集合構造為二叉搜尋樹結構，該結構下對樹中節點的查詢、删除和插入三種操作，時間複雜度均為。影響時間複雜度的因素即為二叉樹的高，為了盡量避免樹中每層上隻有一個節點的情況，這裡引入平衡二叉樹。
平衡二叉樹（AVL樹）
平衡二叉樹也叫自平衡二叉搜尋樹（Self-Balancing Binary Search Tree），是以其本質也是一顆二叉搜尋樹，不過為了限制左右子樹的高度差，避免出現傾斜樹等偏向于線性結構演化的情況，是以對二叉搜尋樹中每個節點的左右子樹作了限制，左右子樹的高度差稱之為平衡因子，樹中每個節點的平衡因子絕對值不大于1，此時二叉搜尋樹稱之為平衡二叉樹。自平衡是指，在對平衡二叉樹執行插入或删除節點操作後，可能會導緻樹中某個節點的平衡因子絕對值超過1，即平衡二叉樹變得“不平衡”，為了恢複該節點左右子樹的平衡，此時需要對節點執行旋轉操作。
在執行插入或删除節點操作後，平衡因子絕對值變為大于1的情況，即左右子樹的高度差為2或-2的情況，可以歸納為如下四種：
左左情況(LL)
LL情況是指根節點的平衡因子為2，根節點的左子節點平衡因子為0或1。
LL_1
如圖 LL_1 所示，當節點C的子節點被删除，或者節點D插入子節點F時，根節點A的平衡因子變為2，A的左子節點B的平衡因子為1。
LL_2
或者如圖 LL_2 所示，當節點C的子節點被删除，根節點A的平衡因子變為2，A的左子節點B的平衡因子為0。。
當根節點的左子樹高度比右子樹的高度大2，因為平衡二叉樹是一種有序結構，節點值之間具有大小關系，是以如果根節點保持不變，左右子樹始終分隔兩岸，則無論如何調整節點位置，二叉樹始終不可能恢複平衡。是以需要更換根節點，使得新的根節點的左右子樹的高度趨于平衡。
該情況下需要對平衡二叉樹執行右旋操作：
設定根節點root的左子節點為新的根節點
；
将
節點的右子樹作為root節點的左子樹，将root節點作為
的右子樹，即降低“左子樹”高度，提升“右子樹”高度，使得新的左右子樹高度趨于平衡；
對于圖 LL_1，節點B的平衡因子為1，設B節點的左子樹D高度為h，則右子樹E高度為h-1，因為A的平衡因子為2，是以二叉樹C的高度為： h-1。則右旋操作後，B的左子樹高度不變為h，右子樹高度為：
，此時二叉樹為平衡二叉樹，如下圖 balanced_LL_1。
balanced_LL_1
對于圖 LL_2，節點B的平衡因子為h，設B節點的左右子樹高度為h，則二叉樹C的高度為：h-1。右旋操作後，B的左子樹高度不變為h，右子樹高度為
：，此時二叉樹為平衡二叉樹，如下圖 balanced_LL_2。
balanced_LL_2
右旋代碼
其中
函數作用為更新調整後節點的平衡因子，因為右旋操作平衡因子變化的節點隻有兩個：原根節點和新根節點，即根節點和根節點的左子節點，是以隻需要對這兩個節點執行
函數。函數代碼參考如下：
更新二叉樹高度
樹的高度也就是左右子樹的高度最大值加一，若無子樹，則設定樹高為零。
右右情況(RR)
該情況與上面的左左情況具有對稱性，對平衡二叉樹執行插入或删除節點操作後，根節點的平衡因子變為-2，根節點的右子節點平衡因子為-1或0，為了恢複二叉樹的平衡，需要進行左旋，來使得新的左右子樹高度區域平衡。
RR
如上圖RR所示，該情況下需要對平衡二叉樹執行左旋操作：
設定根節點
的右子節點為新的根節點 ；
節點的左子樹作為root節點的右子樹，将root節點作為
的左子樹，即降低“右子樹”高度，提升“左子樹”高度，使得新的左右子樹高度趨于平衡；
左旋操作後，平衡二叉樹如圖 balanced_RR 所示。
balanced_RR
左旋代碼
左旋操作同右旋一樣，隻更改了原根節點和新根節點的平衡因子，是以隻需要對這兩個節點執行
函數。
左右情況
該情況下根節點的平衡因子與左左情況相同，都為2，不同之處在于左子節點的平衡因子為-1，若按照之前直接進行右旋操作，則旋轉操作後二叉樹扔處于不平衡狀态。
對于圖 LR，節點B的平衡因子為-1，設B節點的左子樹D高度為h，則右子樹E高度為h+1，因為A的平衡因子為2，是以二叉樹C的高度為： h。則右旋操作後，B的左子樹高度不變為h，右子樹高度為：
，因為B的平衡因子為-2，是以按此方式的旋轉操作沒有效果。
是以該情況下，首先需要對根節點的左子節點進行調整，即将左子節點的平衡因子由-1調整為1， 使得目前情況轉換為LL情況，然後再對二叉樹執行右旋操作。
step 1:對左子樹執行左旋操作
step_1
step 2:對二叉樹執行右旋操作
step_2
右左情況
該情況與上面左右情況對稱，根節點的平衡因子為-2，右子節點平衡因子為1，需要首先對右子樹進行右旋操作，調整二叉樹為RR情況，再對二叉樹執行左旋操作。
RL
step 1:對右子樹執行右旋操作
step_1
step 2:對二叉樹執行左旋操作
step_2
因為平衡二叉樹也是二叉搜尋樹，回顧二叉搜尋樹中的操作複雜度，查詢、插入和删除複雜度均為。平衡二叉樹中查詢複雜度影響因素自然為樹的高度；插入節點操作可以拆分為兩個步驟：查詢節點位置，插入節點後平衡操作；删除節點操作同理可以拆分為兩個步驟：查詢節點位置，删除節點後平衡操作。 平衡調節過程中可能存在旋轉操作，遞歸執行的次數則依賴于樹的高度（可以優化為目前節點平衡因子不發生變化，則取消向上遞歸）。是以平衡二叉樹中查詢、插入和删除節點操作的複雜度依賴于樹高。平衡二叉樹（AVL樹）
平衡二叉樹因為左右子樹的平衡因子限制，是以不可能存在類似于斜樹的情況，因為任一節點的左右子樹高度差最大為一，且二叉樹具有對稱性，是以不妨設每個子樹的左子樹高度大于右子樹高度。
AVL
根據平衡二叉樹定義可知，若二叉樹左子樹高度為
，則右子樹高度最少也要是h-1，方能滿足平衡二叉樹的平衡特性。以F(H)表示高度為H的平衡二叉樹的最少節點個數，若二叉樹不是空樹則有：
根據推導公式可知，平衡二叉樹的高度最大為
。當二叉樹向完全二叉樹靠攏，盡量填滿每層上的節點時，樹的高度最小，為
。是以相對于二叉搜尋樹，平衡二叉樹避免了向線性結構演化的傾向，查詢、插入和删除節點的時間複雜度為
。因為每個節點上需要儲存平衡因子，是以空間複雜度要略高于二叉搜尋樹。
python版本：3.7，樹中的周遊、節點插入和删除操作使用的是遞歸形式
樹節點定義
相對于二叉搜尋樹的節點定義，增加了height屬性。
樹定義
子產品中對樹結構中的函數進行實作
測試代碼與輸出
輸出結果為：