This project implements an applet to perform experiments on random binary search trees.
The implication of the random experiments is that the height of a random search tree is much less than many people would naively estimate prior to performing the experiments.
The tree size has been limited to 100000 to keep the time required for computation within reason. Even so, the user should expect to wait several minutes for a set of 1000 height experiments with trees of size 100000 to complete.
For trees of size up to 100000, the random height is usually between 2 and 3 times the log-base-2 of (tree_size+1) although occasionally it is greater.
To permit the user to explore the random trees in a graphical fashion, the topmost nodes of a tree are “live” and are painted in red. If you pause the mouse over such a node, the value within the node is displayed in the lower right of the window. Furthermore, if you click on the node the subtree based at that node will be displayed. This feature acts as a “zoom” into the depth of the tree. Finally, a button will appear that will let you view the full tree once more.
These graphical features enable you to explore the “fractal” nature of random insertion into a binary search tree.
→Tree Graph Experiment Images
→Tree Height Experiment Images
→Small Tree Images
The Java file
Note: This Java file may also be run as a Java application.