平衡搜索树深度的证明
如果T是一个有n个元素的平衡BST，L是左子树，R是右子树，我如何证明它的深度小于或等于2log(n) + 1？
我有一个归纳证明，但我不明白。
（我知道 stackoverflow 主要是面向编程的，但我发现了一些关于二叉搜索树的问题，并决定尝试一下，希望我没有做一些不好的事情。:)）
If T is a balanced BST with n elements, L its left subtree and R its right one, how can I prove that its depth is less than or equal to 2log(n) + 1?
There is a proof by induction which I have but I don't get it.
(I understand that stackoverflow is mainly programming oriented but I found some questions about binary search trees and decided to give it a try, hope I am not doing something not good. :))
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
根据“平衡”的定义，同一节点的每个左子树和右子树的深度最多相差一。 “深度”通常定义为“从树根向下到叶子的最长步行步数”，因此，例如具有一个根和两个叶子的 BST（三个元素是它们可以在平衡 BST 中排列的唯一方式）是据说深度为一（看起来你使用的定义略有不同，深度为二？），就像一个具有一个根和一个叶子的树（无论该叶子是根的左子树还是右子树都没有区别），而只有根同时也是叶子（单个元素）的深度为 0。（没有零元素的 BST）。
因此，对于 n <= 3 个元素，将 D(n) 称为上面定义的树深度，显然
D(n)D(n)log(n) + 1（其中log表示以 2 为底的对数），通过检查，因为1 = D(2)1 = D(2)log(2) + 1 = 2（还有1 = D(3)，其中不等式的 RHSlog(3) + 1为事实上> 2)，并且0 = D(1) < log(1) + 1 = 1 -- 这为我们提供了归纳基础。为了通过归纳法完成证明，我们必须证明如果
D(k) < log(k) + 1 对于所有k < n，则也可得出 D(n)D(n)D(n)D(n)log(n) + 1 。如果n是奇数，显然左子树和右子树各有
(n-1)/2个元素，并且树的深度比子树多1；但 D(n) = 1 + D((n-1)/2)1 + 1 + log((n-1)/2)（根据归纳假设）= 1 + log(n-1)（因为log((n- 1)/2) = log(n-1) - 1) 更不用说< 1 + log(n)，QED。如果
n是偶数，则只需使用log(n)而不是log(n-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(withlogmeaning base-2 logarithm) by inspection, since1 = D(2) < log(2) + 1 = 2(and also1 = D(3)for which the RHS of inequality,log(3) + 1, is in fact> 2), and0 = 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) + 1for allk < n, then it also follows thatD(n) < log(n) + 1.If n is odd, clearly left and right subtree have
(n-1)/2elements each, and the tree has depth 1 more than the subtrees; but thenD(n) = 1 + D((n-1)/2) < 1 + 1 + log((n-1)/2)(by the induction hypothesis)= 1 + log(n-1)(sincelog((n-1)/2) = log(n-1) - 1) and thus a fortiori< 1 + log(n), QED.If
nis even you follow just the same steps withlog(n)instead oflog(n-1)and without the "a fortiori" finish, and the proof still holds.如果平衡二叉树是完整的，那么你的答案是正确的，左右子树中的元素数量可以是 (n-1)/2，但如果它不完整，则元素数量不需要是 (n-1)/2，如下所示最后一层可能有不同的元素
Your answer is true if Balanced binary tree is complete the number of elements in right and left sub tree can be (n-1)/2 but if it's not complete, number of elements need not to be (n-1)/2 as last level may have different elements