Abstract: | A random suffix search tree is a binary search tree constructed for the suffixes Xi = 0 · BiBi+1Bi+2… of a sequence B1, B2, B3, … of independent identically distributed random b‐ary digits Bj. Let Dn denote the depth of the node for Xn in this tree when B1 is uniform on ?b. We show that for any value of b > 1, ??Dn = 2 log n + O(log2log n), just as for the random binary search tree. We also show that Dn/??Dn → 1 in probability. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003 |