On the expected height of fringe-balanced trees |
| |
Authors: | Luc Devroye |
| |
Affiliation: | (1) School of Computer Science, McGill University, 3480 University Street, H3A 2A7 Montreal, Canada |
| |
Abstract: | We study the effect of a well-known balancing heuristic on the expected height of a random binary search tree. After insertion of an element, if any node on the insertion path has a subtree of size precisely 2t+1 for a fixed integert, then the subtree rooted at that node is destroyed and replaced by a new subtree in which the median of the 2t+1 elements is the new root. IfHn denotes the height of the resulting random tree, we show thatHn/logn c(t) in probability for some functionc(t). In particular,c(0)=4.31107... (the ordinary binary search tree),c(1)=3.192570 ...,c(3)=2.555539 ...,c(10)=2.049289 ... andc(100)=1.623695 ....Research of the author was sponsored by NSERC Grant A3456 and by FCAR Grant 90-ER-0291 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|