M ary-tree

An important topic of discrete Mathematics.
#M_ARY_TREE.

1. M–ary Tree Presented By: Md. Arif Hasan – BSSE1112 Tahmeed Mahbub – BSSE1127 Tasmia Zerin – BSSE1128

2. Balanced Tree B Tree General Tree M – ary Tree Where is M-ary tree in the tree of TREEs ? AVL Tree Red/ Black Tree B+ Tree Here I am! Binary Tree 1.

3. What is M-ary Tree ? A rooted tree is called an m-ary tree if every internal vertex has no more then m children. Types of m-ary tree: A full m-ary tree is an m-ary tree where within each level every node has either 0 or m children . A complete m-ary tree is an m-ary tree which must be completely filled on every level except for the last level. However, if the last level is not complete, then all nodes of the tree must be as far left as possible . A perfect m-ary tree is a full m-ary tree in which all leaf nodes are at the same depth . 1 2 3 m Internal Vertices 2.

4. Properties of m-ary tree : A full m-ary tree with i internal vertices contains n= m i + 1 vertices and l=(m-1)i+1 leaves i = 4 internal vertices m = 3 n = 3 x 4 + 1 = 13 vertices, as 12 vertices (except the root) are children of those 4 internal vertices So, children = m x i = 4 x 3 = n – 1 n = l + i => l = (m-1)i + 1 l = 2 x 4 + 1 = 9 leaves Internal Vertices 3.

5. The children of m-ary tree : Binary Tree M – ary Tree Ternary Tree M = 2 M = 3 Yes, I’m the parent of all 1,2,3…… ary trees 4.

6. Traversal Methods for m-ary tree : Traversing a  m -ary tree is very similar to binary tree traversal. But since there are more than two children per node for  m > 2 , one must define the notion of  left  and  right  subtrees. One common method to establish left/right subtrees is to divide the list of children nodes into two groups.By defining an order on the m children of a node, the first {0,1,…. └ m/2 ┘ } nodes would constitute the left subtree and { ┌ m/2 ┐ ,…..,m} would constitute the right subtree. 5.

7. Left Subtree Right Subtree Here, for m = 3, left subtree will be { 0, 1 } (as 3/2 = 1) and right subtree will be { 2 } For Example : 6.

8. Methods of Storing m-ary trees : Arrays: if the tree is a complete  m -ary tree, this method wastes no space. In this compact arrangement, if a node has an index  i , its  c -th child in range {1,..., m } is found at index m.i + c. The space complexity of this method is O ( m n ) A B C D E F G A D C B E G F 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 7.

9. Pointer Based: Each node would have an internal array for storing pointers to each of its m children. Compared to array-based implementation, this implementation method has superior space complexity of O (m.n) 8.

10. Convert a m-ary tree to binary tree : Converting an arbitrary  m- ary tree to a binary tree would only increase the height of the tree by a constant factor and would not affect the overall worst-case time complexity. First, we link all the immediate children nodes of a given parent node together in order to form a link list. Then, we keep the link from the parent to the first (i.e., the leftmost) child and remove all the other links to the rest of the children. We repeat this process for all the children (if they have any children) until we have processed all the internal nodes and rotate the tree by 45 degrees clockwise. The tree obtained is the desired binary tree obtained from the given  m -ary tree. 9.

11. A G E B C J I F K D H O N L M P Q G B C F D E A J I H K L P Q M O N G B C F D E A J I H K L P O M O N A C J I F K D H O N M P E L G B Q Converting m-ary to binary tree 10.

12. Thank You