# Tries:Removing an Element

Removing an Element

To remove the element whose key is the Key, we ﬁrst 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 the Element whose key is the Key. The element node X that contains the Element 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 28.7. When the element with key 951-23-7625 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 28.8.

To remove the element with key 562-44-2169 from the trie of Figure 28.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 28.9 show the resulting trie.

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 number Of Elements In Subtrie ﬁeld to each branch node.