申論題

9. (3 points) A binary search tree is a tree where every n node has at most two children. For ease of discussion we assume that every y node has a distinct key. In addition, all keys in the left subtree are smaller than the key of root, and all keys in the right subtree are larger than the key of the root. A tree node is a leaf if it does not have any children. The height of the tree is the length of the longest path from the root to a leaf. The successor of a node z is the node right after a in increasing order, and the predecessor of a node z is the node right before z in increasing order.
 1. We can locate the smallest key in a binary search tree in O(h) time in the worst case, where h is the height of the tree.
 2. The height of a binary search tree of n nodes is O(logn.).
3. We can locate the Largest key in a binary search tree in O(logn) time in the worst case, where n is the number of the nodes in the tree.
 4. Assume that a node z has two children. We can remove z while still mainteining the sorted order by locating its successor y, connecting y's parent directly to the only child of y (if there is one, otherwise make it null), which effectively removes the node y from the tree, and replacing the key of z with that of y. 5. Assume that a node z has two children. We can remove z z while still maintaining the sorted order by locating its predecessor y, connecting y's parent directly to the only chid of y (iF there is one, otherwise make it null), which effectively removes the node y from the tree, and replacing the key of z with that of y.