MWayTrees

In-order Traversalsand M -Way Trees : 

In-order Traversalsand M -Way Trees Douglas Wilhelm Harder Department of Electrical and Computer Engineering University of Waterloo Copyright © 2006-8 by Douglas Wilhelm Harder. All rights reserved. ECE 250 Data Structures and Algorithms

In-Order Traversalsand M-Way Trees : 

In-Order Traversalsand M-Way Trees In this topic we will look at: In-order traversals of binary trees Limitations of in-order traversals with n-ary trees Introduction to M-way trees In-order traversals of M-way trees

In-order Traversals : 

In-order Traversals Two depth-first traversals: Pre-order Post-order First and last visits during an Euler walk

In-order Traversals : 

In-order Traversals For binary trees, there is a third intermediate visit An in-order depth-first traversal

In-order Traversals : 

In-order Traversals This visits a binary search tree in order A, B, C, D, E, F, G, H, I, J

In-order Traversals : 

In-order Traversals Printing an expression treee using in-fix notation (3x + 5 + y)(z + 7)

Application : 

Application class Algebraic; void pretty_print( Algebraic * parent ) { if ( !leaf() ) { // If we are printing an operator (not a leaf node) then // we want to print an opening parenthesis if the parent // operator has higher precedence, e.g., // * + // + y -> (x + 5) y * y -> 5x + y // x 5 5 x if ( parent->precedence() > precedence() ) { cout << "("; } // pre-order visit left_tree->pretty_print( this ); // traverse left tree }

Application : 

Application // If we are printing a multiplication, then we will // print a star iff both sub-trees are numeric values, e.g. // * * * // 3 y -> 3y 4 + -> 4(x + 5) 3 5 -> 3*5 // x 5 if ( is_multiplication() ) { if ( left_tree->numeric() && right_tree->numeric() ) { cout << "*"; } } else { cout << this; // print this object }

Application : 

Application if ( !leaf() ) { right_tree->pretty_print( this ); // traverse right sub-tree // If we are printing an operator (not a leaf node) then // we want to print an opening parenthesis if the parent // operator has higher precedence, e.g., // * + // + y -> (x + 5) y * y -> 5x + y // x 5 5 x if ( parent->precedence() > precedence() ) { cout << ")"; } // post-order visit }

M-Way Trees : 

M-Way Trees An in-order traversal does not make sense for general trees The number of visits to a node is one greater than the number of children: ABCDDCBEFFEGGEBAHIJJIKKILLIHMMHA

3-Way Trees : 

3-Way Trees Suppose we had a node storing two values and with three sub-trees: template<class Object> class Three_way_node { Three_way_node *left_tree; Object first_element; Three_way_node *middle_tree; Object second_element; Three_way_node *right_tree; // ... }; left_tree middle_tree right_tree left_element right_element

3-Way Trees : 

3-Way Trees We will require that All sub-trees are 3-way trees The left sub-tree contains items less than the 1st element The middle sub-tree contains items between the two elements The right sub-tree contains items greater than the 2nd element

3-Way Trees : 

3-Way Trees One immediate consequence is that the first element is less than the second Problem: we may not be able to fill both entries in a node: Require that the right sub-tree is empty if the node contains only one element (the first)

3-Way Trees : 

3-Way Trees Suppose we had a node storing two values and with three sub-trees: template<class Object> class Three_way_node { Three_way_node *left_tree; Object first_element; Three_way_node *middle_tree; Object second_element; Three_way_node *right_tree; int num_elements; # 1 or 2 // ... };

3-Way Trees : 

3-Way Trees An example of a 3-way tree:

3-Way Tree : 

3-Way Tree An in-order traversal now makes sense: 1 2 5 6 8 17 19 23 27 38 41 53 59 65 89 94

M-Way Trees : 

M-Way Trees Suppose we had a node storing M – 1 values and with M sub-trees: template<class Object> class M_way_node { private: int M; int num_elements; Object *elements; M_way_node **subtrees; // for an array of M pointers to M-way nodes public: // ... };

M-Way Trees : 

M-Way Trees template<class Object> M_way_node<Object>::M_way_node( const Object &obj, int m ): M( m ), num_elements( 1 ), elements( new Object[M – 1] ), subtrees( new M_way_node<Object> *[M] ) { elements[0] = obj; for ( int i = 0; i < M; ++i ) { subtrees[i] = 0; } }

M-Way Trees : 

M-Way Trees Question: What is the maximum number of elements which may be stored in an M-way tree of height h? Consider the 3-way trees and, if possible, generalize

M-Way Trees : 

M-Way Trees Examining these perfect 3-way trees we get the table:

M-Way Trees : 

M-Way Trees Suggested form: The maximum number of nodes in a perfect M-way tree of height h is Mh + 1 – 1 Observations This is true when M = 2: 2h + 1 – 1 To prove that this is true in general, we will first make use of one fact...

M-Way Trees : 

M-Way Trees We will require the following: the maximum number of leaf nodes in anM-way tree of height h is Mh Proof (by induction): when h = 0, there is M0 = 1 node (a leaf node) assume for h = k that there are Mk leaf nodes for h = k + 1, each leaf node has M children: Mk M = Mk + 1 Q.E.D.

M-Way Trees : 

M-Way Trees Similarly, we will show that the maximum number of elements which may be stored in M-way tree of height h is First, when h = 0, the formula is M1 – 1 which is the maximum number of elements a single node can store

M-Way Trees : 

M-Way Trees We will assume the statement is true forh = k, that is, the maximum number of elements is Mk + 1 – 1 A tree of height h = k has Mk leaf nodes, and therefore, if each of these have the maximum number of children (M), we therefore have M·Mk leaf nodes, each of which stores M – 1 elements

M-Way Trees : 

M-Way Trees Therefore, the maximum number of elements stored is in a tree of heighth = k + 1 is: the total number of elements stored in a tree of height h = k plus M – 1 for each possible sub-tree of each leaf node of height h = k That is, Mk + 1 – 1 + MMk(M – 1) = Mk + 1 – 1 + Mk + 2 – Mk + 1 – 1 = Mk + 2 – 1

M-Way Trees : 

M-Way Trees Thus, the statement must be true for allh > 0 One nice consequence is that the minimum height of an M-way tree which stores n elements is given by ?logM(n)?

M-Way Trees : 

M-Way Trees An M-way tree has the following properties: each node has k elements where 1 = k < M and e0 < ··· < ek - 1 each node has at most one k + 1 sub-trees T0, T1, ..., Tk such that: all elements e in the sub-tree T0 satisfy e < e0, all elements e in Tj ( j = 1, ..., k – 1) satisfy: ej – 1 < e < ej all elements e in the sub-tree Tk satisfy e > ek – 1

M-Way Trees : 

M-Way Trees Observations we require that the elements in a given node are filled in order intermediate trees may be empty a binary search tree is a 2-way tree the minimum depth of an M-way tree with n nodes is logM( n + 1 ) – 1 potentially much less depth than a binary tree

M-Way Trees : 

M-Way Trees Most keys are stored in the leaves Mh leaves A total of M – 1 keys per leaf Thus (M – 1)Mh/(Mh + 1 – 1) ˜ (M – 1)/M

M-Way Trees : 

M-Way Trees A plot of the minimum height of an M-way tree for M = 2, 3, ..., 20 for up to one-million elements

M-Way Trees : 

M-Way Trees Compare: A perfect 6-way tree with h = 2 215 elements in 43 nodes A complete binary tree with n = 215 and h = 7

M-Way Trees : 

M-Way Trees Advantage: Shorter paths from the root Disadvantage: More complex Under what conditions is the additional complexity worth the effort? When the cost from jumping nodes is exceptionally dominant

Summary : 

Summary In this topic, we have looked at: In-order depth-first traversals Limitations on n-ary trees M-way trees

Usage Notes : 

Usage Notes These slides are made publicly available on the web for anyone to use If you choose to use them, or a part thereof, for a course at another institution, I ask only three things: that you inform me that you are using the slides, that you acknowledge my work, and that you alert me of any mistakes which I made or changes which you make, and allow me the option of incorporating such changes (with an acknowledgment) in my set of slides Sincerely, Douglas Wilhelm Harder, MMath dwharder@alumni.uwaterloo.ca