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