一棵树“平衡”的意义是什么？
来源：12-1 平衡树和AVL
Poplar_hills
2019-03-27
Hi bobo 老师，
学习了这节课（尤其是下面这页 PPT）之后我对“平衡”有了如下理解：
如果说一棵树是“平衡”的，就隐含着“这棵树的高度和节点数量成 log(n) 的关系”这样的信息，这也就是“平衡”的意义所在。
之所以要区分一棵树是否平衡，就是因为需要知道这棵树的操作复杂度是什么量级的。比如说“堆是一种平衡树”，实际上就是从操作复杂度说“堆的各种操作（insert、extract）的复杂度都是 O(logn)”。
不知道我的理解是否正确？如果我理解有误的话，是否可以为我解释一下一棵树“平衡”的意义是什么？
谢谢！
写回答
1回答
-
大赞！你理解的完全正确！
如果敢说一棵树是”平衡“的，就意味着它的高度是logn级别的。也就意味着对这棵树的基本操作（增删改查）是logn级别的。
注意，是logn这个级别的，而不是就是logn。具体什么叫logn级别的，严格的是有明确的数学定义的。由于我的课程不希望牵扯这么复杂的理论只是，就没有介绍。如果有兴趣，可以查一下大O的准确数学定义。一颗平衡树，意味着他的高度是O(logn)的，相应的，增删改查等基本操作，也是O(logn)的。
但如果一棵树不能保证一定平衡，比如BST，意味着它的高度有可能是O(n)的，相应的，增删改查的基本操作，也就是O(n)级别的操作。
继续加油！：）
022019-03-27
相似问题