M way Search Tree

Question

I would like to implement a m-way search tree and i need the basics of implementation of m-way search tree. Can anyone provide me good resources that would help me in implementing the same??

Answer 1

Most m-way search trees work by storing (m-1) keys in sorted order in each node. These values then split elements into m regions: m-2 regions bounded in-between the (m-1) keys, one region smaller than the leftmost key, and one region larger than the largest key. For example, a node in a four-way tree might look like this:

       1              3              7
x < 1    1 < x < 3      3 < x < 7     7 < x

To implement search, you begin in the root of the tree and compare the element to each of the values stored in the node. Based on which group it belongs in, either report that the node is found or descend downward into the appropriate child.

The actual mechanics behind how you insert and delete nodes depends on the type of multiway tree you use, just like how in a binary search tree insertion and deletion vary with the type of tree (AVL, splay, red/black, etc.). A good starting point might be a B-tree, perhaps the most famous of the m-way trees. The famous CLRS textbook has a whole chapter dedicated to the structure, which would be am excellent resource for algorithmic details.

Hope this helps!

Answer 2

Maybe you want to look for a ternary tree? A ternary tree is a trie like data structure but like a patricia trie or a crit-bit tree it uses a B-tree as a type or tree model. A kart-trie is a good starting point, too.