Binary search tree
Idea: 


Advantages: 

Disadvantages: 

[You can download the application for offline viewing.]
Exercise 1: Play around with the applet above. Try creating a binary search tree storing elements {1,2,3,$\ldots$,$n$} with the maximum height $n$. How many different BSTs have height $n$?
Exercise 2: Now, try creating a BST storing {1,2,3,$\ldots$,$n$} with minimum height. How many such BSTs are there?
Exercise 3: How many different BSTs are there storing elements {1,2,3,$\ldots$,$n$}?
Tip: Type some number $n$ into the input box and press “Random” to insert random $n$ elements and observe the performance of the data structure on random data. What is the average height of the tree?
Exercise: Let’s take a BST, delete one of its elements and then reinsert it. When do we get the same BST with which we started?
References
 A. Andersson. A note on searching in a binary search tree. Software: Practice and Experience, 21(10):11251128, 1991. [bib] [pdf]
 Jeffrey L Eppinger. An empirical study of insertion and deletion in binary search trees. Communications of the ACM, 26(9):663669, 1983. [bib] [pdf]
 B. Reed. The height of a random binary search tree. Journal of the ACM, 50(3):306332, 2003. [bib] [pdf]