Friday, May 7, 2010 | By: Kunal Ekawde

Radix Patricia and Ternary datastructures

The efficiency of the process depends on the data structures and operations used in it. I had a chance to visit and implement Radix trie, Patricia trie and Ternary search trees.

Radix trie mostly associated with numeric data works on bit string representation of the key. Every node has a index set based on the difference of first bit encountered with previous key. Every next insert this bit position is checked for: if greater -> traverse right, else ->traverse left. Then set its bit position.

Patricia trie mostly associated with alphanumeric data works same as radix trie with one way branching removed(standard definition on internet). I shall post the implementation soon.

Ternary search tree also supports alpha numeric data set, with a each node having pointers to 3 nodes:right, left and equal. The full word comes under equal, if the character compared is greater, it becomes right node else left node. Although you may find insert and find operations, delete was not available on internet.

Here is the my current implementation and invitation to let me know bugs: