平衡二叉樹中，平衡的意思就是當(dāng)節(jié)點數(shù)量固定的時候，左右子樹的高度越接近，這棵二叉樹就越平衡，相應(yīng)的高度也就越低。最理想的平衡狀態(tài)其實就是完全二叉樹和滿二叉樹，它們的高度是最小的。
平衡二叉搜索樹，英文名稱Balanced Binary Search Tree，經(jīng)典常見的平衡二叉樹有AVL樹和紅黑樹。一般也稱它們?yōu)樽云胶獾亩嫠阉鳂洹?br>
AVL樹中，為了判斷其平衡狀態(tài)，定義了“平衡因子”，它表示某節(jié)點的左右子樹的高度差。
AVL樹的特點是：1、每個節(jié)點的平衡因子只可能是1或0或-1（即，絕對值<=1，如果超過1，稱之為“失衡”。）也即是每個節(jié)點的左右子樹高度差不超過1；2、搜索、添加、刪除的時間復(fù)雜度是O(logN)；3、父節(jié)點、非祖先節(jié)點，都不可能失衡；4、失衡最壞的情況，可能會導(dǎo)致所有祖先節(jié)點都失衡。
要維護平衡狀態(tài)，必須先找到最初的失衡節(jié)點，以及造成失衡的原因。所謂最初的失衡節(jié)點，指的是位于二叉搜索樹最下方、接近葉子節(jié)點的那個失衡節(jié)點，一旦解決了這個失衡節(jié)點的失衡狀態(tài)，其祖先節(jié)點的失衡狀態(tài)也就解決了。
區(qū)分出造成一棵已經(jīng)平衡的二叉搜索樹失衡的原因，或者說找出新節(jié)點最后經(jīng)過的添加路徑（這里所說的最后的路徑指的是從失衡節(jié)點開始算），總的來說有四種情況：
- 添加路徑是右右，從失衡節(jié)點g開始，向右先找到右子節(jié)點p，再由p向右找到p的右子節(jié)點n，給n節(jié)點（或其子樹）添加了一個節(jié)點，造成了失衡；
- 添加路徑是左左，從失衡節(jié)點g開始，向左先找到左子節(jié)點p，再由p向左找到p的左子節(jié)點n，給n節(jié)點（或其子樹）添加了一個節(jié)點，造成了失衡；
- 添加路徑是左右，從失衡節(jié)點g開始，向左找到左子節(jié)點p，再由p向右找到p的右子節(jié)點n，給節(jié)點n（或其子樹）添加了一個節(jié)點，造成了失衡；
- 添加路徑是右左，從失衡節(jié)點g開始，向右找到右子節(jié)點p，再由p向左找到p的左子節(jié)點n，給節(jié)點n（或其子樹）添加了一個節(jié)點，造成了失衡。
還需要理解以下兩種操作，是用來將失衡的AVL樹再調(diào)整為平衡狀態(tài)的操作：左旋和右旋。
-
左旋：用來解決“右右”原因造成的失衡。具體操作就是，將失衡節(jié)點的右子樹往左拉，右子節(jié)點變成父節(jié)點，并把晉升之后多余的左子樹出讓給降級節(jié)點的右子節(jié)點?？梢越Y(jié)合下圖進行理解；左旋.png
-
右旋：用來解決“左左”原因造成的失衡。具體操作就是，將失衡節(jié)點的左子樹往右拉，左子節(jié)點變成父節(jié)點，并把晉升之后多余的右子節(jié)點出讓給降級節(jié)點的左子節(jié)點。右旋.png
由“左右”原因造成的失衡，以及由“右左”原因造成的失衡，都可以用左旋和右旋來解決：
