Chapter 12, Problem 1P

(a)

Program Plan Intro

To describes the asymptotic performance of TREE-INSERT for identical n -keys insertion into empty BST.

Explanation of Solution

The insertion in BST first find the suitable place for the node so that after adding the node the properties of the BST remains holds so it need to compare all the nodes with the key and find the successor of the key.

The TREE-INSERT algorithm chooses the suitable place for the node and inserts the key to the right of the rightmost sub-tree and rotates the tree so that the balancing of the tree remains the same.

The comparison of the key with each node of the tree takes the time of $\Theta (n^2)$ for n nodes of tree.

Thus, the algorithm TREE-INSERT takes total cost of $\Theta (n^2)$ .

(b)

Program Plan Intro

To explains the role of Boolean flag variable during insertion of key in BST.

Explanation of Solution

The flag is the temporary variable used to indicate the status of the insert operation. If the insertion operation is already insert another key in the tree then the value of flag variable will be false that means another insert operation is on the way and after the completion of the operation its values is updates to true.

The true value if the variable represent that it can perform the insertion operation without any issues.

When the insert operation starts it set the values of the flag variable to flag so that other process can identify that some operation is still running.

Thus, the Boolean variable has very important role in the insertion of key in the BST as to hold the status of the operation.

(c)

Program Plan Intro

To explaintime taken by the list of equal keys at x and insert z into the list.

Explanation of Solution

For the insertion of key into the equal to x that means the position is already marked and there is no need of comparisons then the algorithm performs the operations in the linear time.

In this case the insertion is depends upon the height of the tree and the number of node it have.

Thus, the operation is performed in constant linear time.

(d)

Program Plan Intro

To finds the worse-case performanceand expected running time for setting x to either x.left or x.right .

Explanation of Solution

The setting operation required some comparisons so that it found the suitable position for the key as right or left sub-tree of the BST so it uses the comparison algorithm that compare the key with all tree nodes.

The comparison takes total time of $\Theta (n^2)$ to compare the key with all the elements as the tree has total n nodes.

In worse-case it randomly choose the node as it right of left sub-tree of the same BST and the number of comparisons required to find the suitable position is maximum is $\Theta (n^2)$ .

The expected running tome of the algorithm is the equals to the depth of the tree that is $\lg n$ and the number of nodes in the tree so the expected time of the algorithm is $O(n\lg n)$ .