Make your own free website on Tripod.com

Assignment 7

 

Exercise 19.1-1

Suppose that x is a node in a binomial tree within a binomial heap, and assume that sibling[x] ≠ NIL. If x is not a root, how does degree[sibling[x]] compare to degree[x]? How about if x is a root?

Answer:

By definition of B5.2 (page 1088): The number of children in a node x in a rooted tree T is called the degree of x.

Also if two nodes have the same parent, they are siblings.

Oval: ROval: R

 

 

 

 

 


(a) (b)

If sibling[x] is immediate to the right of x (see (a) above) then:

Degree[sibling[x]] = degree[x] - 1

If sibling[x] is immediate to the left of x (see (b) above) then:

Degree[sibling[x]] = degree[x] + 1

 

From the min-heap property (page 129) is that for every node i other than the root A[PARENT(i)] ≤ A[i]. The smallest element in a min-heap is at the root.

Also root x is linked to its sibling (root) together known as linked list. The degree of the roots strictly increase as we traverse the root list degree of x cannot be equal to its immediate right root.

Therefore if x is a root then degree[x] < degree[sibling[x]]

 

Exercise 19.1-2

If x is a none root node in a binomial tree within a binomial heap, how does degree[x] compare to degree[p[x]]?

Answer:

The degree[p[x]] contains the pointer to it parent , that means degree[p[x]] = degree[x] + P (some value of P).If x is the most left child then

degree[p[x]] = degree[x] + 1.

Other word degree[p[x]] is always greater than degree[x]:

degree[p[x]] > degree[x]

 

 

Exercise 19.1-3

Suppose we label the nodes of binomial tree Bk in binary by a postorder walk, as in figure 19.4. Consider a node x labeled l at depth i, and let j = k i . Show that x has j 1s in its binary representation. How many binary k-strings are there that contains exactly j 1s ? Show that the degree of x is equal to the number of 1s to the right of the right most 0 in the binary representation of 1s.

Answer: