为证明平衡搜索树的深度

Question

如果T是具有n个元素，L其左子树一个平衡BST和R其正确的，我怎样才能证明其深度小于或等于2log（N）+ 1？

有通过感应证明，我有，但我不明白这一点。

（据我所知，计算器，主要面向编程，但我发现了大约二叉搜索树的一些问题，并决定给它一个尝试，希望我没有做不好的事。））

Answer 1

通过的“平衡”的定义，在同一个节点的每一个左和右子树的深度由一个至多不同。 “深度”通常被定义为“从树根下降到叶最长的步行步骤数”，因此，例如具有一个根和两个叶（在它们可以被布置在平衡BST的唯一途径三个元件）一个BST是据说有深入的一个（看起来像您使用的是稍微不同的定义，会给它深两？），因为总会有一个根和一个叶（即叶是否是根的左或右子树没有区别），而一个只有一个根这也是一个叶（单个元件）将具有深度为0（没有与零个元素没有BST）。

所以对于n <= 3层的元件，调用d（n）的树的深度如上述所定义，明确地D(n) < log(n) + 1（与log意思基-2-对数）通过检查，因为1 = D(2) < log(2) + 1 = 2（也1 = D(3)为其不等式的RHS， log(3) + 1，实际上> 2）和0 = D(1) < log(1) + 1 = 1 - 这为我们提供了感应基

。

要完成归纳证明我们必须证明，如果D(k) < log(k) + 1所有k < 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)并没有“更不必说”完成相同的步骤，证据仍然成立。

Answer 2

如果二叉树是完整的左，右子树元素的数量可以是你的答案是真实的（N-1）/ 2，但如果它不是完整的，元素的数量不需要是（N-1） / 2作为最后一级可以有不同的元素