t**g
发帖数: 1164 | 1 一个unbalanced binary tree
每个节点记录一个整数
对每个节点值
左边的child小于当前节点
右边的child大于当前节点
所以你插入1,2,3,4,5...n,会得到一个depth=n的树
可是插入6,4,8,3,5,7,9，就会得到一个well balanced tree
问题：
What is the average asymptotic depth of a simple unbalanced search tree of
integers? Use O(n) notation and provide proof | g*******y
发帖数: 1930 | 2 h(n) = 1 + 1/n * SUM{ max(h(i), h(n-1-i) } where i=0....n-1
max( h(i) , h(n-1-i) ) = h(max(i , n-1-i))
=>
h(n) = 1 + 2/n * SUM{ h(n/2+i) } where i=0...n/2-1
= 1 + < h(x) > where x = n/2 ... n with uniform distribution
then I am not quite sure about a strict math proof, but you can definitely "
try" the solution to prove it is O(logn) |
|
