Mumbai University > COMPS > Sem 3 > Data Structures

Marks: 5 M

Year: Dec 2014

• A multiway tree is a tree that can have more than two children
• A multiway tree of order m88 (or an **m-way tree) is one in which a tree can have m children.

• An m-way search tree is a m-way tree in which:

  a) Each node has m children and m-1 key fields

  b) The keys in each node are in ascending order.

  c) The keys in the first i children are smaller than the $i^{th}$ key

  d) The keys in the last m-i children are larger than the $i^{th}$ key

• In a binary search tree, m=2. So it has one value and two sub trees.
• The figure above is a m-way search tree of order 3.
• M-way search trees give the same advantages to m-way trees that binary search trees gave to binary trees - they provide fast information retrieval and update.
• However, they also have the same problems that binary search trees had - they can become unbalanced, which means that the construction of the tree becomes of vital importance.
• In m-way search tree, each sub-tree is also a m-way search tree and follows the same rules.
• An extension of a multiway search tree of order m is a B-tree of order m.
• This type of tree will be used when the data to be accessed/stored is located on secondary storage devices because they allow for large amounts of data to be stored in a node.