algorithm - 如何求出二叉树的主深度是O(sqrt(N))？

Question

在C语言数据结构与算法分析第二版中，关于二叉树，有描述二叉树的平均深度为O(sqrt(n))。我试图证明这一点，但我不知道如何做到这一点，有没有人可以帮助我？

Answer 1

让我们考虑完美二叉树(总是将元素分成 2 个):

       *
   *       *
 *   *   *   *
* * * * * * * *

如果我删除间隙并向左对齐:

*
**
****
********

您会看到每个深度级别都将其中的元素数量加倍(与上一级别相比)，因此:

n = 1 + 2 + 4 + 8 + ...

或:

n = sum( 2^i ) where i={ 0,1,2, ... ,level-1 }

因此，如果您想到它(就像设置了所有位的二进制数)，它与:

n = 2^level -1

所以从中提取级别:

n = 2^level -1  // +1
n+1 = 2^level   // log2
log2(n+1) = level

其中 n 是元素的数量，level 是树的深度。

对于不同数量的拆分，只是对数的底发生变化...但是对于通常的真实树，拆分是不规则的，您需要考虑每个元素的平均拆分数量...

如果你的树的高度应该与 O(sqrt(n)) 成正比，那么元素应该形成一个正方形 (level^2 = n) 或矩形，所以推测图形化:

******
******
******
******
******
******

@@@@@@
*@@@@@
**@@@@
***@@@
****@@
*****@

@
*@@
**@@@
***@@@@
****@@@@@
*****@@@@@@

*
***
*****
*******
*********
***********

          *
       *  *  *
     *  * * *  *
   *  * * * * *  *
 *  * * * * * * *  *
* * * * * * * * * * *

所以除了第一层 split 为 3 之外，大多数元素不只是在每个级别中的第一个和最后一个拆分为 2。如果我选​​择矩形而不是正方形，那么矩形越宽，平均拆分越多。 ..

          *
         * *
       *  *  *
     *  * * *  *
   *  * * * * *  *
 *  * * * * * * *  *
*   * * * * * * *   *