Search trees are random structures that play a vital role in data storage in computer science. This talk aims at understanding the statistical properties of various random search trees using simple techniques of statistical physics. In particular, via a mapping to a random fragmentation problem, we show how a rather striking phase transition appears in the fluctuations of the number of nodes needed to store a random data of size $N$, as a function of the branching ratio $m$ of the tree at a critical value $m_c=26$
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.