Transcript LINUX System (English

Lecture 12 : Trie Data Structure
Bong-Soo Sohn
Assistant Professor
School of Computer Science and Engineering
Chung-Ang University
Problem

Store this collection of words in a memory
efficient way :
{abacus, abode, dreaded, dust, dusty, planar,
east}
Arrays
a
b
a
c
u
a
b
o
d
e
d
r
e
a
d
d
u
s
t
d
u
s
t
= 6 slots
s
= 5 slots
e
d
= 7 slots
= 4 slots
y
= 5 slots
Idea

Take advantage of the common letters in
the words

Reduce redundancy
Use same letter for more than one word

Trie

Store characters (digits) in each node, not keys.
 Path from root to a node is associated with a
key
 Use characters of the key to guide the search
process
 All the descendants of a node have a common
prefix of the string associated with that node

From retrieval, but pronounced “try”
Example
g
s
o
h
t
i
u
go
Make sure the word
“she” is not found…
she
e
m
n
sun
d
l
e
…unless it has been
explicitly inserted! shed
time
l
shell
example

A trie for keys "t", "to", "te", "tea", "ten",
"i", "in", and "inn".
Advantages






Looking up keys is faster. O(m) time.
A BST takes O(log n) time
m : length of key , n : # of elements
In the worst case, log(n) will approach m
Tries can require less space when they contain a
large number of short strings
Longest prefix matching is possible


finding the key sharing the longest possible prefix of
characters all unique
Fast search/insert/delete
Drawbacks

Tries can be slower in some cases.


Especially when the tree is accessed from disk
It is not easy to represent all keys as strings


Floating point numbers (1.0 , +1.0, 1 …)
Inefficient when a key is too long
Applications

Can replace a hash table






Only take O(m) , m : length of key
No collision
No need to provide hash function
Can provide an alphabetical ordering of keys
Dictionary
IP routing



Routing : process of selecting paths in a network along which to
send network traffic
when given a destination address, find next place(place) to go.
Internet router table is a collection of rules of the form (P, NH),

P : prefix, NH : next hop