平衡二叉樹
今天有同學問了我如何構造平衡二叉樹，總結如下：
平衡因子 BF（balance factor）為該節點左子樹高度 - 右子樹高度，絕對值如果 ≤ 1，則二叉樹不需要調整。
平衡二叉樹構造過程比較簡單，分為四種情況：
- LL 插入
- RR 插入
- LR 插入
- RL 插入
用執行個體解釋一下四種情況的調整方案：
LL 插入：
可以計算得到 8 的 BF 為 2，受到破壞且是第一個發現的節點，
LL 表示破壞者處于被破壞者左子樹（left）的左子樹（left）中。
被破壞者 15
/ \
發現者 8 17
/
4
/
破壞者 1
此時需要發現者調整為：
被破壞者 15
/ \
發現者 4 17
/ \
1 8
LR 插入：
可以計算得到 8 的 BF 為 2，受到破壞且是第一個發現的節點，
LR 表示破壞者處于被破壞者左子樹（left）的右子樹（right）中。
被破壞者 15
/ \
發現者 4 17
/ \
1 8
\
12
此時需要将 調整為
15 8
/ / \
4 4 15
\
8
8
/ \
4 15
/ \
1 17
然後很重要的一步就是對 12 調整位置：
8
/ \
4 15
/ / \
1 12 17
而其實 RR 插入是和 LL 插入的情況相似的，RL 插入和 LR 插入也是如此。其中 LR 插入這種類型比 LL 插入類型調整起來更為複雜，LL 也不是從發現者開始計算左右子樹的，需要向上傳遞找到一系列受影響的節點，一般都是根節點出發的。
12 這個節點之是以放在 15 的左子樹中而不是放在 4 的右子樹，是由于平衡二叉樹節點的左子樹都比節點小，右子樹都比節點大的性質決定的。
總結
對一棵平衡二叉樹插入資料，平衡因子沒有被破壞就不需要調整；如果調整後不是一個二叉平衡樹，不滿足其節點的左子樹都比節點小，右子樹都比節點大的性質就說明調整的過程出錯了，需要排查算法的錯誤。