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.'

Where's the `ANY`

key?

Homer Simpson

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
`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.

- 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 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).