# 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 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 all operations take $O(h)$ time and $h$ can be as large as $n$

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]