Question

Suppose that d ≥ 2 is an integer constant. In a d-ary tree, each node has at most d nonempty subtrees. For example, the trees discussed along with heaps had d = 2. We can represent a nearly complete d-ary tree with n nodes using an array whose indexes range from 0 to n−1. (This is different from Cormen’s arrays, whose indexes range from 1 to n.)
      Suppose that i is the index of a node in the array. Then CHILD(i, j) is the index of the jth child of the node at i, where 1 ≤ j ≤ d. If there is no such child, then CHILD(i, j) ≥ n. Also, PARENT(i) is the index of the parent of the node at i. If there is no such parent, then PARENT(i) < 0.

1a. Show a short algorithm for CHILD. Your algorithm must run in Θ(1) time.

1b. Show a short algorithm for PARENT. Your algorithm must run in Θ(1) time.

Answer 1

Answer:

• If the height of this tree h anywhere the root node is by the side of height 0, after that this tree will have minimum number of nodes equivalent to

• 1+ d + d2 + d3 + .... + dh-1 + 1 = (dh - 1)/(d-1) + 1 and maximum height force be 1+ d + d2 + d3 + .... + dh-1 + dh = (dh+1-1)/(d-1)

• used for any node at index i , after that index of its child node will range as of d*i+1 to d*i + d , where d*i+1 is the directory of leftmost child and d*i + d is the index of rightmost child.

in the same way if j is the index of a node, afterward index of its parent will be ( j-1) / d.

• We can prove that for any index in the choice d*i+1 to d*i+d, the value after subtraction with 1 as well as dividing by d and attractive the quotient part only, we obtain index i i.e. parent index.

• So under is the algorithm by

a. The short algorithm for child run time consider by:

CHILD( i, j)

1. child_index = i*d + j

2. Return (child_index) //If the child do exist then value returned will be >= n

b.The short algorithm for parent run time consider by:

PARENT(i )

1. If i == 0 then return -1; //as root node do not have parent

2. Return (i-1)/d //Return correct index

Both algorithm take time \Theta(1).