Question? Leave a message!

Binary trees

Binary trees
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 © 20062013 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 reallife 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 subtrees as – The lefthand subtree, and – The righthand subtreeBinary 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 subtrees are non empty trees Legend: full nodes neither leaf nodesBinary trees 9 5.1.1 Definition An empty node or a null subtree 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 Binarynode protected: Type element; Binarynode lefttree; Binarynode righttree; public: Binarynode( Type const ); Type retrieve() const; Binarynode left() const; Binarynode right() const; bool empty() const; bool isleaf() 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 BinarynodeType::Binarynode( Type const obj ): element( obj ), lefttree( nullptr ), righttree( nullptr ) // Empty constructor Binary trees 13 5.1.2 Binary Node Class The accessors are similar to that of Singlelist template typename Type Type BinarynodeType::retrieve() const return element; template typename Type BinarynodeType BinarynodeType::left() const return lefttree; template typename Type BinarynodeType BinarynodeType::right() const return righttree; Binary trees 14 5.1.2 Binary Node Class Much of the basic functionality is very similar to Simpletree template typename Type bool BinarynodeType::empty() const return ( this == nullptr ); template typename Type bool BinarynodeType::isleaf() 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 BinarynodeType::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 BinarynodeType::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 BinarynodeType::clear( Binarynode ptrtothis ) if ( empty() ) return; left()clear( leftnode ); right()clear( rightnode ); delete this; ptrtothis = 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 trees 20 Application: Ropes In 1995, Boehm et al. introduced the idea of a rope, or a heavyweight stringBinary trees 21 Application: Ropes Alphanumeric data is stored using a string of characters – A character (or char) is a numeric value from 0 to 255 where certain numbers represent certain letters For example, ‘A’ 65 01000001 2 ‘B’ 66 01000010 2 ‘a’ 97 01100001 2 ‘b’ 98 01100010 2 ‘ ’ 32 00100000 2 Unicode extends character encoding beyond the Latin alphabet – Still waiting for the Tengwar characters… J.R.R. TolkienBinary trees 22 Application: Ropes A Cstyle string is an array of characters followed by the character with a numeric value of 0 On problem with using arrays is the runtime required to concatenate two stringsBinary trees 23 Application: Ropes Concatenating two strings requires the operations of: – Allocating more memory, and – Coping both strings Q(n + m)Binary trees 24 Application: Ropes The rope data structure: – Stores strings in the leaves, – Internal nodes (full) represent the concatenation of the two strings, and – Represents the string with the right subtree concatenated onto the end of the left The previous concatenation may now occur in Q(1) timeBinary trees 25 Application: Ropes The string may be represented using the rope References: J.R.R. Tolkien, The HobbitBinary trees 26 Application: Ropes Additional information may be useful: – Recording the number of characters in both the left and right subtrees It is also possible to eliminate duplication of common substrings References: J.R.R. Tolkien, The HobbitBinary trees 27 Application: Expression Trees Any basic mathematical expression containing binary operators may be represented using a binary tree For example, 3(4a + b + c) + d/5 + (6 – e)Binary trees 28 Application: Expression Trees Observations: – Internal nodes store operators – Leaf nodes store literals or variables – No nodes have just one sub tree – The order is not relevant for • Addition and multiplication (commutative) – Order is relevant for • Subtraction and division (noncommutative) – It is possible to replace noncommutative operators using the unary negation and inversion: 1 (a/b) = a b (a – b) = a + (–b) Binary trees 29 Application: Expression Trees A postorder depthfirst traversal converts such a tree to the reverse Polish format 3 4 a × b c + + × d 5 ÷ 6 e – + +Binary trees 30 Application: Expression Trees Humans think in inorder Computers think in postorder: – Both operands must be loaded into registers – The operation is then called on those registers Most use inorder notation (C, C++, Java, C, etc.) – Necessary to translate inorder into postorderBinary trees 31 Summary In this talk, we introduced binary trees – Each node has two distinct and identifiable subtrees – Either subtree may optionally be empty – The subtrees are ordered relative to the other We looked at: – Properties – ApplicationsBinary trees 32 Usage Notes • These slides are made publicly available on the web for anyone to use • If you choose to use them, or a part thereof, for a course at another institution, I ask only three things: – that you inform me that you are using the slides, – that you acknowledge my work, and – that you alert me of any mistakes which I made or changes which you make, and allow me the option of incorporating such changes (with an acknowledgment) in my set of slides Sincerely, Douglas Wilhelm Harder, MMath
Document Information
User Name:
User Type:
United Kingdom
Uploaded Date: