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 key to positive discipline is not punishment, she tells us, but mutual respect. Nelsen coaches parents and teachers to be both firm and kind, so that any child-from a three-year-old toddler to a rebellious teenager-can learn creative cooperation and...
• means "life", so . abiotic. simply means "not living". ... A cheetah and gazelle are an obvious example of a classic predator-prey relationship. ... The Carbon Cycle. This is one of the fundamental biological interactions that make up .
• Thematic statements: not too vague (a person changes because of death) or too specific and wordy (an individual who loses something precious must go on a journey to discover truth about himself in order to reconcile his loss and become...
• In open-system terms, business organizations are made up of interdependent technical, boundary-spanning, and managerial subsystems. Organizations need to satisfy different effectiveness criteria in the near, intermediate, and distant future.
• Anthropology Graduate Program - Sample Timeline. ANTH 7255 (Applied) ANTH 7400 (GDC) ANTH 7200 (Theory) ANTH 7511 (Med Anth Theory) ANTH 7075 (Methods) ANTH 7076 (Analysis) ANTH 6511 (Med Anth) Practicum and Comprehensive Exams. Required Courses (excluding electives) Fall ....
• G1/S, G2/M, and M checkpoints Section 16.3 Cell-Cycle Control and Checkpoints G1/S checkpoints monitor cell size and determine whether DNA has been damaged. G2/M is where physiological conditions are checked (once G1/S are passed) prior to mitosis.
• Value Proposition Definition. Your Value Proposition is: a statement that includes your important customer and market. Need. along with your new, compelling, and defensible. Approach. to address that need with superior. Benefits per costs. when compared to the. Competition. and/or...
• Chapter 8 An Introduction To Metabolism Metabolism Catabolic Pathways Anabolic Pathways Energy Kinetic Energy Potential Energy Activation Energy Energy Transformation . 1st Law of Thermodynamics 2nd Law of Thermodynamics Entropy Summary The quantity of energy in the universe is constant,...