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
`To Start Press Any Key.'
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.
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
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
If you don't want to watch the animation (you just want to make some changes
to the tree) you can uncheck the
Clear button deletes whole tree, then
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.
insert, it will insert a random number (this does not hold for find or delete).
Pause, it will perform the action immediately, without animation – in this way you can quickly generate the tree you want).
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.
#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).