binary-tree - 平衡搜索树深度的证明

Question

如果 T 是具有 n 个元素的平衡 BST，L 是左子树，R 是右子树，我如何证明它的深度小于或等于 2log(n) + 1？

我有一个归纳证明，但我不明白。

（我知道stackoverflow主要是面向编程的，但是我发现了一些关于二叉搜索树的问题并决定试一试，希望我没有做不好的事情。:)）

Answer 1

By definition of "balanced", depths of every left and right subtrees of the same node differ at most by one. "Depth" is normally defined as "number of step of longest walk from tree root down to leaf", so for example a BST with one root and two leaves (three elements in the only way they can be arranged in a balanced BST) is said to have depth one (looks like you're using a slightly different definition that would give it depth two?), as would one with one root and one leaf (whether that leaf is the root's left or right subtree makes no difference), while one with just a root that's also a leaf (a single element) would have depth 0. (There is no BST with zero elements).

So for n <= 3 elements, calling D(n) the tree depth as above defined, clearly D(n) < log(n) + 1 (with log meaning base-2 logarithm) by inspection, since 1 = D(2) < log(2) + 1 = 2 (and also 1 = D(3) for which the RHS of inequality, log(3) + 1, is in fact > 2), and 0 = D(1) < log(1) + 1 = 1 -- this gives us the induction base.

To complete the proof by induction we have to show that if D(k) < log(k) + 1 for all k < n, then it also follows that D(n) < log(n) + 1.

If n is odd, clearly left and right subtree have (n-1)/2 elements each, and the tree has depth 1 more than the subtrees; but then D(n) = 1 + D((n-1)/2) < 1 + 1 + log((n-1)/2) (by the induction hypothesis) = 1 + log(n-1) (since log((n-1)/2) = log(n-1) - 1) and thus a fortiori < 1 + log(n), QED.

If n is even you follow just the same steps with log(n) instead of log(n-1) and without the "a fortiori" finish, and the proof still holds.

Answer 2

如果平衡二叉树完整，则您的答案是正确的，左右子树中的元素数可以为 (n-1)/2，但如果不完整，则元素数不必为 (n-1)/2，因为最后一层可能有不同的元素