Martingales and large deviations for binary search trees
We establish an almost sure large deviations theorem for the depth of the external nodes of binary search trees (BSTs). To achieve this, a parametric family of martingales is introduced. This family also allows us to get asymptotic results on the number of external nodes at deepest level. (C) 2001 John Wiley & Sons, Inc.We establish an almost sure large deviations theorem for the depth of the external nodes of binary search trees (BSTs). To achieve this, a parametric family of martingales is introduced. This family also allows us to get asymptotic results on the number of external nodes at deepest level. (C) 2001 John Wiley & Sons, Inc.
martingales large deviations binary search trees random trees