A 

= 

(e  + a_{j}(a_{1}+...+a_{j}) 

). 
N 

(z,u,x_{1},x_{2},...,x_{r})= 

æ ç ç è 
1 + 

ö ÷ ÷ ø 
( A  \ {a}) 

= (a_{1}+...+a 

) 

W (a 

+...+a_{r}) 

. 
æ ç ç è 

f_{n} z^{n} 
ö ÷ ÷ ø 
W 
æ ç ç è 

g_{n} z^{n} 
ö ÷ ÷ ø 
= 

æ ç ç è 


f_{k}g_{nk} 
ö ÷ ÷ ø 
z^{n}. 
(N 

(z,u,x_{1},...,x 

) W N 

(z,u,x 

,...,x_{r})) 
æ ç ç è 
1+ 

ö ÷ ÷ ø 
. 
E  [C 

]= 


æ ç è 
1e 

ö ÷ ø 
, with  P 

= 

p_{j}. 





E  [L] 

= 

n log n +O(n) and E  [R] 

= 

log n +O(1) 
In order to assess the relevance of these theoretical analyses, a simulation campaign was undertaken on Herman Melville's novel, Moby Dick. Its conclusions are [1]:
arraytrie (standard) listtrie bsttrie (tst)
Pointers r/H_{ S} n 2/H_{ S} n 3/H_{ S} n Path length 1/H_{ S} nlog n C_{ S}^{*}/H_{ S} nlog n C_{ S}/H_{ S} nlog n Search 1/H_{ S} log n C_{ S}^{*}/H_{ S} log n C_{ S}/H_{ S} log n
Ternary search tries are an efficient data structure from the information theoretic point of view since a search costs typically about log n comparisons. Listtries require about 3 times as many comparisons. For an alphabet of cardinality 26, the storage cost of ternary search tries is about 9 times smaller than standard arraytries.
This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.