# BST Class Template - Florida State University

Trees 3: The Binary Search Tree Reading: Sections 4.3 and 4.6 1 Binary Search Tree Also known as Totally Ordered Tree Definition: A binary tree B is called a binary search tree iff: There is an order relation < defined for the vertices of B For any vertex v, and any descendant u of v.left, u < v For any vertex v, and any descendent w of v.right, v < w root 1 4

2 6 3 5 7 2 Binary Search Tree Which one is NOT a BST? 3

Binary Search Tree Consequences: The smallest element in a binary search tree (BST) is the leftmost node The largest element in a BST is the right-most node Inorder traversal of a BST encounters nodes in increasing order root 1 4 2 6 3

5 7 4 Binary Search using BST Assumes nodes are organized in a totally ordered binary tree Begin at root node Descend using comparison to make left/right decision if (search_value < node_value) go to the left child else if (search_value > node_value) go to the right child else return true (success) Until descending move is impossible Return false (failure)

5 Binary Search using BST Runtime <= descending path length <= depth of tree If tree has enough branching, runtime <= O(log size) 6 BST Class Template Template Class BinarySearchTree {

public: BinarySearchTree(); BinarySearchTree(const BinarySearchTree & rhs); BinarySearchTree(BinarySearchTree &&rhs); ~BinarySearchTree(); // copy // move const Comparable & findMin() const; const Comparable & findMax() const; bool contains(const Comparable &x) const; bool isEmpty() const; void printTree(ostream & out = std::cout) const; void makeEmpty(); void insert(const Comparable &x); void insert(Comparable &&x);

void remove(const Comparable &x); // move BinarySearchTree & operator=(const BinarySearchTree &rhs); BinarySearchTree & operator=(BinarySearchTree && rhs); // move 7 BST Class Template (Contd) private: struct BinaryNode { Comparable element; BinaryNode *left; BinaryNode *right; BinaryNode(const Comparable &theElement, BinaryNode *lt, BinaryNode *rt)

: element{theElement}, left{lt}, right{rt} {} BinaryNode(Comparable && theElement, BinaryNode *lt, BinaryNode *rt) : element{std::move(theElement)}, left{lt}, right{rt} {} }; BinaryNode *root; void insert(const Comparable &x, BinaryNode * & t); void insert(Comparable &&x, BinaryNode * &t); void remove(const Comparable &x, BinaryNode * & t); BinaryNode *findMin(BinaryNode *t) const; BinaryNode *findMax(BinaryNode *t) const; bool contains(const Comparable &x, BinaryNode *t) const; void makeEmpty(BinaryNode * &t); void printTree(BinaryNode *t, ostream & out) const; BinaryNode *clone(BinaryNode *t) const; Pointer passed by reference (why?)

