ON THE SILHOUETTE OF BINARY SEARCH TREES

• 成果类型: Article
• 署名作者: Gruebel, Rudolf
• 署名单位: Leibniz University Hannover
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/08-AAP593
• 发表日期: 2009
• 页码: 1781-1802
• 关键词: contraction method; quicksort; algorithm

摘要

A zero-one sequence describes a path through a rooted directed binary tree T; it also encodes a real number in [0, 1]. We regard the level of the external node of T along the path as a function on the unit interval, the silhouette of T. We investigate the asymptotic behavior of the resulting stochastic processes for sequences of trees that are generated by the binary search tree algorithm.