I was reading through How to Solve it by Computer however, couldn’t find anything on trie. A mechanism to search for and insert strings. Following from other search tree data structures we will build a search tree. I've taken Sedgewick's algorithm book for reference.
Basic properties
Root does not have any character key as well as value in it unlike other nodes that have characters associated with it.
Basic properties
Root does not have any character key as well as value in it unlike other nodes that have characters associated with it.
We will describe the technique by which an R-way trie operates. The string for example we have “she sells sea shells by the sea shore”. The last character of the key has a value associated with the node. This is usually the index of the key within the original string. For instance, the key she will have the value as “0” on the last node having the last key character, in this case “e”.
Searching
For searching, we follow all the characters in the key and return the value corresponding to it in order to indicate the search succeeded otherwise a null value at the end indicates that the key does not exist within the trie. With this out of the way let’s see how code would look like:
Insertion
To insert any key we first and foremost search within the trie. If it doesn’t exist we create a new start node and move ahead similarly.
Deletion
Deletion works by traversing to the value of the last key character and if at all found remove that node. And go backwards and delete nodes until you find a node that has a corresponding value.
Other key operations among others
keysWithPrefix – This will return a queue with similar keys that matches the input key
Advantages
Use trie when search should include prefixes otherwise a hash table would suffice.
Searching
For searching, we follow all the characters in the key and return the value corresponding to it in order to indicate the search succeeded otherwise a null value at the end indicates that the key does not exist within the trie. With this out of the way let’s see how code would look like:
Insertion
To insert any key we first and foremost search within the trie. If it doesn’t exist we create a new start node and move ahead similarly.
Deletion
Deletion works by traversing to the value of the last key character and if at all found remove that node. And go backwards and delete nodes until you find a node that has a corresponding value.
Other key operations among others
keysWithPrefix – This will return a queue with similar keys that matches the input key
Advantages
Use trie when search should include prefixes otherwise a hash table would suffice.
No comments:
Post a Comment