Understanding Search Trees via Statistical Physics

Satya Majumdar
Université d'Orsay

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) Presentation (PDF File)

Back to Workshop II: Random Curves, Surfaces, and Transport