Use classes BinarySearchTree, AVLTree, RedBlackBST, SplayTree to create four search

trees.

$1.$ For each tree:

a$)$ Insert $100,000$ integer keys, from $1$ to $100,000($ascending order$).$ Find the average time of

each insertion.

b$)$ Do $100,000$ searches of random integer keys between $1$ and $100,000.$ Find the average time

of each search.

c$)$ Delete all the keys in the trees, starting from $100,000$ down to $1($descending order$).$ Find the

average time of each deletion.

$2.$ For each tree:

a$)$ Insert $100,000$ random keys between $1$ and $100,000.$ Find the average time of each search.

b$)$ Repeat #$1.$b$.$

c$)$ Repeat #$1.$c$,$ but with random keys between $1$ and $100,000.$ Note that not all the keys can be

found in the tree.