Binary search tree

Idea:	all items are stored in a binary tree if $v$ is a node with item $x$, then all the smaller items are in the left subtree and all the larger items are in the right subtree
Advantages:	combines the advantages of sorted array (fast search) and linked list (flexibility when adding and deleting items) all operations take $O(h)$ time, where $h$ is the height of the tree (usually small) when the items are inserted in random order, the height is $O(\log n)$ with high probability
Disadvantages:	all operations take $O(h)$ time and $h$ can be as large as $n$

[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):1125-1128, 1991. [bib] [pdf]
Jeffrey L Eppinger. An empirical study of insertion and deletion in binary search trees. Communications of the ACM, 26(9):663-669, 1983. [bib] [pdf]
B. Reed. The height of a random binary search tree. Journal of the ACM, 50(3):306-332, 2003. [bib] [pdf]