algorithm - 给定以下条件，我们如何确定它是否是自平衡 BST？

Question

根据自平衡 BST 的定义，孩子的身高应该 = Big-Theta(logn)。

在以下情况下，如何检查 BST 是否是自平衡的？其左子树和右子树中的节点数不超过其子树（包括节点本身）中节点总数的90%。

Answer 1

是的，如果你能确保每个子树的大小最多是其父树的 90%，那么树的高度最多可以是 -log(n)/log(.9)。