Question? Leave a message!

Binary search tree algorithm with example ppt

binary search tree example ppt and optimal binary search trees using dynamic programming ppt
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
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 © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Binary 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: – push_front and push_back 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 sub-tree to be less than the object stored in the root node, and – Require all objects in the right sub-tree 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 sub-trees 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 sub-tree – Otherwise, continue searching the right sub-tree 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 non-empty binary search tree as a binary tree with the following properties: – The left sub-tree (if any) is a binary search tree and all elements are less than the root element, and – The right sub-tree (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 Single_list class – We will have a Binary_search_nodes class – A Binary_search_tree 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 binary-search-tree 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 "Binary_node.h" template typename Type class Binary_search_tree; template typename Type class Binary_search_node:public Binary_nodeType using Binary_nodeType::element; using Binary_nodeType::left_tree; using Binary_nodeType::right_tree; public: Binary_search_node( Type const & ); Binary_search_node left() const; Binary_search_node 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 &, Binary_search_node & ); friend class Binary_search_treeType; ;Binary search trees 18 6.1.4 Constructor The constructor simply calls the constructor of the base class – Recall that it sets both left_tree and right_tree to nullptr – It assumes that this is a new leaf node template typename Type Binary_search_nodeType::Binary_search_node( Type const &obj ): Binary_nodeType( 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 Binary_node, we must recast them as Binary_search_node: template typename Type Binary_search_nodeType Binary_search_nodeType::left() const return reinterpret_castBinary_search_node ( Binary_nodeType::left() ); template typename Type Binary_search_nodeType Binary_search_nodeType::right() const return reinterpret_castBinary_search_node ( Binary_nodeType::right() ); Binary search trees 20 6.1.4 Inherited Member Functions The member functions bool empty() const bool is_leaf() const int size() const int height() const are inherited from the bas class Binary_nodeBinary search trees 21 Finding the Minimum Object template typename Type Type Binary_search_nodeType::front() const if ( empty() ) throw underflow(); return ( left()-empty() ) ? retrieve() : left()-front(); – The run time O(h)