(1) Compute the internal path length, external path length, average numbers of comparisons for a successful search, and average number of comparisons for an unsuccessful search for BST (B).

(2) Using the algorithm described in class, show the result of deleting node 3 in BST (A)

(3) Using the algorithm described in class, show the result of deleting node 4 in BST (A)

(4) Using the algorithm described in class, show the result of deleting node 5 in BST (A)

(5) Show the result of inserting 3.5 in BST (B)

(6) Show how to transform BST (A) into BST (B) by performing 4 rotations. Draw all intermediate trees. Hint: Each rotation brings 7 one level up.

struct bnode

{

int data;

bnode *left, *right;

}; // Precondition:

bst != 0 bnode*& findmax(bnode*& root)

{

if (root == 0) { cerr right == 0) return root;

else

return findmax(root->right);

}

void Delete(bnode*& root, int val) {

bool found;

bnode*& bnp = Find(root, val, found);

if (!found) return;

if (bnp != 0) {

if (bnp->left == 0 && bnp->right == 0)

{

delete bnp; bnp = 0;

}

else if (bnp->left == 0) {

bnode* bnp2 = bnp; bnp = bnp->right;

delete bnp2;

}

else if (bnp->right == 0) {

bnode* bnp2 = bnp; bnp = bnp->left; delete bnp2;

}

else {

bnode*& bnp2 = findmax(bnp->left); bnp->data = bnp2->data;

bnode* t = bnp2; bnp2 = bnp2->left;

delete t;

}

}

}

5 10 4 8 6 7 10 5 10 4 8 6 7 10