PLEASE SHOW ALL STEPS WHEN SOLVING THIS Problem 2. A perfect binary tree is a tr

Question

PLEASE SHOW ALL STEPS WHEN SOLVING THIS

Problem 2. A perfect binary tree is a tree in which every node other than the leaves has exactly two children, and the leaves are all at the same level. We are going to find the exact number of comparisons (in the worst case) for heap creation in a perfect binary tree. We will guess the formula by looking at a few small examples, and then prove it is correct by mathematical induction (a) The height of a tree is the number of levels of nodes. (A tree consisting of a single root node has height 0. A tree consist ing of a root node with some children has height 1. Etc.) (i) Assume a perfect binary tree has height h. How many nodes does it have? Justify. (b) Calulate by hand the exact number of comparisons for complete trees with heights (c) We know that the true answer should be approximately 2n. Find the differences between (d) Guess a formula for your differences as a function of n (ii Assume a perfect binary tree has n nodes. What is its height? Justify. 0, 1,2,3,4 2n and your calculated values. (e) What formula does that give you for the exact number of comparisons for heap creation as a function of n?

Explanation / Answer

a)

i) For a complete binary tree with height h, on level 0, 20 nodes are present.Level 2 has 21 nodes.Level 3 has 22 nodes ..... Level h has 2h-1 nodes .Hence total number of nodes = (20 + 21? + 22? + ....2h-1 )

This is GP its sum is -  20? ( 2h+1 - 1) / ( 2 -1 ) =  2h+1 - 1 nodes are present.

ii) As explained in above case, Tree with a height h has 2h - 1 nodes. Given number of nodes=n.Therefore

n = 2h - 1 --> h = log 2( n + 1 )

b) For conversion in binary heap, every element is compared with its child and if not found at correct position then it swapped with the appropriate child and then this procedure is repeated till the element is placed at its correct place.

Nodes of last level need not be compared as they do not have any child to be compared with.

For height 0,number of nodes = 1.Therefore no comparison is needed.

For height 1,number of nodes = 22 - 1 =3 .Nodes of last level will not be compared Node of level 0 will be compared will both of its child.and will be swapped if necessary.Only 2 comparisons are needed.

For height 2,number of nodes = 23 - 1 =7 .Nodes of last level will not be compared 2 Nodes of level 1 will be compared.Both the nodes at this level will be compared Now node at level 0 will be compared atmost 2 times as its subtree has height 1 Number of comparison needed. = 2* (1+1 + 2) = 8

For height 3,number of nodes = 24 - 1 =15 .Nodes of last level will not be compared 4 Nodes of level 2 will be compared only once.Now both nodes at level 1 will be compared atmost 2 times as its subtree has height 1 .Node at level 0 will be compared atmost 3 times as its subtree has height 2 Number of comparison needed. = 2* (1*4 + 2 *2 + 3*1)= 22

For height 4,number of nodes = 25 - 1 =31 .Nodes of last level will not be compared 8 Nodes of level 3 will be compared only once 4 Nodes of level 2 will be compared twice.Now both nodes at level 1 will be compared atmost 3 times as its subtree has height 2.Node at level 0 will be compared atmost 4 times as its subtree has height 3 Number of comparison needed. = 2 * (1*8 + 2 *4 + 3*2 + 4*1) = 52

Similarly for height 5, Number of comparison needed. = 2*(1*16 + 2 *8 + 3*4 + 4*2 + 5*1) = 114

Note that 2 is multiplied because of comparison with both children

c) For height 0,n=1 2*n - actual answer = 2 - 0 =2

For height 1,n=3 2*n - actual answer = 6 - 2 =4

For height 2,n=7 2*n - actual answer = 14 - 8 =6

For height 3,n=15 2*n - actual answer = 30 - 22 =8

For height 4,n=31 2*n - actual answer = 62 - 52 =10

For height 5,n=63 2*n - actual answer = 126 - 114 = 12

d) You can see that difference is following a pattern of 2*(h+1) where h is the height of the tree.It is calculated that  

h = log 2( n + 1 ) .Hence difference as a function of n is 2*( log 2( n + 1 ) +1).

e) Since actual comparisons are less than the expexcted ones and hence, exact number of comparisons are

2*n - 2*( log 2( n + 1 ) +1).

Hope i have answered your question satisfactorily.Leave doubts in comment section if any

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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