Premium
Random suffix search trees
Author(s) -
Devroye Luc,
Neininger Ralph
Publication year - 2003
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10103
Subject(s) - combinatorics , mathematics , random binary tree , binary search tree , self balancing binary search tree , independent and identically distributed random variables , tree (set theory) , optimal binary search tree , b tree , suffix , sequence (biology) , suffix tree , binary number , discrete mathematics , binary tree , k ary tree , random variable , statistics , tree structure , arithmetic , linguistics , philosophy , biology , genetics
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 ℤ b . We show that for any value of b > 1, D n = 2 log n + O (log 2 log n ), just as for the random binary search tree. We also show that D n / D n → 1 in probability. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003