Please read the instructions carefully before any expert answer it.

Implement the AA tree in C++. You can find instructions on how such a tree operates online.

1.Submit the code which inserts 10000 randomly-generated items into your binary search tree

2. Prints the maximum depth of the tree and Prints all items in sorted order.

3 .Also, compare the timing of inserting 10000 items into a heap with the timing of inserting 10000 items into an AA tree.

4. Also, count swaps that occur in a heap and the tree rotation/balancing operations.

5. Report all of those statistics at your programs exit.