Question? Leave a message!




Binary search trees

Binary search trees
ECE 250 Algorithms and Data Structures Binary search trees Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Binary search trees 2 Outline This topic covers binary search trees: – Abstract Sorted Lists – Background – Definition and examples – Implementation: • Front, back, insert, erase • Previous smaller and next larger objects th • Finding the k objectBinary search trees 3 6.1.1 Abstract Sorted Lists Previously, we discussed Abstract Lists: the objects are explicitly linearly ordered by the programmer We will now discuss the Abstract Sorted List: – The relation is based on an implicit linear ordering Certain operations no longer make sense: – pushfront and pushback are replaced by a generic insertBinary search trees 4 6.1.1 Abstract Sorted Lists Queries that may be made about data stored in a Sorted List ADT include: – Finding the smallest and largest entries th – Finding the k largest entry – Find the next larger and previous smaller objects of a given object which may or may not be in the container – Iterate through those objects that fall on an interval a, bBinary search trees 5 6.1.1 Implementation If we implement an Abstract Sorted List using an array or a linked list, we will have operations which are O(n) – As an insertion could occur anywhere in a linked list or array, we must either traverse or copy, on average, O(n) objectsBinary search trees 6 6.1.2 Background Recall that with a binary tree, we can dictate an order on the two children We will exploit this order: – Require all objects in the left subtree to be less than the object stored in the root node, and – Require all objects in the right subtree to be greater than the object in the root objectBinary search trees 7 6.1.2 Binary Search Trees Graphically, we may relationship – Each of the two subtrees will themselves be binary search treesBinary search trees 8 6.1.2 Binary Search Trees Notice that we can already use this structure for searching: examine the root node and if we have not found what we are looking for: – If the object is less than what is stored in the root node, continue searching in the left subtree – Otherwise, continue searching the right subtree With a linear order, one of the following three must be true: a b a = b a bBinary search trees 9 6.1.2 Definition Thus, we define a nonempty binary search tree as a binary tree with the following properties: – The left subtree (if any) is a binary search tree and all elements are less than the root element, and – The right subtree (if any) is a binary search tree and all elements are greater than the root elementBinary search trees 10 6.1.2 Examples Here are other examples of binary search trees:Binary search trees 11 6.1.2 Examples Unfortunately, it is possible to construct degenerate binary search trees – This is equivalent to a linked list, i.e., O(n)Binary search trees 12 6.1.2 Examples All these binary search trees store the same dataBinary search trees 13 6.1.3 Duplicate Elements We will assume that in any binary tree, we are not storing duplicate elements unless otherwise stated – In reality, it is seldom the case where duplicate elements in a container must be stored as separate entities You can always consider duplicate elements with modifications to the algorithms we will coverBinary search trees 14 6.1.4 Implementation We will look at an implementation of a binary search tree in the same spirit as we did with our Singlelist class – We will have a Binarysearchnodes class – A Binarysearchtree class will store a pointer to the root We will use templates, however, we will require that the class overrides the comparison operatorsBinary search trees 15 6.1.4 Implementation Any class which uses this binarysearchtree class must therefore implement: bool operator=( Type const , Type const ); bool operator ( Type const , Type const ); bool operator==( Type const , Type const ); That is, we are allowed to compare two instances of this class – Examples: int and doubleBinary search trees 16 6.1.4 Implementation include "Binarynode.h" template typename Type class Binarysearchtree; template typename Type class Binarysearchnode:public BinarynodeType using BinarynodeType::element; using BinarynodeType::lefttree; using BinarynodeType::righttree; public: Binarysearchnode( Type const ); Binarysearchnode left() const; Binarysearchnode right() const;Binary search trees 17 6.1.4 Implementation Type front() const; Type back() const; bool find( Type const ) const; void clear(); bool insert( Type const ); bool erase( Type const , Binarysearchnode ); friend class BinarysearchtreeType; ;Binary search trees 18 6.1.4 Constructor The constructor simply calls the constructor of the base class – Recall that it sets both lefttree and righttree to nullptr – It assumes that this is a new leaf node template typename Type BinarysearchnodeType::Binarysearchnode( Type const obj ): BinarynodeType( obj ) // Just calls the constructor of the base class Binary search trees 19 6.1.4 Standard Accessors Because it is a derived class, it already inherits the function: Type retrieve() const; Because the base class returns a pointer to a Binarynode, we must recast them as Binarysearchnode: template typename Type BinarysearchnodeType BinarysearchnodeType::left() const return reinterpretcastBinarysearchnode ( BinarynodeType::left() ); template typename Type BinarysearchnodeType BinarysearchnodeType::right() const return reinterpretcastBinarysearchnode ( BinarynodeType::right() ); Binary search trees 20 6.1.4 Inherited Member Functions The member functions bool empty() const bool isleaf() const int size() const int height() const are inherited from the bas class BinarynodeBinary search trees 21 6.1.4.1 Finding the Minimum Object template typename Type Type BinarysearchnodeType::front() const if ( empty() ) throw underflow(); return ( left()empty() ) retrieve() : left()front(); – The run time O(h)Binary search trees 22 6.1.4.2 Finding the Maximum Object template typename Type Type BinarysearchnodeType::back() const if ( empty() ) throw underflow(); return ( right()empty() ) retrieve() : right()back(); – The extreme values are not necessarily leaf nodesBinary search trees 23 6.1.4.3 Find To determine membership, traverse the tree based on the linear relationship: – If a node containing the value is found, e.g., 81, return 1 – If an empty node is reached, e.g., 36, the object is not in the tree:Binary search trees 24 6.1.4.3 Find The implementation is similar to front and back: template typename Type bool BinarysearchnodeType::find( Type const obj ) const if ( empty() ) return false; else if ( retrieve() == obj ) return true; return ( obj retrieve() ) left()find( obj ) : right()find( obj ); – The run time is O(h)Binary search trees 25 6.1.4.4 Insert Recall that a Sorted List is implicitly ordered – It does not make sense to have member functions such as pushfront and pushback – Insertion will be performed by a single insert member function which places the object into the correct locationBinary search trees 26 6.1.4.4 Insert An insertion will be performed at a leaf node: – Any empty node is a possible location for an insertion The values which may be inserted at any empty node depend on the surrounding nodesBinary search trees 27 6.1.4.4 Insert For example, this node may hold 48, 49, or 50Binary search trees 28 6.1.4.4 Insert An insertion at this location must be 35, 36, 37, or 38Binary search trees 29 6.1.4.4 Insert This empty node may hold values from 71 to 74Binary search trees 30 6.1.4.4 Insert Like find, we will step through the tree – If we find the object already in the tree, we will return • The object is already in the binary search tree (no duplicates) – Otherwise, we will arrive at an empty node – The object will be inserted into that location – The run time is O(h)Binary search trees 31 6.1.4.4 Insert In inserting the value 52, we traverse the tree until we reach an empty node – The left subtree of 54 is an empty nodeBinary search trees 32 6.1.4.4 Insert A new leaf node is created and assigned to the member variable lefttreeBinary search trees 33 6.1.4.4 Insert In inserting 40, we determine the right subtree of 39 is an empty nodeBinary search trees 34 6.1.4.4 Insert A new leaf node storing 40 is created and assigned to the member variable righttreeBinary search trees 35 6.1.4.4 Insert template typename Type bool BinarysearchnodeType::insert( Type const obj, Binarysearchnode ptrtothis ) if ( empty() ) ptrtothis = new BinarysearchnodeType( obj ); return true; else if ( obj retrieve() ) return left()insert( obj, lefttree ); else if ( obj retrieve() ) return right()insert( obj, righttree ); else return false; Binary search trees 36 6.1.4.4 Insert It is assumed that if neither of the conditions: obj retrieve() obj retrieve() then obj == retrieve() and therefore we do nothing – The object is already in the binary search treeBinary search trees 37 6.1.4.4 Insert Blackboard example: – In the given order, insert these objects into an initially empty binary search tree: 31 45 36 14 52 42 6 21 73 47 26 37 33 8 – What values could be placed: • To the left of 21 • To the right of 26 • To the left of 47 – How would we determine if 40 is in this binary search tree – Which values could be inserted to increase the height of the treeBinary search trees 38 6.1.4.5 Erase A node being erased is not always going to be a leaf node There are three possible scenarios: – The node is a leaf node, – It has exactly one child, or – It has two children (it is a full node)Binary search trees 39 6.1.4.5 Erase A leaf node simply must be removed and the appropriate member variable of the parent is set to nullptr – Consider removing 75Binary search trees 40 6.1.4.5 Erase The node is deleted and lefttree of 81 is set to nullptrBinary search trees 41 6.1.4.5 Erase Erasing the node containing 40 is similarBinary search trees 42 6.1.4.5 Erase The node is deleted and righttree of 39 is set to nullptrBinary search trees 43 6.1.4.5 Erase If a node has only one child, we can simply promote the subtree associated with the child – Consider removing 8 which has one left childBinary search trees 44 6.1.4.5 Erase The node 8 is deleted and the lefttree of 11 is updated to point to 3Binary search trees 45 6.1.4.5 Erase There is no difference in promoting a single node or a subtree – To remove 39, it has a single child 11Binary search trees 46 6.1.4.5 Erase The node containing 39 is deleted and leftnode of 42 is updated to point to 11 – Notice that order is still maintainedBinary search trees 47 6.1.4.5 Erase Consider erasing the node containing 99Binary search trees 48 6.1.4.5 Erase The node is deleted and the left subtree is promoted: – The member variable righttree of 70 is set to point to 92 – Again, the order of the tree is maintainedBinary search trees 49 6.1.4.5 Erase Finally, we will consider the problem of erasing a full node, e.g., 42 We will perform two operations: – Replace 42 with the minimum object in the right subtree – Erase that object from the right subtreeBinary search trees 50 6.1.4.5 Erase In this case, we replace 42 with 47 – We temporarily have two copies of 47 in the treeBinary search trees 51 6.1.4.5 Erase We now recursively erase 47 from the right subtree – We note that 47 is a leaf node in the right subtreeBinary search trees 52 6.1.4.5 Erase Leaf nodes are simply removed and lefttree of 51 is set to nullptr – Notice that the tree is still sorted: 47 was the least object in the right subtreeBinary search trees 53 6.1.4.5 Erase Suppose we want to erase the root 47 again: – We must copy the minimum of the right subtree – We could promote the maximum object in the left subtree and achieve similar resultsBinary search trees 54 6.1.4.5 Erase We copy 51 from the right subtreeBinary search trees 55 6.1.4.5 Erase We must proceed by delete 51 from the right subtreeBinary search trees 56 6.1.4.5 Erase In this case, the node storing 51 has just a single childBinary search trees 57 6.1.4.5 Erase We delete the node containing 51 and assign the member variable lefttree of 70 to point to 59Binary search trees 58 6.1.4.5 Erase Note that after seven removals, the remaining tree is still correctly sortedBinary search trees 59 6.1.4.5 Erase In the two examples of removing a full node, we promoted: – A node with no children – A node with right child Is it possible, in removing a full node, to promote a child with two children Binary search trees 60 6.1.4.5 Erase Recall that we promoted the minimum element in the right subtree – If that node had a left subtree, that subtree would contain a smaller valueBinary search trees 61 6.1.4.5 Erase In order to properly remove a node, we will have to change the member variable pointing to the node – To do this, we will pass that member variable by reference Additionally: We will return 1 if the object is removed and 1 if the object was not foundBinary search trees 62 6.1.4.5 Erase template typename Type bool BinarysearchnodeType::erase( Type const obj, Binarysearchnode ptrtothis ) if ( empty() ) return false; else if ( obj == retrieve() ) if ( isleaf() ) // leaf node ptrtothis = nullptr; delete this; else if ( left()empty() right()empty() ) // full node element = right()front(); right()erase( retrieve(), righttree ); else // only one child ptrtothis = ( left()empty() ) left() : right(); delete this; return true; else if ( obj retrieve() ) return left()erase( obj, lefttree ); else return right()erase( obj, righttree ); Binary search trees 63 6.1.4.5 Erase Blackboard example: – In the binary search tree generated previously: • Erase 47 • Erase 21 • Erase 45 • Erase 31 • Erase 36Binary search trees 64 6.1.5 Binary Search Tree We have defined binary search nodes – Similar to the Singlenode in Project 1 We must now introduce a container which stores the root – A Binarysearchtree class Most operations will be simply passed to the root nodeBinary search trees 65 6.1.5 Implementation template typename Type class Binarysearchtree private: BinarysearchnodeType rootnode; BinarysearchnodeType root() const; public: Binarysearchtree(); Binarysearchtree(); bool empty() const; int size() const; int height() const; Type front() const; Type back() const; int count( Type const obj ) const; void clear(); bool insert( Type const obj ); bool erase( Type const obj ); ;Binary search trees 66 6.1.5 Constructor, Destructor, and Clear template typename Type BinarysearchtreeType::Binarysearchtree(): rootnode( nullptr ) // does nothing template typename Type BinarysearchtreeType::Binarysearchtree() clear(); template typename Type void BinarysearchtreeType::clear() root()clear( rootnode ); Binary search trees 67 6.1.5 Constructor, Destructor, and Clear template typename Type BinarysearchtreeType BinarysearchtreeType::root() const return treeroot; template typename Type bool BinarysearchtreeType::empty() const return root()empty(); template typename Type int BinarysearchtreeType::size() const return root()size(); Binary search trees 68 6.1.5 Empty, Size, Height and Count template typename Type int BinarysearchtreeType::height() const return root()height(); template typename Type bool BinarysearchtreeType::find( Type const obj ) const return root()find( obj ); Binary search trees 69 6.1.5 Front and Back // If root() is nullptr, 'front' will throw an underflow exception template typename Type Type BinarysearchtreeType::front() const return root()front(); // If root() is nullptr, 'back' will throw an underflow exception template typename Type Type BinarysearchtreeType::back() const return root()back(); Binary search trees 70 6.1.5 Insert and Erase template typename Type bool BinarysearchtreeType::insert( Type const obj ) return root()insert( obj, rootnode ); template typename Type bool BinarysearchtreeType::erase( Type const obj ) return root()erase( obj, rootnode ); Binary search trees 71 6.1.6 Other Relationbased Operations We will quickly consider two other relationbased queries that are very quick to calculate with an array of sorted objects: – Finding the previous and next entries, and th – Finding the k entryBinary search trees 72 6.1.6.1 Previous and Next Objects All the operations up to now have been operations which work on any container: count, insert, etc. – If these are the only relevant operations, use a hash table Operations specific to linearly ordered data include: – Find the next larger and previous smaller objects of a given object which may or may not be in the container th – Find the k entry of the container – Iterate through those objects that fall on an interval a, b We will focus on finding the next largest object – The others will followBinary search trees 73 6.1.6.1 Previous and Next Objects To find the next largest object: – If the node has a right subtree, the minimum object in that subtree is the nextlargest object Binary search trees 74 6.1.6.1 Previous and Next Objects If, however, there is no right subtree: – It is the next largest object (if any) that exists in the path from the root to the nodeBinary search trees 75 6.1.6.1 Previous and Next Objects More generally: what is the next largest entry of an arbitrary object – This can be found with a single search from the root node to one of the leaves—an O(h) operation – This function returns the object if it did not find something greater than it template typename Type Type BinarysearchnodeType::next( Type const obj ) const if ( empty() ) return obj; else if ( retrieve() == obj ) return ( right()empty() ) obj : right()front(); else if ( retrieve() obj ) Type tmp = left()next( obj ); return ( tmp == obj ) retrieve() : tmp; else return right()next( obj ); Binary search trees 76 th 6.1.6.2 Finding the k Object th Another operation on sorted lists may be finding the k largest object – Recall that k goes from 0 to n– 1 – If the leftsubtree has ℓ = k entries, return the current node, th – If the left subtree has ℓ k entries, return the k entry of the left subtree, th – Otherwise, the left subtree has ℓ k entries, so return the (k–ℓ– 1) entry of the right subtree 18 7 10 1 5 0 2 3 4 5 6 7 8 9 10 11 13 141516 17 1 12Binary search trees 77 th 6.1.6.2 Finding the k Object template typename Type Type BinarysearchtreeType::at( int k ) const return ( k 0 k = size() ) Type() : root()at( k ); // Need to go from 0, ..., n 1 template typename Type Type BinarysearchnodeType::at( int k ) const if ( left()size() == k ) return retrieve(); else if ( left()size() k ) return left()at( k ); else return right()at( k left()size() – 1 ); Binary search trees 78 th 6.1.7 Finding the k Object This requires that size() returns in Q(1) time – We must have a member variable int treesize; which stores the number of descendants of this node – This requires Q(n) additional memory template typename Type bool BinarysearchtreeType::size() const return root()size(); – We can implement this in the Binarynode class, if we want • The constructor will set the size to 1Binary search trees 79 th 6.1.7 Finding the k Object We must now update insert(…) and erase(…) to update it template typename Type bool BinarysearchnodeType::insert( Type const obj, Binarysearchnode ptrtothis ) if ( empty() ) ptrtothis = new BinarysearchnodeType( obj ); return true; else if ( obj retrieve() ) return left()insert( obj, lefttree ) ++treesize : false; else if ( obj retrieve() ) return right()insert( obj, righttree ) ++treesize : false; else return false; Clever trick: in C and C++, any nonzero value is interpreted as trueBinary search trees 80 6.1.7 Run Time: O(h) Almost all of the relevant operations on a binary search tree are O(h) – If the tree is close to a linked list, the run times is O(n) • Insert 1, 2, 3, 4, 5, 6, 7, ..., n into a empty binary search tree – The best we can do is if the tree is perfect: O(ln(n)) – Our goal will be to find tree structures where we can maintain a height of Q(ln(n)) We will look at – AVL trees – B+ trees both of which ensure that the height remains Q(ln(n)) Others exist, too
Website URL
Comment