## Data Structure Name: Trie - #### Description: - Special form of n-ary tree, which is typically used to store strings. Each Trie node represents a string (a prefix).  Each node might have several children nodes while the paths to the different nodes represent different characters.  The strings the child nodes represent will be these origin string represented by the nodes itself plus the character on the path/ - #### Variations: - #### Diagram: - #### General Use: - Typeahead Search, Autocomplete, Spell Checker ## Key Considerations - #### Properties: - #### Implementation Details: - Can be implemented with: - Array - fast, but wastes space - Hashmap - slowed than array, but saves space - Insertion - Check each level of the Trie and determine if a new character needs to be inserted - Search - Search Prefix - Search down root looking for characters in the prefix - This is the "magic" of the tree - Search Word - Mark a node as "end of word" using Boolea | | [[Big O - Time Complexity]] | [[Big O - Space Complexity]] | | ------ | --------------------------- | ---------------------------- | | Access | | | | Add | | | | Delete | | | | Search | | | - #### General Tips - #### Special Properties ## Specific Use Cases - TBD