Tries:Inserting into a Trie
To insert an element the Element whose key is the Key, we first search the trie for an existing element with this key. If the trie contains such an element, then we replace the existing element with the Element. When the trie contains no element whose key equals the Key, the Element is inserted into the trie using the following procedure.
Case 1 For Insert Procedure
If the search for theKey ended at an element node X, then the key of the element in X and theKey are used to construct a subtrie to replace X.
Suppose we are to insert an element with key 271-10-2529 into the trie of Figure 28.1. The search for the key 271-10-2529 terminates at node G and we determine that the key, 271-16-3624, of the element in node G is not equal to the key of the element to be inserted. Since the first three digits of the keys are used to get as far as node E of the trie, we set up branch nodes for the fourth digit (from the left) onwards until we reach the first digit at which the two keys differ. This results in branch nodes for the fourth and fifth digits followed by element nodes for each of the two elements. Figure 28.6 shows the resulting trie.
Case 2 For Insert Procedure
If the search for the Key ends by falling off the trie from the branch node X, then we simply add a child (which is an element node) to the node X. The added element node contains the Element.
Suppose we are to insert an element with key 987-33-1122 to the trie of Figure 28.1. The search for an element with key equal to 987-33-1122 ends when we fall off the trie while following the pointer D.child[8]. We replace the null pointer D.child[8] with a pointer to a new element node that contains the Element, as is shown in Figure 28.7.
The time required to insert an element with a d digit key into a radix r trie is O(dr) because the insertion may require us to create O(d) branch nodes and it takes O(r) time to initialize the children pointers in a branch node.
Comments
Post a Comment