Page 235 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Figure 11.5: Two Views of Binomial Tree B 4

B 0

(a)
B
1
B 2

B
3

(b)

B 3

B
3
Alternatively, you can think of B as being comprised of two binomial trees of order k-1.
k

Example: Figure 11.5 (b) shows that B is made up of two instances of B . In general,
3
4
suppose you have two trees of order k-1, say B 1 k–1 and B 2 k–1 , where B 1 k–1 = {R , B , B , B , ..., B 1 k–2 }.
1
1
1
1
1
2
0
Then you can construct a binomial tree of order k by combining the trees to get
1
B = {R , B , B , B , ..., B 1 , B 2 }.
1
1
1
k 0 1 2 k–2 k–1
Why do you call B a binomial tree? It is because the number of nodes at a given depth in the tree
k
is determined by the binomial coeffi cient. And the binomial coeffi cient derives its name from the
binomial theorem. And the binomial theorem tells us how to compute the n power of a binomial .
th
And a binomial is an expression which consists of two terms, such as x+y. That is why it is called
a binomial tree!
Task “Binomial tree is a general true with a very special shape” Discuss.

230 LOVELY PROFESSIONAL UNIVERSITY