11.2 Lexicographic Search Trees: Tries 1. Tries Definitions pg530 Definition: A trie of order m is either empty or consists of an ordered sequence of exactly m tries of order m
11.2 Lexicographic Search Trees: Tries Definition: A trie of order m is either empty or consists of an ordered sequence of exactly m tries of order m. 1. Tries Definitions pg.530
2 Seach for a Key中再 pg.530 baa Da cab baba
2. Seach for a Key pg.530
3. C++ Tries Declarations pg. 531-532 o Every Record has a Key that is an alphanumeric string Method char key letter(int position returns the character in the given position of the key or returns a blank, if the key has length less than position o Auxiliary function int alphabetic order(char symbol) returns the alphabetic position of the character symbol, or 27 for nonblank, nonalphabetic characters, or 0 for blank characters
3. C++ Tries Declarations pg.531-532 •Every Record has a Key that is an alphanumeric string. •Method char key letter(int position) returns the character in the given position of the key or returns a blank, if the key has length less than position. •Auxiliary function int alphabetic order(char symbol) returns the alphabetic position of the character symbol, or 27 for nonblank, nonalphabetic characters, or 0 for blank characters
const int num chars 28 constructors struct Trie node Record*data Trie_node *branehnum_chars]: e(0) Trie nodel } class Trie I public Trie; bool empty (; Error code trie search(const Key &target, Record &x) const Error code insert(const Record &new entry)
const int num_chars = 28; struct Trie_node { Record *data; Trie_node *branch[num_chars]; Trie_node(); }; data members constructors class Trie { public: Trie(); bool empty(); Error_code trie_search(const Key &target, Record &x) const; Error_code insert(const Record &new_entry);
void inorder( void visit)(Record ) int size int height; void clear(; TrieD void depth traverse(void visit) (Record *) Error code remove(const Key &target) private: Trie node *root: }
void inorder(void (*visit)(Record *)); int size(); int height(); void clear(); ~Trie(); void depth_traverse(void (*visit)(Record *)); Error_code remove(const Key &target); private: Trie_node *root; };