楼主:
carlossp (weyuruiwysfjgnjf)
2015-02-03 20:26:44小弟有几题问题想要问大家
98年资结 2.(4) Prove that the average height of the binary search tree
after inserting n integer values{1,2....n} in a random order
is O(logn).
这题毫无想法，只想到每次插入的可能性做高度平均,超复杂～～
觉得我的写法可能拿不到分 看看就好given a set {1,2....n} nodeseach node may be a leaf in same posibilitythus we know that in BST average serch time isO(lgn), for those leafs serch times = tree heightthen the BST will be average height O(lgn)