Let T be a general tree of n nodes and e edges. Recall that T is a connected acy

Question

Let T be a general tree of n nodes and e edges. Recall that T is a connected acyclic graph (T has no cycles). a) A perfect tree with branching factor k (for some integer k > 1) is a rooted tree where every non-leaf has exactly k children and all the leaves are at the bottom level. Compute the number of nodes in a perfect tree with branching factor k and height h. Your answer should be in terms of k and h, and should be in 'closed-form", i.e., should have a constant number of terms. b) A B-tree with bounded branching factors (d, k) where (1

Explanation / Answer

PLEASE POST AS SEPARATE QUESTIONS:

a)

For a binary tree of height h has number of nodes
N= 2^{h+1}-1

First level has 2^0 nodes
2nd level has 2^1 nodes
3rd level has 2^2 nodes and so on.
so that kth level has 2^(k-1) nodes

Addind all these nodes to find total number of nodes in h+1 level(height h)
N= 1+2+2^2+2^3+...+2^h = (2^{h+1}-1)/(2-1) = 2^{h+1}-1

L is the total number of nodes at the last level that is leaves
so L=2^h

So that N= 2*L - 1

Now talking about k-ary tree of height h from binary tree of height h
just replace 2 by k

N=1+k+k^2+k^3+...+k^h
   (k^{h+1}-1)/(k-1)
but L=k^h

so that N= (k*L-1)/(k-1)

DO THUMBS UP ^_^   

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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