Assume that you need to keep track of some data. To store those data, you have the following options: a. A linked list maintained in sorted order.
b. A linked list of unsorted records.
c. A binary search tree.
d. An array maintained in sorted order.
e. An array of unsorted records.

For each of the following scenarios, which of above choices would be the best (i. e. you will pick)

1. The records are guaranteed to arrive already sorted from lowest to high- est (i. e., whenever a record is inserted, its key value will always be greater than that of the last record inserted). A total of 1000 inserts will be interspersed with 1000 searches.
2. The records arrive with values having a uniform random distribution (so the BST is likely to be well balanced). 1,000,000 insertions are performed, followed by 10 searches.
3. The records arrive with values having a uniform random distribution (so the BST is likely to be well balanced). 1000 insertions are interspersed with 1000 searches.
4. The records arrive with values having a uniform random distribution (so the BST is likely to be well balanced). 1000 insertions are performed,