NIST defines Trie as “A tree for storing strings in which there is one node for every common prefix. The strings are stored in extra leaf nodes”. So, it’s a way of storing and retrieving information that is stored in order or un-ordered lists or pigeonholes.
A trie (Fredkin, 1960), also called digital tree and sometimes radix tree, is an ordered multi-way tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are not necessarily associated with every node. Rather, values tend only to be associated with leaves, and with some inner nodes that correspond to keys of interest.
Trie data structure is mainly used for sorting (by using preorder traversal) and searching (by using suffix tree).
Trie Example
For example, in the case of alphabetical keys, each node has an array of (27) pointers to its branches, one for each of the 26 alphabet characters and one for blank (” “). The keys are stored in leaf nodes called information nodes. To access an information node containing a key, we need to move down a series of branch nodes follow appropriate branch based on the alphabetical characters composing the key. All trie_node fields that neither intern node nor to an leaf node are represented using null pointers.
To access these information nodes, we follow a path beginning from a branch node moving down each level forming the key, until the appropriate information node holding the key is reached. Thus the depth of an information node in a trie depends on the similarity of its first few characters fellow keys. Here, while AEROPLANE and TRAIN occupy shallow levels (level 1 branch node) in the Trie, CAR, CARRIAGE, CARAVAN have moved down by 4 levels of branch nodes due to their uniform prefix “CAR”. Observe how we move down each lev level of the branch node with the help of the characters forming the key. The role played by the blank field in the branch node is evident when we move down to access CAR. While the information node pertaining to CAR positions itself under the blank field, those of CARAVAN and CARRIAGE attach themselves to pointers from A to R respectively of the same branch node.
Usage of Trie
- Trie is much more efficient data structure than BST (Binary Search Tree) and hashing because we do not need to calculate any hash. We can add and search strings in o(l) time. Here l represents the length of a single word.
- Another bigger advantage Trie is that we can sort string data easily without calculating hash.
- Tries are more useful where we have a fixed dictionary of strings and you want to look up quickly.
Bitwise/Binary Trie
Bitwise Tries are much the same as a normal character-based trie except that individual bits are used to traverse what effectively becomes a form of binary tree. We could start with the most significant or least significant bit, depending on the kind of numbers we expect. In this case every node would have at most two successors, one for 0 and one for 1. This does not waste nearly as much space and can be efficient for many purposes.
Only leaf nodes hold the key in binary trie.
There are many other advance data structures you can use in solving your complex problems. For example, Binary Decision Diagram is mainly used for taking concrete decisions such as yes or no. Binary Trees are mainly used for searching and sorting as they provide a means to store data hierarchically.