關(guān)于平衡二叉樹了解的還是太少，遂記錄如下。

• AVL樹的前世今生：二叉搜索樹（Binary Search Tree）

二叉搜索樹，是因?yàn)檫@種二叉樹能大幅度提高搜索效率。如果一個(gè)二叉樹滿足：對于任意一個(gè)節(jié)點(diǎn)，其值不小于左子樹的任何節(jié)點(diǎn)，且不大于右子樹的任何節(jié)點(diǎn)（反之亦可），則為二叉搜索樹。BST如果按照中序排序的話是一個(gè)有序序列。BST的平均查找時(shí)間復(fù)雜度為O(logn)，但是極端情況下，假如一開始建樹的時(shí)候是有序序列，那么查找時(shí)間復(fù)雜度可以到O(n), 構(gòu)建樹的時(shí)間復(fù)雜度為O(nlogn),為了解決這一問題，引人AVL tree。從此我們的主人公開始登場。

• AVL樹的優(yōu)勢

由于AVL tree要求左右子樹的高度差不大于1，因此這就保證了在建樹時(shí)不會出現(xiàn)樹退化為鏈表的情形。查找的時(shí)間復(fù)雜度可以保證為O(logn), 建樹時(shí)間復(fù)雜度依然為O(nlogn)。

• AVL樹的建樹過程
  主要問題：當(dāng)二叉排序樹不平衡時(shí)有幾種情形，具體是通過什么方法使樹平衡？是否有可以借鑒的規(guī)律？
  具體參考1

參考：
1 看圖說話之平衡二叉排序樹(AVL樹)