Binary search tree example ppt

binary search tree algorithm ppt and binary tree traversal example ppt
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
ECE 250 Algorithms and Data Structures Binary 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 © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Binary trees 2 Outline In this talk, we will look at the binary tree data structure: – Definition – Properties – A few applications • Ropes (strings) • Expression treesBinary trees 3 Definition This is not a binary tree:Binary trees 4 5.1 Definition The arbitrary number of children in general trees is often unnecessary—many real-life trees are restricted to two branches – Expression trees using binary operators – An ancestral tree of an individual, parents, grandparents, etc. – Phylogenetic trees – Lossless encoding algorithms There are also issues with general trees: – There is no natural order between a node and its childrenBinary trees 5 5.1.1 Definition A binary tree is a restriction where each node has exactly two children: – Each child is either empty or another binary tree – This restriction allows us to label the children as left and right subtrees At this point, recall that lg(n) = Q(log (n)) for any b bBinary trees 6 5.1.1 Definition We will also refer to the two sub-trees as – The left-hand sub-tree, and – The right-hand sub-treeBinary trees 7 5.1.1 Definition Sample variations on binary trees with five nodes:Binary trees 8 5.1.1 Definition A full node is a node where both the left and right sub-trees are non- empty trees Legend: full nodes neither leaf nodesBinary trees 9 5.1.1 Definition An empty node or a null sub-tree is any location where a new leaf node could be appendedBinary trees 10 5.1.1 Definition A full binary tree is where each node is: – A full node, or – A leaf node These have applications in – Expression trees – Huffman encodingBinary trees 11 5.1.2 Binary Node Class The binary node class is similar to the single node class: include algorithm template typename Type class Binary_node protected: Type element; Binary_node left_tree; Binary_node right_tree; public: Binary_node( Type const & ); Type retrieve() const; Binary_node left() const; Binary_node right() const; bool empty() const; bool is_leaf() const; int size() const; int height() const; void clear(); Binary trees 12 5.1.2 Binary Node Class We will usually only construct new leaf nodes template typename Type Binary_nodeType::Binary_node( Type const &obj ): element( obj ), left_tree( nullptr ), right_tree( nullptr ) // Empty constructor Binary trees 13 5.1.2 Binary Node Class The accessors are similar to that of Single_list template typename Type Type Binary_nodeType::retrieve() const return element; template typename Type Binary_nodeType Binary_nodeType::left() const return left_tree; template typename Type Binary_nodeType Binary_nodeType::right() const return right_tree; Binary trees 14 5.1.2 Binary Node Class Much of the basic functionality is very similar to Simple_tree template typename Type bool Binary_nodeType::empty() const return ( this == nullptr ); template typename Type bool Binary_nodeType::is_leaf() const return empty() && left()-empty() && right()-empty(); Binary trees 15 5.1.2 Size The recursive size function runs in Q(n) time and Q(h) memory – These can be implemented to run in Q(1) template typename Type int Binary_nodeType::size() const return empty() ? 0 : 1 + left()-size() + right()-size(); Binary trees 16 5.1.2 Height The recursive height function also runs in Q(n) time and Q(h) memory – Later we will implement this in Q(1) time template typename Type int Binary_nodeType::height() const return empty() ? -1 : 1 + std::max( left()-height(), right()-height() ); Binary trees 17 5.1.2 Clear Removing all the nodes in a tree is similarly recursive: template typename Type void Binary_nodeType::clear( Binary_node &ptr_to_this ) if ( empty() ) return; left()-clear( left_node ); right()-clear( right_node ); delete this; ptr_to_this = nullptr; Binary trees 18 5.1.3 Run Times Recall that with linked lists and arrays, some operations would run in Q(n) time The run times of operations on binary trees, we will see, depends on the height of the tree We will see that: – The worst is clearly Q(n) – Under average conditions, the height isQ n – The best case is Q(ln(n))Binary trees 19 5.1.3 Run Times If we can achieve and maintain a height Q(lg(n)), we will see that many operations can run in Q(lg(n)) we Logarithmic time is not significantly worse than constant time: lg( 1000 ) ≈ 10 kB lg( 1 000 000 ) ≈ 20 MB lg( 1 000 000 000 ) ≈ 30 GB lg( 1 000 000 000 000 ) ≈ 40 TB n lg( 1000 ) ≈ 10 n http://xkcd.com/394/Binary trees 20 5.1.4.1 Application: Ropes In 1995, Boehm et al. introduced the idea of a rope, or a heavyweight string