Question? Leave a message!




Multiway Search Trees

Multiway Search Trees
ECE 250 Algorithms and Data Structures Multiway Search Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering Trees University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Multiway search trees 2 Outline In this topic we will look at: – An introduction to multiway search trees – An implementation in C++ – Inorder traversals of multiway treesMultiway search trees 3 6.4.1 Inorder traversals on general trees We have noted that inorder traversals only make sense for binary search trees and not Nary trees in generalMultiway search trees 4 6.4.2 3Way Trees Suppose we had a node storing two values and with three subtrees:Multiway search trees 5 6.4.2 3Way Trees This could be implemented as follows: template typename Type class Threewaynode Threewaynode lefttree; Type firstelement; Threewaynode middletree; Type secondelement; Threewaynode righttree; // ... ; leftelement rightelement middletree lefttree righttreeMultiway search trees 6 6.4.2 3Way Trees In order to define a search tree, we will require that: – The first element is less than the second element – All subtrees are 3way trees st – The left subtree contains items less than the 1 element – The middle subtree contains items between the two elements nd – The right subtree contains items greater than the 2 element leftelement rightelement middletree lefttree righttreeMultiway search trees 7 6.4.2 3Way Trees If a node has only one element, all trees are assumed to be empty – If a second object is inserted, it will be inserted into this node template typename Type class Threewaynode Threewaynode lefttree; Type firstelement; Threewaynode middletree; Type secondelement; Threewaynode righttree; int numelements; 1 or 2 // ... ; template typename Type bool Threewaynode::full() const return numelements == 2; Multiway search trees 8 6.4.2.1 3Way Trees Most operations are more complex than with binary trees… template typename Type bool ThreewaynodeType::find( Type const obj ) const if ( empty() ) return false; else if ( full() ) return ( first() == obj ); if ( obj first() ) return left()find( obj ); else if ( obj == first() ) return true; else if ( obj first() obj second() ) return middle()find( obj ); else if ( obj == second() ) return true; else return right()find( obj ); Multiway search trees 9 6.4.2.1 3Way Trees Insertion also becomes much more interesting template typename Type bool ThreewaynodeType::insert( Type const obj, ThreewaynodeType ptrtothis ) if ( empty() ) ptrtothis = new Threewaynode( obj ); return true; if ( full() ) if ( obj == first() ) return false; else if ( obj first() ) secondelement = first(); firstelement = obj; else secondelement = obj; numelements = 2; return true; Multiway search trees 10 6.4.2.1 3Way Trees if ( obj == first() obj == second() ) return false; if ( obj first() ) return left()insert( obj ); else if ( obj second() ) return right()insert( obj ) ; else return middle()insert( obj ); Erasing an element is even more complex – There are many more cases to considerMultiway search trees 11 6.4.2.2 Insertion into 3Way Trees Consider inserting values into an empty 3way tree: – Starting with 68, it would be inserted into the rootMultiway search trees 12 6.4.2.2 Insertion into 3Way Trees If 27 was inserted next, it would be fit into the root nodeMultiway search trees 13 6.4.2.2 Insertion into 3Way Trees If 27 was inserted next, it would be fit into the root nodeMultiway search trees 14 6.4.2.2 Insertion into 3Way Trees Any new insertion would create an appropriate subtree – Inserting 91, we note that 91 68, so a right subtree is constructedMultiway search trees 15 6.4.2.2 Insertion into 3Way Trees Any new insertion would create an appropriate subtree – Inserting 91, we note that 91 68, so a right subtree is constructedMultiway search trees 16 6.4.2.2 Insertion into 3Way Trees If we insert 38, we note that 28 38 68 and thus build a new sub tree in the middleMultiway search trees 17 6.4.2.2 Insertion into 3Way Trees If we insert 38, we note that 28 38 68 and thus build a new sub tree in the middleMultiway search trees 18 6.4.2.2 Insertion into 3Way Trees At this point, if we insert 82, we note 82 68 and the right subtree is not yet fullMultiway search trees 19 6.4.2.2 Insertion into 3Way Trees At this point, if we insert 82, we note 82 68 and the right subtree is not yet fullMultiway search trees 20 6.4.2.2 Insertion into 3Way Trees If we insert 14, we note 14 27, so we create a new nodeMultiway search trees 21 6.4.2.2 Insertion into 3Way Trees If we insert 14, we note 14 27, so we create a new nodeMultiway search trees 22 6.4.2.2 Insertion into 3Way Trees Next, inserting 62, 27 62 28 so we insert it into the middle sub tree which also is not fullMultiway search trees 23 6.4.2.2 Insertion into 3Way Trees Next, inserting 62, 27 62 28 so we insert it into the middle sub tree which also is not fullMultiway search trees 24 6.4.2.2 Insertion into 3Way Trees If we insert 45, – First, 27 45 68 and then 38 45 62Multiway search trees 25 6.4.2.2 Insertion into 3Way Trees If we insert 45, – First, 27 45 68 and then 38 45 62Multiway search trees 26 6.4.2.2 Insertion into 3Way Trees If we insert 76, we note 68 76 but then 76 82 – Create a new left subtree of the 8291 nodeMultiway search trees 27 6.4.2.2 Insertion into 3Way Trees If we insert 76, we note 68 76 but then 76 82 – Create a new left subtree of the 8291 nodeMultiway search trees 28 6.4.2.2 Insertion into 3Way Trees If we insert 4, 4 27 and the left subtree contains only a single elementMultiway search trees 29 6.4.2.2 Insertion into 3Way Trees If we insert 4, 4 27 and the left subtree contains only a single elementMultiway search trees 30 6.4.2.2 Insertion into 3Way Trees If we insert 51, 27 51 68 and 38 51 62; therefore, we insert 51 into the node containing 45Multiway search trees 31 6.4.2.2 Insertion into 3Way Trees If we insert 51, 27 51 68 and 38 51 62; therefore, we insert 51 into the node containing 45Multiway search trees 32 6.4.2.2 Insertion into 3Way Trees If we insert 8, 8 27 and then 4 8 14 – Construct a new middle subtree of the 414 nodeMultiway search trees 33 6.4.2.2 Insertion into 3Way Trees If we insert 8, 8 27 and then 4 8 14 – Construct a new middle subtree of the 414 nodeMultiway search trees 34 6.4.2.2 Insertion into 3Way Trees If we insert 98, 98 68 and 98 91 – Construct a new right subtree of the 8191 nodeMultiway search trees 35 6.4.2.2 Insertion into 3Way Trees If we insert 98, 98 68 and 98 91 – Construct a new right subtree of the 8191 nodeMultiway search trees 36 6.4.2.2 Insertion into 3Way Trees Finally, consider adding 57: – 27 57 68, 38 57 62 and 57 51 – Construct a new right subtree of the 4551 nodeMultiway search trees 37 6.4.2.2 Insertion into 3Way Trees Finally, consider adding 57: – 27 57 68, 38 57 62 and 57 51 – Construct a new right subtree of the 4551 nodeMultiway search trees 38 6.4.2.1 Inorder Traversals Insertion also becomes much more interesting template typename Type void ThreewaynodeType::inordertraversal() const if ( empty() ) return; if ( full() ) cout first(); else left()inordertraversal(); cout first(); middle()inordertraversal(); cout second(); right()inordertraversal(); Multiway search trees 39 6.4.2.3 Inorder Traversals An inorder traversal can be performed on this tree: 4 8 14 27 38 45 51 57 62 68 76 82 91 98Multiway search trees 40 6.4.3 Multiway tree implementation Suppose we had a node storing N– 1 values and with N subtrees – We will describe this as an Nway tree template typename Type, int N class Multiwaynode private: int numelements; Type elementsN – 1; Multiwaynode N; // an array of pointers to multiway nodes public: Multiwaynode( Type const ); // ... ; templatetypename Type, int M bool M waynodeType, M::full() const return ( numelements == M 1 ); Multiway search trees 41 6.4.3 Multiway tree implementation The constructor would initial the node to store one element template typename Type, int N MultiwaynodeType, N::Multiwaynode( Type const obj ): numelements( 1 ) elements0 = obj; // All subtreees are null subtrees for ( int i = 0; i N; ++i ) subtreesi = nullptr; Multiway search trees 42 6.4.3 Multiway tree implementation An inorder traversal would be similar: template typename Type, int N void MultiwaynodeType, N::inordertraversal() const if ( empty() ) return; else if ( full() ) for ( int i = 0; i numelements; ++i ) cout elementsi; else for ( int i = 0; i N 1; ++i ) subtreesiinordertraversal(); cout elementsi; subtreesN 1inordertraversal(); Multiway search trees 43 6.4.3.1 Size Question: – What is the maximum number of elements which may be stored in a multiway tree of height h We will consider 3way trees and, if possible, generalizeMultiway search trees 44 6.4.3.1 Size Examining these perfect 3way trees we get the table: h Size Formula 1 0 2 3– 1 2 1 8 3– 1 3 2 26 3– 1 4 3 80 3– 1Multiway search trees 45 6.4.3.1 Size Suggested form: – The maximum number of nodes in a perfect multiway tree h + 1 of height h is N– 1 Observations h + 1 – This is true when N = 2: 2– 1 To prove this, we need only observe: h1 N1 – A perfect Nary tree of height h has nodes N1 – Thus, if each node now has N– 1 elements: h1 N1 h1 NN11  N1Multiway search trees 46 6.4.3.2 Size Note also that the majority of elements are in the leaf nodes: h – There are N leaf nodes in a perfect Mway search tree of height h – Each of these stores N– 1 elements Thus, we may calculate the ratio hh N N 11 N N  N1  hh  11 N1 N N For example: – In an 8way search tree, 87.5 of elements are in leaf nodes – In a 100way search tree, 99 of elements are in the leaf nodes Multiway search trees 47 6.4.3.3 Minimum height The minimum height of a multiway tree storing n elements is ⌊log (n)⌋ N – For large N, the depth is potentially much less than a binary tree – A plot of the minimum height of a multiway tree for N = 2, 3, ..., 20 for up to onemillion elementsMultiway search trees 48 6.4.3.3 8way trees versus binary trees Compare: – A perfect 8way tree with h = 2 • 511 elements in 73 nodes – A perfect binary tree with h = 8 • 511 elements in 511 nodesMultiway search trees 49 6.4.3.4 8way tree example A sample 8way search tree: – Note how a binary search is required to find the appropriate subtree – How do you determine if 43 is in this search tree – Question: what order would these entries have been inserted – How do we erase an elementMultiway search trees 50 6.4.3.4 Multiway 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 dominantMultiway search trees 51 Summary In this topic, we have looked at: – Multiway trees • Each node stores N– 1 sorted elements • N subtrees interleave the elements h +1 • Perfect Multiway trees store N– 1 elements – We saw an implementation in C++ – We considered inorder traversals of multiway trees – Has the potential to store more elements in shallower treesMultiway search trees 52 References 1 Cormen, Leiserson, and Rivest, Introduction to Algorithms, MIT Press, 1990, §7.13, p.152. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §6.56, p.21525.Multiway search trees 53 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 dwharderalumni.uwaterloo.ca