A Practical Guide to Data Structures and Algorithms using Java

Compressed Trie Data Structure 693

DigitizedOrderedCollection

-

-

feed

-

-

-

fee

fee* (3)

-

dab

cab

bad

add

-

* (0)

Figure 43.4

The trie that results when removing dad# from the compressed trie shown in Figure 43.1.

(2)”). Thus, x is removed, making y a child of the root. The resulting compressed trie is shown

in Figure 43.3. Finally, Figure 43.4 shows the compressed trie that results when dad# is removed,

causing its parent also to be removed.

protected void remove(TrieNode<E> node) {

((LeafNode) node).remove(); //preserve OrderedLeafChain

InternalNode parent = (InternalNode) node.parent();

int childIndex = digitizer.getDigit(node.data(), parent.bp());

parent.children[childIndex] ...