Transcript Lexicographic Search:Tries

Lexicographic Search:Tries
•
All of the searching methods we have seen so far
compare entire keys during the search
•
Idea: Why not consider a key to be a sequence of
characters (letters or digits, for example) and use
these characters to determine a multiway branch at
each step
–
–
–
–
If the keys are alphabetic names (names), we make a 29-way
branch at each step.
If the keys are natural numbers in base 10, we make a 10 way
branch at each step
Similar to a thumb index in a dictionary
Called Retrieval -- pronounced like “try”
1
•
Tries - Example
Assume that we have the following keys in a trie:
–
–
0, 10, 11, 100, 101, 110, 2, 21
Notice that the root does not store actual data
0 1 2 3 4 5 6 7 8 9
2
0
10
100
101
11
21
110
2
•
Search 110:
Tries - Search
0 1 2 3 4 5 6 7 8 9
2
0
10
100
101
11
21
110
3
•
Tries - Insertion
Insert 2195 into the following trie:
0 1 2 3 4 5 6 7 8 9
2
0
10
100
101
11
21
110
2195
4
•
Tries - Deletion
Delete 10 from the following trie:
0 1 2 3 4 5 6 7 8 9
2
0
10
100
101
11
21
110
2195
5
•
Tries - Deletion
Delete 110 from the following trie:
0 1 2 3 4 5 6 7 8 9
2
0
21
100
101
110
2195
6
Tries: Summary
•
# of steps requires to search a trie (or to insert into it) is
proportional to the number of characters making up a key
–
•
If the number of chars is small relative to the logarithm 2 of
the number of keys, a trie may be superior to a binary search
tree
–
•
E.g., if we have numbers in the range 0 – 999999, then we have at
most 6 steps (comparisons) to reach a key
E.g., if keys consist of all 999999 numbers in the range 0-999999,
we have at most 6 steps to reach a key, whereas a binary search
tree would take log2(999999) ~ 20 steps (key comparisons)
The best solution may be to combine the methods
–
A trie can be used in the fist few chars of the key, and then
another method can be used for the remainder of the key
7