引言
因為按照不同的插入順序，將會導(dǎo)致不同深度菜秦，和不同的平均查找長度ASL
定義
- 平衡因子（Balance Factor）:BF(T) = hL - hR
- 平衡二叉樹（Balanced Binary Tree）（AVL樹）
任一節(jié)點的左右子樹高度的絕對值不超過1透且， |BF(T)|<=1
平衡二叉樹的調(diào)整
- RR旋轉(zhuǎn)
麻煩節(jié)點在發(fā)現(xiàn)者右子樹的右子樹伤塌，需要進(jìn)行RR旋轉(zhuǎn) - LL旋轉(zhuǎn)
麻煩節(jié)點在發(fā)現(xiàn)者左子樹的左子樹茫负，需要進(jìn)行LL旋轉(zhuǎn) - LR旋轉(zhuǎn)
麻煩節(jié)點在發(fā)現(xiàn)者左子樹的右子樹米同，需要進(jìn)行LR旋轉(zhuǎn) - RL旋轉(zhuǎn)
麻煩節(jié)點在發(fā)現(xiàn)者右子樹的左子樹陷嘴，需要進(jìn)行RL旋轉(zhuǎn)
我的思考
需要如下幾個函數(shù)來支撐實現(xiàn)平衡二叉樹的插入元素
- 求當(dāng)前節(jié)點的左右子樹的高度映砖，通過左右高度值計算平衡因子。
- 確定平衡因子> 1對應(yīng)的節(jié)點灾挨，判別需要采用的旋轉(zhuǎn)調(diào)整方式
- 按照對應(yīng)的旋轉(zhuǎn)方式重新排列二叉樹
