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?
- If x is not a root, degree[sibling[x]] < degree[x]
- If x is a root, degree[sibling[x]] > degree[x]
If x is a nonroot node in a binomial tree within a binomial heap, how does degree[x] compare to degree[p[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 contain exactly j 1's? Show that the degree of x is equal to the number of 1's to the right of the rightmost 0 in the binary representation of l.
Follow @louis1992 on github to help finish this task.