CODEWITHSUNDEEP
algorithmdata-structurestreeb-tree
Piyush Kumar
Piyush Kumar

Reputation: 191

difference between m way tree and m way search tree

I tried finding the difference between m way tree and the m way search tree. Most resources only tells about m way search tree and end up being on B tree or B+ trees.

My doubts are:-

Upvotes: 1

Views: 1285

Answers (1)

trincot
trincot

Reputation: 350310

Is it analogous to the binary tree and binary search tree?

Yes

m way trees don't have any particular order

This is true

and every node has to be filled fully before moving to the new node.(complete tree)

Something like this describes a step in an algorithm, and has little to do with the data structure itself: nothing is "moving" in a data structure.

Definitions

In short: an m-way tree puts no conditions on the values stored in the nodes, while an m-way search tree does.

Reva Freedman, associate professor at Northern Illinois University has notes on Multiway Trees where four terms are defined in succession, each time indicating which additional requirements apply for the next term:

  1. multi way tree,
  2. m-way tree
  3. m-way search tree
  4. B-tree of order m

Multiway Trees

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

As with the other trees that have been studied, the nodes in an m-way tree will be made up of key fields, in this case m-1 key fields, and pointers to children.

To make the processing of m-way trees easier, some type of order will be imposed on the keys within each node, resulting in a multiway search tree of order m ( or an m-way search tree). By definition an m-way search tree is a m-way tree in which:

  • Each node has m children and m-1 key fields
  • The keys in each node are in ascending order.
  • The keys in the first i children are smaller than the ith key
  • The keys in the last m-i children are larger than the ith key

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.

B-Trees

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.

A B-tree of order m is a multiway search tree in which:

  • The root has at least two subtrees unless it is the only node in the tree.
  • Each nonroot and each nonleaf node have at most m nonempty children and at least m/2 nonempty children.
  • The number of keys in each nonroot and each nonleaf node is one less than the number of its nonempty children.
  • All leaves are on the same level.

Upvotes: 3

Related Questions