# 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