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?
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.
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]]
If x is a none root node in a binomial tree within a binomial heap, how does degree[x] compare to degree[p[x]]?
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]
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 1’s in its binary representation. How many binary k-strings are there that contains exactly j 1’s ? Show that the degree of x is equal to the number of 1’s to the right of the right most 0 in the binary representation of 1’s.