Binary search trees

Java applet visualizing numerous binary search tree; too bad you can't see it

This applet animates the functioning of several dictionary data structures. It can be used as a teaching aid or for self-study. By watching the visualization the user should more easily grasp the ideas behind the data structures.

standalone version for download

Usage

`To Start Press Any Key.'
Where's the ANY key?
Homer Simpson

The main parts

In the upper region there is a menu of trees you would like to visualize. You can choose either Binary Search Tree (BST), AVL tree, B tree, Red-black tree, AA tree, Skip list, Heap, Treap, Scapegoat tree, or Splay tree.

Controls

To insert, find or delete an element from a tree, write the input into the text field. (Input is an integer from 0 to 99 (inclusive); lower or greater numbers will be changed to 0 or 99.) Then press Insert, Find or Delete and the operation will start.

The animation pauses after each step of an algorithm. The step is commented on the right panel. You can proceed with the animation, by pressing the Next button.

If you don't want to watch the animation (you just want to make some changes to the tree) you can uncheck the Pause box.

The Clear button deletes whole tree, then Random button inserts 10 random numbers to the tree (you can use it to generate a random tree).

If you check the Small box, the applet will draw smaller trees. However, if you have high enough resolution, you may prefer the bigger version of the applet – trees won't fill your screen so quickly there.

Advanced usage

• If you don't type anything in the input box and press insert, it will insert a random number (this does not hold for find or delete).
• You can type several values into the input box separated by spaces and the press some action button (it will insert/find/delete these numbers one by one; if you uncheck Pause, it will perform the action immediately, without animation – in this way you can quickly generate the tree you want).
• If you type n in the input box and press random, it will insert n random numbers; or, if the input box is empty, it will insert 10 numbers by default

Statistics

Statistics of the data structures are in the last line of the control panel.

• Size — the number of nodes of the tree
• Height — height of the tree (number of levels; this is closely related to the worst case number of comparisons needed to find some node), expressed also as a multiple of the height of a perfectly balanced tree (for example if AVL-tree with 54 nodes has height 7, the optimal tree would have height 6, so the height of that AVL-tree is approximately 1.17-times the optimal height).
• Ave. depth — average node depth, i.e. sum of depth(v) for all vertices v divided by size(T); this is related to the average number of comparisons needed to find a give node.
• #Nodes and #Keys — in B-trees we can store several keys in one node, thus we discriminate these in statistics
• #Deleted — in a scapegoat-tree we count the number of deleted nodes — if this is greater than half the number of nodes, the tree is rebuilt.
• #Excess nodes — is the number of the excess nodes (allé nodes except the left and right sentinels and the bottom level).