I am developing a Trie
data-structure where each node represents a word. So words st
, stack
, stackoverflow
and overflow
will be arranged as
root
--st
---stack
-----stackoverflow
--overflow
My Trie uses a HashTable
internally so all node lookup will take constant time. Following is the algorithm I came up to insert an item into the trie.
- Check item existence in the trie. If exist, return, else goto step2.
- Iterate each character in the
key
and check for the existence of the word. Do this until we get a node where the new value can be added as child. If no node found, it will be added under root node. - After insertion, rearrange the siblings of the node under which the new node was inserted. This will walk through all the siblings and compare against the newly inserted node. If any of the node starts with same characters that new node have, it will be moved from there and added as child of new node.
I am not sure that this is the correct way of implementing a trie. Any suggestions or improvements are welcome.
Language used : C++