The height of record-biased trees

Benoît Corsini

Given a permutation $\sigma$, its corresponding binary search tree is obtained by recursively inserting the values $\sigma (1),\dots ,\sigma (n)$ into a binary tree so that the label of each node i…