4. Searching a Tries M Terminate search Move to Errfor a NULL location bearch(cons the next character )&x) of the target /* Post: If t arch is successful oI success is retur l and the output Ler x is set as a copy he Trie' s recor olds target Other wi、, a code of sent is returned Uses: Methbds f classy i int position=0; ch/ Aex' char; Trie node *location root; while(location =/OLL &,/ (next_chftarget/key_letter(position))I=") I location=lgcation->branch[alphabetic_order(next_char)l position++
4. Searching a Tries pg.532 Error_code Trie::trie_search(const Key &target, Record &x) /* Post: If the search is successful, a code of success is returned, and the output parameter x is set as a copy of the Trie's record that holds target. Otherwise, a code of not_present is returned. Uses: Methods of class Key. */ { int position = 0; char next_char; Trie_node *location = root; while (location != NULL && (next_char=target.key_letter(position)) != ' ') { location=location->branch[alphabetic_order(next_char)]; position++; } indexes letters of key Terminate search for a NULL location Terminate search for a blank in the target Move down the appropriate branch of the trie Move to the next character of the target
if contin NULL & location->data != NULL) Create a new empty Trie ) data); return success eu rot present 5. Insertion to a Tries pg.533 Error_code Trie nsert(const Record &new_entry) / Post: If the Key pf new_entry is already in the Trie, a code of\ Plicate_error is returned Otherwise, code of success is returned and the Record N ew_entry is inserted into the Trie Uses: Methods of classes Record and Trie_node. * Error_code result=success; if (root==NULL) root new Trie node
if (location != NULL && location->data != NULL) { x = *(location->data); return success; } else return not_present; } 5. Insertion into a Tries pg.533 Error_code Trie::insert(const Record &new_entry) /* Post: If the Key of new_entry is already in the Trie, a code of duplicate_error is returned. Otherwise, a code of success is returned and the Record new_entry is inserted into the Trie. Uses: Methods of classes Record and Trie_node.*/ { Error_code result = success; if (root==NULL) root = new Trie_node; Create a new empty Trie
int position = 0; char next char, At this poin Trie node *location= root; we have tested while(location ! NULL && for all non blank characters of (next_char=target key_letter new_entry k int next_position alph border(next_char) if(location->branchl position]== NULL location->bra nexp sition]=new Trie_node location koation->bran\xtposition position if(location->data NULL)result icate_error else location->data= new Record(n& \ntry); return result. moves through the trie
int position = 0; char next_char; Trie_node *location = root; while (location != NULL && (next_char=target.key_letter(position)) != ' ') { int next_position = alphabetic_order(next_char); if (location->branch[next_position] == NULL) location->branch[next_position]=new Trie_node; location = location->branch[next_position]; position++; } if (location->data != NULL) result = duplicate_error; else location->data = new Record(new_entry); return result; } indexes letters of new_entry moves through the Trie At this point, we have tested for all non blank characters of new_entry
The number of steps required to search a trie or insert into it is proportional to the number of characters making up a key, not to a logarithm of the number of keys as in other tree-based searches
The number of steps required to search a trie or insert into it is proportional to the number of characters making up a key, not to a logarithm of the number of keys as in other tree-based searches
6. Deletion from a tries pg533 Error code Trie: trie search(const Key &target, Record &x) /* Post: If the search is successful a code of success is returned, and the output parameter x is set as a copy of the Tries record that holds target. Otherwise, a code of not_ present is returned. Uses: Methods of class Key. * I int position =0; char next char, Trie node location root: while(location E NULL & (next char=target key letter(position))=) I location=location->branch[alphabetic order(next char)]; position++
6. Deletion from a Tries pg.533 Error_code Trie::trie_search(const Key &target, Record &x) /* Post: If the search is successful, a code of success is returned, and the output parameter x is set as a copy of the Trie's record that holds target. Otherwise, a code of not_present is returned. Uses: Methods of class Key. */ { int position = 0; char next_char; Trie_node *location = root; while (location != NULL && (next_char=target.key_letter(position)) != ' ') { location=location->branch[alphabetic_order(next_char)]; position++; }