Internal functions used in recursive calls }; 8 BST: Public members calling private recursive functions 9 BST: Searching for an element /** * Internal method to test if an item is in a subtree.

* x is item to search for. * t is the node that roots the subtree. */ bool contains( const Comparable & x, BinaryNode *t ) const { if( t == nullptr ) return false; else if( x < t->element ) return contains( x, t->left ); else if( t->element < x ) return contains( x, t->right ); else return true; // Match } 10

BST: Find the smallest element /** * Internal method to find the smallest item in a subtree t. * Return node containing the smallest item. */ BinaryNode * findMin( BinaryNode *t ) const { if( t == nullptr ) return nullptr; if( t->left == nullptr ) return t; return findMin( t->left ); Tail recursion } 11

BST: Find the biggest element /** * Internal method to find the largest item in a subtree t. * Return node containing the largest item. */ BinaryNode * findMax( BinaryNode *t ) const { if( t != nullptr ) while( t->right != nullptr ) t = t->right; return t; } Non-recursive 12

BST: Insertion (5) Before insertion After insertion 13 BST: Insertion (contd.) /** * Internal method to insert into a subtree. * x is the item to insert. * t is the node that roots the subtree. * Set the new root of the subtree. */ void insert( const Comparable & x, BinaryNode * & t ) { if( t == nullptr ) t = new BinaryNode{ x, nullptr, nullptr };

else if( x < t->element ) insert( x, t->left ); else if( t->element < x ) insert( x, t->right ); else ; // Duplicate; do nothing } Strategy: Traverse the tree as if searching for x with contains() Insert when you reach a null pointer t. How to implement the move version of insert()?

14 BST: Deletion Deleting a node with one child Before deleting (4) After deleting (4) Deletion Strategy: Bypass the node being deleted 15 BST: Deletion (contd.) Deleting a node with two children Before deleting (2) After deleting (2)

Deletion Strategy: Replace the node with smallest node in the right subtree 16 BST: Deletion (contd.) /** * Internal method to remove from a subtree. * x is the item to remove. * t is the node that roots the subtree. */ void remove( const Comparable & x, BinaryNode * & t ) { if( t == nullptr ) return; // Item not found; do nothing if( x < t->element ) remove( x, t->left );

else if( t->element < x ) remove( x, t->right ); else if( t->left != nullptr && t->right != nullptr ) { // two children t->element = findMin( t->right )->element; remove( t->element, t->right ); } else { BinaryNode *oldNode = t; t = ( t->left != nullptr ) ? t->left : t->right; delete oldNode; } } 17 BST: Lazy Deletion Another deletion strategy

Dont delete! Just mark the node as deleted. Wastes space But useful if deletions are rare or space is not a concern. 18 BST: Destructor /** * Destructor for the tree */ ~BinarySearchTree( )

{ makeEmpty( ); } /** * Internal method to make subtree empty. */ void makeEmpty( BinaryNode * & t ) { if( t != nullptr ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = nullptr; }

19 BST: Assignment Operator /** * Copy constructor */ BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr } { root = clone( rhs.root ); } /** * Internal method to clone subtree. */ BinaryNode * clone( BinaryNode *t ) const { if( t == nullptr ) return nullptr;

else return new BinaryNode{ t->element, clone( t->left ), clone( t->right ) }; } 20 Tree Traversal (Inorder) // Print the tree contents in sorted order. void printTree( ostrem & out ) const { if( isEmpty( ) ) cout << "Empty tree" << endl; else printTree( root, out); } /** * Internal method to print a subtree rooted at t in sorted order.

*/ void printTree( BinaryNode *t, ostream & out ) const { if( t != nullptr ) { printTree( t->left ); out << t->element << endl; printTree( t->right ); } } 21 BST: Insertion Bias

Start with an empty tree. Insert elements in sorted order What tree do you get? How do you fix it? 22 BST: Deletion Bias After large number of alternating insertions and deletions Why this bias? How do you fix it? 23 BST: Search using function objects

Template > class BinarySearchTree { public: // same methods, with Object replacing Comparable private: BinaryNode *root; Comparable isLessThan; // same methods, with Object replacing Comparable bool contains( const Comparable & x, BinaryNode *t ) const { if( t == nullptr ) return false; else if( isLessThan(x, t->element )) return contains( x, t->left ); else if( isLessThan(t->element ,x )) return contains( x, t->right ); else

return true; // Match } }; 24 Reading assignment Sections 4.4, 4.7, and 4.8 25

## Recently Viewed Presentations

• The Web Model Contact a server and download a web page Server has all the resources and capabilities But…client devices becoming more powerful and well-connected The P2P Model A peer's resources are similar to the resources of the other participants...
• Key Preaching Truths. The Truth about Sanctification. A Holy Life. Key Preaching Truths. The Truth about Sanctification. A Holy Life. God created us for holiness. ... 3 Types of Suffering 'Common'- a result of your life's circumstances. When Ridiculed1 Peter...
• Introduction to CMOS VLSI Design Circuits & Layout Outline CMOS Gate Design Pass Transistors CMOS Latches & Flip-Flops Standard Cell Layouts Stick Diagrams CMOS Gate Design Activity: Sketch a 4-input CMOS NAND gate CMOS Gate Design Activity: Sketch a 4-input...
• Supporting Your K-12 Students with the ORC. Bethany Arsenault, ORC Coordinator. 2018/2019
• Prophecy is very important. Over 1/3 of the Bible is prophecy or the foretelling of future events. God has given us thousands of verses that deal with prophecy. God has devoted whole books in the Bible to nothing but prophecy....
• LAUREN, MAY, ANNIE, & ANJANETTE Helps to absorb vitamins and minerals Needed to build cell membranes and myelin sheath around nerves Essential for blood clotting, muscle movement, and inflammation Contain all possible hydrogens in carbon chains (All Single Bonds) No...
• HR Expectations. Homeroom is a one way door! You cannot leave without permission and a pass. Get ready for the day! 9:00: time to read. You must be reading.
• Sociopathic behavior on the Internet. Dissocial personality disorder, definition p. 196. Types: Cyberbully: uses the Internet to harass a particular target, often using fake identities or public Web sites to enable harassment; often chooses targets known in real life