Discrete Math - Graphs A binomial tree is a special kind of rooted tree used for

Question

Discrete Math - Graphs

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, leftmost) 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) The height of a degree d binomial tree is d.

Proof by induction:

The base case is d = 0, when there is only one node and no edges. The height is 0. So the result is true for d = 0.

Let us assume the result is true for d = n i.e the hieght of a degree n binomial tree is n.

A degree n+1 tree is formed by adding a new vertex with a new edge to every node of the degree n tree.

Since only the leftmost vertex has degree n in an n-degree tree, that vertex gets degree n+1. And the height of the tree is thus n+1.

Thus the result is true for d = n+1 as well.

Hence by induction, the result is true for all n.

(b) As we said already, a d+1 degree tree gets one additional node for every node.

Thus N(d+1) = 2N(d)

(c) N(d) = 2d  (not hard to notice considering the result above)

Proof by induction:

Base case is d = 0, 20 = 1 is the number of nodes.

Let us assume the result is true for some d = n i.e N(n) = 2n.

Now according to our recurrence relation,

N(n+1) = 2 * 2n = 2n+1

Thus the result is true for d = n+1 as well.

Hence by induction, the result is true for all d.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.