Random Suffix Search Trees

A random suffix search tree is a binary search tree constructed for the suffixes X i = 0:B i B i+1 B i+2 : : : of a sequence B 1 ; B 2 ; B 3 :; : : : of independent identically distributed random b-ary digits B j . Let D n denote the depth of the node for X n in this tree when B 1 is uniform on Z b . We show that for any value of b > 1, E D n = 2 log n + O(log log n), just as for the random binary search tree. We also show that D n = E D n ! 1 in probability