Question? Leave a message!




Binomial Trees

Binomial Trees
ECE 250 Algorithms and Data Structures Binomial 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.Binomial trees 2 Background A binomial tree is an alternate optimal tree to a perfect binary treeBinomial trees 3 The Idea The recursive definition is as follows: – A single node is a binomial tree of order h = 0 – A binomial tree B of order h is two binomial trees B and B of 1 2 height h – 1 where • The root of B is the root of B, and 1 • B is a subtree of B 2 1Binomial trees 4 Recursive Definition Thus, we start with a binomial tree of height 0:Binomial trees 5 Recursive Definition A binomial tree of height h = 1 is: – A binomial tree of height 0 with a subtree of height 0Binomial trees 6 Recursive Definition A binomial tree of order h = 1:Binomial trees 7 Recursive Definition A binomial tree of order h = 2 is: – A binomial tree of order 1 with an additional subtree of order 1Binomial trees 8 Recursive Definition Like perfect trees, binomial trees are not defined for three nodesBinomial trees 9 Recursive Definition A binomial tree of order h = 3 is: – A binomial tree of order 2 with an additional subtree of order 2Binomial trees 10 Recursive Definition A binomial tree of order h = 3 is: – A binomial tree of order 2 with an additional subtree of order 2 – Here we have 8 nodesBinomial trees 11 Recursive Definition A binomial tree of order h = 4 is: – A binomial tree of order 3 with an additional subtree of order 3Binomial trees 12 Recursive Definition A binomial tree of order h = 4 is: – A binomial tree of order 3 with an additional subtree of order 3 – Here we have 16 nodesBinomial trees 13 Recursive Definition A binomial tree of order h = 5 is: – A binomial tree of order 4 with an additional subtree of order 4Binomial trees 14 Recursive Definition A binomial tree of order h = 5 is: – A binomial tree of order 4 with an additional subtree of order 4Binomial trees 15 Recursive Definition As a last example, a binomial tree of order h = 6 is: – A binomial tree of order 5 with an additional subtree of order 5Binomial trees 16 Various Theorems Theorem A binomial tree of order h has height h Proof: By induction, a binomial tree of order h = 0 has height 0, Assume it is true that a binomial tree of order h has height h, and A binomial tree of order h + 1 consists of: • A binomial tree of order h and therefore height h, and • An additional subtree of order h and therefore height h Thus, a binomial tree order h has a height of max(h, h + 1) = h + 1 We will use the terms ―order h‖ and ―height h‖ interchangableBinomial trees 17 Various Theorems Theorem h A binomial tree of height h has 2 nodes Proof: 0 By induction, a binomial tree of height h = 0 has 1 = 2 nodes, Assume it is true for a binomial tree of height h, and A binomial tree of height h + 1 consists of: h • A binomial tree of height h with 2 nodes, and h • An additional subtree of height h with 2 additional nodes h h + 1 Thus, a binomial tree of height h + 1 has 2 = 2 nodesBinomial trees 18 Various Theorems Corollary A binomial tree with n nodes has a height of lg(n)Binomial trees 19 Various Theorems Theorem h  A binomial tree of height h has nodes at depth k  k  Proof: 0 By induction, a binomial tree of height h = 0 has 1 = 2 nodes, Assume it is true for a binomial tree of height h, and A binomial tree of height h + 1 has only one root node and one node at depth h + 1: hh  11  1  01 h  The number of nodes at depth k in a tree of height h + 1 has • All the nodes of a binomial tree of height h at depth k, and • All the nodes of a binomial tree of height h at depth k + 1 Thus, h1 h h    k k k1 Binomial trees 20 Alternate Definition An alternate definition of a binomial tree is: A binomial tree of height h is a root node and has h subtrees which are binomial trees of heights 0, 1, 2, …, h – 1Binomial trees 21 Alternate Definition For example, this binomial tree of height h = 6 has six subtrees of heights 5, 4, 3, 2, 1 and 0Binomial trees 22 Various Theorems Theorem The degree of a root of a binomial tree of height h is h Proof: This follows trivially from the alternate definition Corollary The degree of the root is lg(n)Binomial trees 23 Various Theorems Theorem The root has the maximum degree of any node in a binomial tree Proof: Every other node is the root of a binomial tree of height less than h and therefore can only have less than h childrenBinomial trees 24 Applications We will use binomial trees in two applications: – The worstcase scenario for the depth of a disjoint set data structure – Binomial heaps—very fast priority queuesBinomial trees 25 Summary This topic has covered binomial trees: h – A tree of height h with 2 nodes – Same idea as a perfect binary tree – The root has degree h h  – There are with nodes at depth k  k Binomial trees 26 References 1 Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, nd 2 Ed., MIT Press, 2001, §19.1, pp.4579. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §6.8.1, p.240.Binomial trees 27 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