t**g
发帖数: 1164 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: ttgg (还在苦苦思索昵称中), 信区: JobHunting
标 题: 请教一个binary tree问题
发信站: BBS 未名空间站 (Fri Feb 26 00:18:36 2010, 美东)
一个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 |
|
