Insertion

###Insertion Algorithm

• Stage 1 of the search algorithm above is used to identify the container in which the recordshould be inserted. This container, which can be empty, is at depth k.For the special case of arriving at a trie node at depth k = n + 1, the container is underthe empty-string pointer
• If k ≤ n, the standard insertion algorithm for the container data structure is used to addthe record to the container, using only the suffix characters ck+1 ··· cn. Otherwise, therecord is added under the empty-string pointer