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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom