To remove the element whose key is theKey
, we
first search for the element with this key. If there
is no matching element in the trie,
nothing is to be done. So, assume that the trie contains an element
theElement
whose
key is theKey
.
The element node X
that contains theElement
is discarded, and
we retrace the path from X
to the root discarding
branch nodes that are roots of subtries that
have only 1
element in them.
This path retracing stops when we either reach a branch node that is not
discarded or we discard the root.
Consider the trie of Figure 7. When the element with key
951237625
is removed, the element node
J
is discarded and we follow the
path from node J
to the root node
A
.
The branch node I
is discarded because the subtrie with
root I
contains the single element node
K
.
We next reach the branch node F
. This node is also
discarded, and we proceed to the branch node D
.
Since the subtrie rooted at D
has
2
element nodes (K
and L
), this branch node is not discarded.
Instead, node K
is made a child of this branch
node, as is shown in Figure 8.
Figure 8 Trie of Figure 7 with 951237635 removed
To remove the element with key 562442169
from the
trie of Figure 8,
we discard the element node C
.
Since its parent node remains the root of a subtrie that has more than
one element, the parent node is not discarded and the removal operation
is complete.
Figure 9 show the resulting trie.
Figure 9 Trie of Figure 8 with 562442169 removed
The time required to remove an element with a d
digit
key from a radix r
trie is O(dr)
because the removal may require
us to discard
O(d)
branch nodes and it takes
O(r)
time to determine whether
a branch node is to be discarded.
The complexity of the remove operation can be reduced to
O(r+d)
by adding a
numberOfElementsInSubtrie
field to each branch node.
Prefix Search and Applications
You have probably realized that to search a trie we do not need the
entire key. Most of the time, only the first few digits (i.e., a prefix)
of the key is needed. For example, our search of the trie of
Figure 2 for an element with
key 951237625
used only the first four digits of the
key. The ability to search a trie using only the prefix of a key enables
us to use tries in applications where only the prefix might be known or where
we might desire the user to provide only a prefix. Some of these applications
are described below.
Criminology
Suppose that you are at the scene of a crime and observe the
first few characters CRX
on the registration plate of the getaway car.
If we have a trie of registration numbers, we can use the characters
CRX
to reach a subtrie that contains all
registration numbers that begin with CRX
.
The elements in this subtrie can then be examined to see which cars
satisfy other properties that might have been observed.
Automatic Command Completion
When using an operating system such as Unix or DOS, we type in
system commands to accomplish certain tasks.
For example, the Unix and DOS command cd
may be used
to change the current directory.
Figure 10 gives a list of commands that have the
prefix ps
(this list was obtained by executing
the command ls /usr/local/bin/ps*
on a Unix system).
ps2ascii ps2pdf psbook psmandup psselect
ps2epsi ps2pk pscal psmerge pstopnm
ps2frag ps2ps psidtopgm psnup pstops
ps2gif psbb pslatex psresize pstruct
Figure 10 Commands that begin with "ps"
We can simply the task of typing in commands by providing a command
completion facility which automatically types in the command suffix
once the user has typed in a long enough prefix to uniquely
identify the command. For instance, once the letters
psi
have been entered, we know that the command
must be psidtopgm
because there is only
one command that has the prefix psi
. In this case,
we replace the need to type in a 9
character
command name by the need to type in just the first 3
characters of the command!
A command completion system is easily implemented when the commands are
stored in a trie using ASCII characters as the digits. As the user types the
command digits from left to right, we move down the trie. The command
may be completed as soon as we reach an element node. If we fall off the trie in
the process, the user can be informed that no command with the typed prefix
exists.
Although we have described command completion in the context
of operating system commands, the facilty is useful in other environments:

A network browser keeps a history of the URLs of sites that
you have visited. By organizing this history as a trie, the user need only type
the prefix of a previously used URL and the browser can complete the URL.

A word processor can maintain a dictionary of words and can complete words
as you type the text. Words can be completed as soon as you have typed a long
enough prefix to identify the word uniquely.

An automatic phone dialler can maintain a list of frequently called telephone
numbers as a trie. Once you have punched in a long enough prefix to uniquely
identify the phone number, the dialler can complete the call for you.
LZW Compression Algorithm
The LZW compression algorithm was developed in Section 7.5 of the text.
Recall that the primary operation performed during compression is the
determination of the longest prefix (of the uncompressed portion of the file
that is begin compressed) for which we have a code in the code table.
Let us call this operation longestPrefix
.
In Section 7.5.2, the code table was implemented
as a hash table and the operation longestPrefix
was performed by searching this hash table first using a prefix of
size 1
, then a prefix of size 2
,
and so on until the first unsuccessful search. Since each hash table search
has an expected complexity of O(1)
,
a longestPrefix
operation takes O(s)
expected time, where s
is the length of the
longest prefix for which we have a code in our code table.
We may use a trie for the code table.
In this application, we add a code
field to
each branch node. The code
field of a branch node
gives the code for the string defined by the path from
the trie root to this branch node.
The trie for LZW codes has no element nodes.
The
longestPrefix
operation may be implemented as follows.
Scan the characters in the uncompressed portion of the file from left to right.
Use these characters to follow a path down the code trie until you fall off
the trie. Once you fall off, the longest matching
prefix is identified, and the code for this prefix is in the
code
field of the
branch node you fell off of.
Using a trie, the actual complexity of
the longestPrefix
operation is O(s)
.
Compressed Tries
Take a close look at the trie of Figure 2. This trie has a few branch nodes
(nodes B, D,
and F
)
that do not partition the elements in their subtrie
into two or
more nonempty groups.
We often can improve both the time and space performance metrics of a trie
by eliminating all branch nodes that have only one child. The resulting
trie is called a compressed trie.
When branch nodes with a single child are removed from a trie, we need to keep
additional information so that dictionary operations may be performed
correctly. The additional information stored in three
compressed trie structures is described below.
Compressed Tries with Digit Numbers
In a compressed trie with digit numbers, each branch node
has an additional field digitNumber
that tells us which
digit of the key is used to branch at this node.
Figure 11 shows the compressed trie with digit numbers that corresponds
to the trie of Figure 2.
The leftmost field of each branch node of Figure 11 is the
digitNumber
field.
Figure 11 Compressed trie with digit numbers
Searching a Compressed Trie with Digit Numbers
A compressed trie with digit numbers may be searched by following a path
from the root. At each branch node, the digit, of the search
key, given in the branch node's
digitNumber
field is used to determine
which subtrie to move to. For example, when searching
the trie of Figure 11
for an element with key 951237625
,
we start at the root of the trie. Since the root node is a branch node
with digitNumber = 1
, we use the first digit
9
of the search key to determine which
subtrie to move to. A move to node A.child[9] = I
is made. Since, I.digitNumber = 4
,
the fourth digit, 2
,
of the search key tells us which subtrie to move to.
A move is now made to node I.child[2] = J
.
We are now at an element node, and the search key is compared with the
key of the element in node J
. Since the
keys match, we have found the desired element.
Notice that a search for an element with key
913237625
also terminates at node
J
. However, the search key
and the element key at node J
do not match
and we conclude that the trie contains no element with key
913237625
.
Inserting into a Compressed Trie with Digit Numbers
To insert an element with key 987261615
into the
trie of Figure 11, we first search for an element with this key.
The search ends at node J
. Since, the
search key and the key, 951237625
,
of the element in this node do not match, we
conclude that the trie has no element whose key matches
the search key. To insert the new element, we find the first digit where
the search key differs from the key in node J
and create a branch node
for this digit. Since, the first digit where the search key
987261615
and the element key
951237625
differ is the second digit,
we create a branch node with digitNumber = 2
.
Since, digit values increase as we go down the trie, the proper place to
insert the new branch node can be determined by retracing the path
from the root to node J
and stopping as soon as
either
a node with digit value greater than 2
or
the node J
is reached.
In the trie of Figure 11, this path retracing stops at node
I
. The new branch node is made the parent of
node I
, and we get the trie of Figure 12.
Figure 12 Compressed trie following the insertion of 987261615 into the compressed trie of Figure 11
Consider inserting an element with key 958364194
into the compressed trie of Figure 11. The search for an element with this
key terminates when we fall of the trie by following the pointer
I.child[3] = null
. To complete the insertion,
we must first find an element in the subtrie
rooted at node I
. This element is found by
following a downward path from node I
using
(say) the first non null
link in each
branch node encountered. Doing this on the compressed trie of
Figure 11, leads us to node J
. Having reached an
element node, we find the first digit where the element key and the
search key differ and complete the insertion as in the previous example.
Figure 13 shows the resulting compressed trie.
Figure 13 Compressed trie following the insertion of 958364194 into the compressed trie of Figure 11
Because of the possible need to search for the first non null
child pointer in each branch node, the time required to insert an element
into a compressed tries with digit numbers is O(rd)
,
where r
is the trie radix and d
is the maximum number of digits in any key.
Removing an Element from a Compressed Trie with Digit Numbers
To remove an element whose key is theKey
, we
do the following:

Find the element node
X
that contains the element whose key is
theKey
.

Discard node
X
.

If the parent of
X
is left with only
one child, discard the parent node also. When the parent of
X
is discarded, the sole remaining child of
the parent of
X
becomes a child of the
grandparent (if any) of X
.
To remove the element with key 951941654
from the compressed trie of Figure 13, we first locate the node
K
that contains the element that is to be removed.
When this node is discarded, the parent I
of K
is left with only one child.
Consequently, node I
is also discarded,
and the only remaining child J
of node
I
is the made a child of the grandparent
of K
.
Figure 14 shows the resulting compressed trie.
Figure 14 Compressed trie following the removal of 951941654 from the compressed trie of Figure 13
Because of the need to determine whether a branch node is left with two
or more children, removing a d
digit
element from a radix r
trie takes
O(d+r)
time.
Compressed Tries with Skip Fields
In a compressed trie with skip fields, each branch node
has an additional field skip
which tells us the
number of branch nodes that were originally between the current
branch node and its parent.
Figure 15 shows the compressed trie with skip fields that corresponds
to the trie of Figure 2.
The leftmost field of each branch node of Figure 15 is the
skip field.
Figure 15 Compressed trie with skip fields
The algorithms to search, insert, and remove are very similar to those
used for a compressed trie with digit numbers.
Compressed Tries with Edge Information
In a compressed trie with edge information, each branch node
has the following additional information associated with it:
a pointer/reference element
to an element (or element node) in the subtrie,
and an integer skip
which equals the number of branch nodes eliminated
between this branch node and its parent.
Figure 16 shows the compressed trie with edge information
that corresponds
to the trie of Figure 2.
The first field of each branch node is its
element
field, and the second field is the
skip
field.
Figure 16 Compressed trie with edge information
Even though we store the ``edge information'' with branch nodes, it is
convenient to think of this information as
being associated with the edge that comes into the branch node from its parent
(when the branch node is not the root). When moving
down a trie, we follow edges, and
when an edge is followed. we skip over the number of digits given by the
skip
field of the edge information. The value of the
digits that are skipped over may be determined by using the
element
field.
When moving from node A
to node I
of the compressed trie of Figure 16, we use digit 1
of the key to determine which child field of A
is to be used. Also, we skip over the next 2
digits,
that is, digits 2
and 3
,
of the keys of the elements in the subtrie rooted at I
.
Since all elements in the subtrie I
have the same
value for the digits that are skipped over, we can determine the value of these
skipped over digits from any of the elements in the subtrie. Using the
element
field of the edge information, we access
the element node J
, and determine that the digits
that are skipped over are 5
and
1
.
Searching a Compressed Trie with Edge Information
When searching a compressed trie with edge information,
we can use the edge information to terminate unsuccessful searches
(possibly) before we reach an element node or fall off the trie.
As in the other compressed trie variants, the search is done by following a path
from the root.
Suppose we are searching
the compressed trie of Figure 16
for an element with key 921231234
.
Since the skip
value for the root node is
0
, we use the first digit
9
of the search key to determine which
subtrie to move to. A move to node A.child[9] = I
is made. By examining the edge information
(stored in node I
),
we determine that, in making the move from node
A
to node I
,
the digits
5
and
1
are skipped.
Since these digits do not agree with the next two digits of the search key,
the search terminates with the conclusion that the trie
contains no element whose key equals the search key.
Inserting into a Compressed Trie with Edge Information
To insert an element with key 987261615
into the
compressed trie of Figure 16, we first search for an element with this key.
The search terminates unsuccessfully when we move from node
A
to node I
because of
a mismatch between the skipped over digits and the corresponding
digits of the search key.
The first mismatch is at the first skipped over digit.
Therefore, we insert a branch node L
between nodes
A
and I
.
The skip
value for this branch node is
0
, and its element
field is set
to reference the element node for the newly inserted element.
We must also change the skip
value of
I
to 1
.
Figure 17 shows the resulting compressed trie.
Figure 17 Compressed trie following the insertion of 987261615 into the compressed trie of Figure 16
Suppose we are to insert an element with key 958364194
into the compressed trie of Figure 16. The search for an element with this
key terminates when we move to node I
because of a mismatch between the digits that are skipped over
and the corresponding digits of the search key.
A new branch node is inserted between nodes
A
and I
and we get
the compressed trie that is shown in Figure 18.
Figure 18 Compressed trie following the insertion of 958364194 into the compressed trie of Figure 16
The time required to insert a d
digit element
into a radix r
compressed trie with edge information
is O(r+d)
.
Removing an Element from a Compressed Trie with Edge Information
This is similar to removal from a compressed trie with digit numbers except
for the need to update the element
fields of
branch nodes whose element
field references
the removed element.
Space Required by a Compressed Trie
Since each branch node partitions the elements in its subtrie into
two or more nonempty groups, an n
element
compressed trie has at most n1
branch nodes.
Therefore, the space required by each of the compressed trie variants
described by us is O(nr)
, where r
is the trie radix.
When compressed tries are represented as hash tables,
we need an additional data structure to store the nonpointer fields of
branch nodes. We may use an array (much like we use the array
information
) for this purpose.
Exercises
Draw the compressed trie with digit numbers for the keys
aabbbbaaa, bbbaaabb, aaabaabb, aaaaabaaa, bbbaabaa,
and aabba
. You will need to append a special
symbol (code class=var>#
to each of the keys.
Draw the information on edge compressed trie for the keys
aabbbbaaa, bbbaaabb, aaabaabb, aaaaabaaa, bbbaabaa,
and aabba
. You will need to append a special
symbol (code class=var>#
to each of the keys.

Develop the class
CompressedTrieWithDigitNumber
which
implements compressed tries with digit numbers.
Use nodes that have as many children fields as the alphabet size plus one
(for the special symol at the end of each key).
You must include methods to search (both exact match and prefix match),
insert, and remove.

Develop the class
CompressedTrieWithDigitNumber
which
implements compressed tries with digit numbers.
Use the hash table scheme.
You must include methods to search (both exact match and prefix match),
insert, and remove.

Develop the class
CompressedTrieWithEdgeInformation
which
implements compressed tries with digit numbers.
Use nodes that have as many children fields as the alphabet size plus one
(for the special symol at the end of each key).
You must include methods to search (both exact match and prefix match),
insert, and remove.

Develop the class
CompressedTrieWithEdgeInformation
which
implements compressed tries with digit numbers.
Use the hash table scheme.
You must include methods to search (both exact match and prefix match),
insert, and remove.
References and Selected Readings
For more information on tries, see the texts:

The Art of Computer Programming: Sorting and Searching,
Second Edition,
by D. Knuth, AddisonWesley, 1998.

Fundamentals of Data Structures in C++, by E. Horowitz, S. Sahni,
and D. Mehta, Computer Science Press, 1995.
In these texts,
the discussion of alternatives to scanning keys from left to right,
external tries, and the data structure Patricia
(practical algorithm for information coded in alphanumeric),
which is a binary trie in which
element nodes are replaced by a single element field in each
branch node is of particular interest.