Lecture Notes in Computer Science, 1997, Volume 1256/1997, 441-448, DOI: 10.1007/3-540-63165-8_200

On the concentration of the height of binary search trees

J. M. Robson

View Related Documents

Abstract

The expectation of the absolute value of the difference between the heights of two random binary search trees of n nodes is less than 6.25 for infinitely many n. Given a plausible assumption, this expectation is less than 4.96 for all but a finite number of values of n.

Fulltext Preview

Image of the first page of the fulltext document