Question? Leave a message!




Multiway Search Trees

Multiway Search Trees
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
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 © 2006-2013 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++ – In-order traversals of multiway treesMultiway search trees 3 6.4.1 In-order traversals on general trees We have noted that in-order traversals only make sense for binary search trees and not N-ary trees in generalMultiway search trees 4 6.4.2 3-Way Trees Suppose we had a node storing two values and with three sub-trees:Multiway search trees 5 6.4.2 3-Way Trees This could be implemented as follows: template typename Type class Three_way_node Three_way_node left_tree; Type first_element; Three_way_node middle_tree; Type second_element; Three_way_node right_tree; // ... ; left_element right_element middle_tree left_tree right_treeMultiway search trees 6 6.4.2 3-Way Trees In order to define a search tree, we will require that: – The first element is less than the second element – All sub-trees are 3-way trees st – The left sub-tree contains items less than the 1 element – The middle sub-tree contains items between the two elements nd – The right sub-tree contains items greater than the 2 element left_element right_element middle_tree left_tree right_treeMultiway search trees 7 6.4.2 3-Way 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 Three_way_node Three_way_node left_tree; Type first_element; Three_way_node middle_tree; Type second_element; Three_way_node right_tree; int num_elements; 1 or 2 // ... ; template typename Type bool Three_way_node::full() const return num_elements == 2; Multiway search trees 8 6.4.2.1 3-Way Trees Most operations are more complex than with binary trees… template typename Type bool Three_way_nodeType::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 3-Way Trees Insertion also becomes much more interesting template typename Type bool Three_way_nodeType::insert( Type const &obj, Three_way_nodeType &ptr_to_this ) if ( empty() ) ptr_to_this = new Three_way_node( obj ); return true; if ( full() ) if ( obj == first() ) return false; else if ( obj first() ) second_element = first(); first_element = obj; else second_element = obj; num_elements = 2; return true; Multiway search trees 10 6.4.2.1 3-Way 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 3-Way Trees Consider inserting values into an empty 3-way tree: – Starting with 68, it would be inserted into the rootMultiway search trees 12 6.4.2.2 Insertion into 3-Way Trees If 27 was inserted next, it would be fit into the root nodeMultiway search trees 13 6.4.2.2 Insertion into 3-Way Trees If 27 was inserted next, it would be fit into the root nodeMultiway search trees 14 6.4.2.2 Insertion into 3-Way Trees Any new insertion would create an appropriate sub-tree – Inserting 91, we note that 91 68, so a right sub-tree is constructedMultiway search trees 15 6.4.2.2 Insertion into 3-Way Trees Any new insertion would create an appropriate sub-tree – Inserting 91, we note that 91 68, so a right sub-tree is constructedMultiway search trees 16 6.4.2.2 Insertion into 3-Way 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 3-Way 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 3-Way Trees At this point, if we insert 82, we note 82 68 and the right sub-tree is not yet fullMultiway search trees 19 6.4.2.2 Insertion into 3-Way Trees At this point, if we insert 82, we note 82 68 and the right sub-tree is not yet fullMultiway search trees 20 6.4.2.2 Insertion into 3-Way Trees If we insert 14, we note 14 27, so we create a new node