摘要: 平衡二叉樹的平衡標(biāo)志計算可以說是最簡單的, 也可以說是AVL樹中最難的。平衡標(biāo) 志計算方法有兩種: a. Balance = Height(Left) - Height(Right); b. Balance = Height(Right) - Height(Left); 其中 Height 為結(jié)點(diǎn)的子樹高度(>= 0), 算法簡單就是說只要左右子樹高度相減即可, 但運(yùn)行效率不高。當(dāng)結(jié)點(diǎn)數(shù)上千以上時, 頻繁增刪結(jié)點(diǎn)帶來開銷會相當(dāng)可觀, 正因如此, 本人通過推理得到的計算公式就非常重要了。
閱讀全文