请教一个binary tree问题# JobHunting - 待字闺中
t*g
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
每个节点记录一个整数
对每个节点值
左边的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