Question? Leave a message!




Binomial Trees

Binomial Trees
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
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 © 2006-2013 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 sub-tree 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 sub-tree 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 sub-tree 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 sub-tree of order 2Binomial trees 10 Recursive Definition A binomial tree of order h = 3 is: – A binomial tree of order 2 with an additional sub-tree 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 sub-tree of order 3Binomial trees 12 Recursive Definition A binomial tree of order h = 4 is: – A binomial tree of order 3 with an additional sub-tree 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 sub-tree of order 4Binomial trees 14 Recursive Definition A binomial tree of order h = 5 is: – A binomial tree of order 4 with an additional sub-tree 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 sub-tree 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 sub-tree 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 sub-tree 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 sub-trees which are binomial trees of heights 0, 1, 2, …, h – 1