On the silhouette of binary search trees (Q983879): Difference between revisions

A zero-one sequence is used to describe a path through a rooted directed binary tree \(T\). It also encodes a real number in \([0,1]\), given by its binary expansion. The silhouette of the tree is defined as function on \([0,1]\), which at point \(s\) has as value the height of the tree along the binary path corresponding \(s\). For a sequence of random binary search trees a limit theorem for the silhouette process is established, where convergence is understood in the sense of linear functionals on some function space. The proof combines martingale arguments with the contraction method.