2. Delete a node in a Binary Search Tree (6 points) a) Implement the deletion of...

Transcribed Image Text:

2. Delete a node in a Binary Search Tree (6 points) a) Implement the deletion of a node from a BST as described the algorithm below. Delete(t, x) Find the node containing x. If x has no children then remove x from T. Return. If x has 1 child, then let s be that child. Remove x and makes a child of the parent of x. Return. If x has 2 children, then find the smallest node in the right subtree of x and let it be y. Assign the content of node y to node x and delete node y recursively. Return. b) Implement the deletion by merging method. - Root Delete node node node->left- -node->right Rightmost node of the left subtree Root node->left node->right DeleteByMerging(t, x) Find the node containing x. If x has no children or one child, process as in question a). If x has two children, attach the right subtree of x to the rightmost node of the left subtree. Then, attach the left subtree to the parent of x. Return. c) Write a program to compare these two methods of deletion. For each method, print out the BST (using the method written in Problem 1) after the deletion. 2. Delete a node in a Binary Search Tree (6 points) a) Implement the deletion of a node from a BST as described the algorithm below. Delete(t, x) Find the node containing x. If x has no children then remove x from T. Return. If x has 1 child, then let s be that child. Remove x and makes a child of the parent of x. Return. If x has 2 children, then find the smallest node in the right subtree of x and let it be y. Assign the content of node y to node x and delete node y recursively. Return. b) Implement the deletion by merging method. - Root Delete node node node->left- -node->right Rightmost node of the left subtree Root node->left node->right DeleteByMerging(t, x) Find the node containing x. If x has no children or one child, process as in question a). If x has two children, attach the right subtree of x to the rightmost node of the left subtree. Then, attach the left subtree to the parent of x. Return. c) Write a program to compare these two methods of deletion. For each method, print out the BST (using the method written in Problem 1) after the deletion.