A binomial tree is a special kind of rooted tree used for various data structure
ID: 3837684 • Letter: A
Question
A binomial tree is a special kind of rooted tree used for various data structures in computer science. A degree d binomial tree can be defined recursively as follows. A degree 0 binomial tree is a single vertex with no edges. A degree d binomial tree has a root vertex with out-degree d. The first (that is, left most) subtree is a degree d - 1 binomial tree. The second (that is, second to left) subtree is a degree d - 2 binomial tree. Continue on in this way so that the last (rightmost) subtree is a degree 0 binomial tree. (a) What is the height of a degree d binomial tree? Prove your result by induction on d. (b) Write a recurrence for the number of nodes N(d) in a binomial tree of degree d. (c) Use the guess-and-check method to guess a formula for N(d). Prove that your formula holds by induction on d.Explanation / Answer
A binomial tree of degree d is two binomial tree of degree d-1 joined by on edge, the
root of one is the leftmost child of the root of the other
like this
o
/|
o o
|
o
binomial tree of degree 2 is two binomial tree of degree 1 joined by one edge. the
root of one is the leftmost child of the root of the other
Q 1
Proof 1)
Height of degree d binomial tree is d
proof by induction
Height(0) = 0
Height(1) = 1
Assume Height(k) = k
Now, Height (k + 1) = A binomial tree of degree k+1 is two binomial tree of degree k joined by one edge,the
root of one is the leftmost child of the root of the other. So, this will increase height of tree by 1
so, Height(k + 1) = Height(k) + 1
= k + 1
Thus, Height of degree d binomial tree is d
Q 2)
N(d) = 2^d
Q 3)
No of nodes in degree d binomial tree is 2^d
proof by induction
N(0) = 1
N(1) = 2
Assume N(k) = 2^k
Now, N(k + 1) = A binomial tree of degree k+1 is two binomial tree of degree k joined by one edge,
so, N(k + 1) = N(k) + N(k)
= 2^k + 2^k
= 2^(k+1)
N(d) = 2^d
Thus, No of nodes in degree d binomial tree is 2^d
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.