摘要: 平衡二叉树的平衡标志计算可以说是最简单的, 也可以说是AVL树中最难的。平衡标 志计算方法有两种: a. Balance = Height(Left) - Height(Right); b. Balance = Height(Right) - Height(Left); 其中 Height 为结点的子树高度(>= 0), 算法简单就是说只要左右子树高度相减即可, 但运行效率不高。当结点数上千以上时, 频繁增删结点带来开销会相当可观, 正因如此, 本人通过推理得到的计算公式就非常重要了。
阅读全文