5.1 Perfect Balance (8 points) Propose an algorithm which inserts a set of keys into an initially empty binary search tr

[answerhappygod]

5 1 Perfect Balance 8 Points Propose An Algorithm Which Inserts A Set Of Keys Into An Initially Empty Binary Search Tr 1 (56.03 KiB) Viewed 43 times

5.1 Perfect Balance (8 points) Propose an algorithm which inserts a set of keys into an initially empty binary search tree such that the tree produced is equivalent to binary search. This means the sequence of compares done in find() is the same as the sequence of compares used by binary search for the same key. Also analyze time complexity of this algorithm.. Hint: In binary search, we first compare current key with th key in the array, then compare current key with th key or th key in the array, etc. Solution: 5.2 BST with Duplicate keys (5 points) The binary search tree we introduced in the class does not support duplicate keys. By some modifications, we can make BST support duplicate keys. A simple approach is to change the rule of BST: the key smaller or equal to the current key goes to the left subtree, the key greater than the current key goes to the right subtree. However, a better solution is to add an additional field to each node called count, which is the number of current key in the binary search tree. Briefly introduce how to implement insert and remove in this kind of BST and explain why this approach is better than the first one. Solution: