Question? Leave a message!




Perfect binary trees

Perfect binary trees
ECE 250 Algorithms and Data Structures Perfect 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 © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Perfect binary trees 2 Outline Introducing perfect binary trees – Definitions and examples h + 1 – Number of nodes: 2 – 1 – Logarithmic height h – Number of leaf nodes: 2 – ApplicationsPerfect binary trees 3 5.2.1 Definition Standard definition: – A perfect binary tree of height h is a binary tree where • All leaf nodes have the same depth h • All other nodes are fullPerfect binary trees 4 5.2.1 Definition Recursive definition: – A binary tree of height h = 0 is perfect – A binary tree with height h 0 is a perfect if both subtrees are prefect binary trees of height h – 1Perfect binary trees 5 5.2.1 Examples Perfect binary trees of height h = 0, 1, 2, 3 and 4Perfect binary trees 6 Examples Perfect binary trees of height h = 3 and h = 4 – Note they’re the wrongway up…Perfect binary trees 7 5.2.2 Theorems We will now look at four theorems that describe the properties of perfect binary trees: h + 1 – A perfect tree has 2 – 1 – The height is Q(ln(n)) h – There are 2 leaf nodes – The average depth of a node is Q(ln(n)) The results of these theorems will allow us to determine the optimal runtime properties of operations on binary treesPerfect binary trees 8 h + 1 5.2.2.1 2 – 1 Nodes Theorem h + 1 A perfect binary tree of height h has 2 – 1 nodes Proof: We will use mathematical induction: 1. Show that it is true for h = 0 2. Assume it is true for an arbitrary h 3. Show that the truth for h implies the truth for h + 1Perfect binary trees 9 h + 1 5.2.2.1 2 – 1 Nodes The base case: – When h = 0 we have a single node n = 1 0 + 1 – The formula is correct: 2 – 1 = 1Perfect binary trees 10 h + 1 5.2.2.1 2 – 1 Nodes The inductive step: – If the height of the tree is h, then assume that the number of nodes is h + 1 n = 2 – 1 hPerfect binary trees 11 h + 1 5.2.2.1 2 – 1 Nodes We must show that a tree of height h + 1 has (h + 1) + 1 h + 2 n = 2 – 1 = 2 – 1 nodes h + 1Perfect binary trees 12 h + 1 5.2.2.1 2 – 1 Nodes Using the recursive definition, both subtrees are perfect trees of height h h + 1 – By assumption, each subtree has 2 – 1 nodes – Therefore the total number of nodes is h + 1 h + 1 h + 2 (2 – 1) + 1 + (2 – 1) = 2 – 1 h hPerfect binary trees 13 h + 1 5.2.2.1 2 – 1 Nodes Consequently The statement is true for h = 0 and the truth of the statement for an arbitrary h implies the truth of the statement for h + 1. Therefore, by the process of mathematical induction, the statement is true for all h ≥ 0Perfect binary trees 14 5.2.2.2 Logarithmic Height Theorem A perfect binary tree with n nodes has height lg(n + 1) – 1 Proof h + 1 Solving n = 2 – 1 for h: h + 1 n + 1 = 2 lg(n + 1) = h + 1 h = lg(n + 1) – 1Perfect binary trees 15 5.2.2.2 Logarithmic Height Lemma lg(n + 1) – 1 = Q(ln(n)) Proof 1 n1 ln(2) lg(nn  1) 1 1 1 lim lim lim lim n n n n 1 ln(nn )1 ln(2) ln(2) ln(2)  nPerfect binary trees 16 h 5.2.2.3 2 Leaf Nodes Theorem h A perfect binary tree with height h has 2 leaf nodes Proof (by induction): 0 When h = 0, there is 2 = 1 leaf node. h Assume that a perfect binary tree of height h has 2 leaf nodes and observe that both subtrees of a perfect binary tree of height h + 1 have h 2 leaf nodes. Consequence: Over half all nodes are leaf nodes: h 21  h1 21 2Perfect binary trees 17 5.2.2.4 The Average Depth of a Node Consequence: – 5050 chance that a randomly selected node is a leaf node The average depth of a node in a perfect binary tree is Depth Count 0 1 1 2 2 4 3 8 4 16 5 32 h Sum of the k k2  h1 h1 h1 h1 depths h2 2 2 h(21) (21)1 h k0  h1 h1 h1 21 21 21 h1  h1 h1Q ln(n)  h1 21 Number of nodesPerfect binary trees 18 5.2.3 Applications Perfect binary trees are considered to be the ideal case – The height and average depth are both Q(ln(n)) We will attempt to find trees which are as close as possible to perfect binary treesPerfect binary trees 19 Summary We have defined perfect binary trees and discussed: h + 1 – The number of nodes: n = 2 – 1 – The height: lg(n + 1) – 1 h – The number of leaves: 2 – Half the nodes are leaves • Average depth is Q(ln(n)) – It is an ideal casePerfect binary trees 20 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 dwharderalumni.uwaterloo.ca
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017