证明平衡二叉搜索树的高度是 log(n) [英] Proof that the height of a balanced binary-search tree is log(n)

问题描述

二分搜索算法需要 log(n) 时间，因为树的高度(有 n 个节点)将为 log(n).

你将如何证明这一点?

解决方案

现在我没有给出数学证明.尝试理解使用log to base 2的问题.log₂是计算机科学中log的正常含义.

首先理解它是二进制对数(log₂n)(以2为底的对数).例如，

• 1 的二进制对数是 0
• 2 的二元对数是 1
• 3 的二进制对数是 1
• 4 的二元对数是 2
• 5、6、7的二元对数是2
• 8-15的二元对数是3
• 16-31 的二元对数是 4，依此类推.

对于每个高度，完全平衡树中的节点数为

<前>高度节点日志计算0 1 日志₂1 = 01 3 log₂3 = 12 7 log₂7 = 23 15 log₂15 = 3

考虑一个具有 8 到 15 个节点(任意数字，比如 10 个)的平衡树.它总是高度 3，因为从 8 到 15 的任何数字的 log₂ 都是 3.

在平衡二叉树中，每次迭代时要解决的问题的大小减半.因此，大约需要 log₂n 次迭代才能获得大小为 1 的问题.

我希望这会有所帮助.

The binary-search algorithm takes log(n) time, because of the fact that the height of the tree (with n nodes) would be log(n).

How would you prove this?

解决方案

Now here I am not giving mathematical proof. Try to understand the problem using log to the base 2. Log₂ is the normal meaning of log in computer science.

First, understand it is binary logarithm (log₂n) (logarithm to the base 2). For example,

• the binary logarithm of 1 is 0
• the binary logarithm of 2 is 1
• the binary logarithm of 3 is 1
• the binary logarithm of 4 is 2
• the binary logarithm of 5, 6, 7 is 2
• the binary logarithm of 8-15 is 3
• the binary logarithm of 16-31 is 4 and so on.

For each height the number of nodes in a fully balanced tree are

    Height  Nodes  Log calculation
      0        1      log21 = 0
      1        3      log23 = 1
      2        7      log27 = 2
      3       15      log215 = 3

Consider a balanced tree with between 8 and 15 nodes (any number, let's say 10). It is always going to be height 3 because log₂ of any number from 8 to 15 is 3.

In a balanced binary tree the size of the problem to be solved is halved with every iteration. Thus roughly log₂n iterations are needed to obtain a problem of size 1.

I hope this helps.

这篇关于证明平衡二叉搜索树的高度是 log(n)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！