AVL and BST Trees applet

The applet displays a collection of integers, organized in two ways: as a binary search tree (BST), and as an AVL tree. The stored numbers involved are the same in both cases, but the structure of the two trees is different. I assume that you know the basic properties of these trees:

In a binary search tree (BST) each node holds a data, in our case an int. If n is an integer at some node N, then for any x in the left subtree, and any y in the right subtree of N, we have

x ≤ n ≤ y

A binary search tree T is called an AVL tree, named after its inventors G. M. Adelson-Velskii and E. M. Landis, if in addition to the condition 1, the following is true: Let N be any node in the tree, and let L be the left subtree of N, and let R be the right subtree of N. Then

│height(L) - height(R)│ ≤ 1

For the discussion of the concept, its importance, and what not, see for example M. A. Weiss, Data Structures and Algorithm Analysis in Java, Second edition, Addison Wesley, Chapter 4, but the subject is also discussed in many other places.

This page displays an applet showing the two trees: AVL and BST. Both trees contain the same set of data, it's just the organization of this data is different in each of the trees.

The page gives the basic description of the trees and the instructions for navigating and massaging these trees. To display the trees, click on the bluish button, labeled "Display the AVL-BST Trees". Depending on your security setting, a yellow bar at the top of the page may appear warning you that running this applet ("ActiveX controls" it will say) maybe dangerous. In that case, click on this yellow bar and allow the applet to be run. Trust me. In any case, after you click on the bluish button, the tree will appear in a separate window. You may resize the window, minimize it (in which case its icon will appear in the bottom tray so you can restore it), or close it altogether. If this last action is taken, you must click on the bluish button again to restore the applet.

Some basic comments about the functionality of the applet:

The program opens with the empty collection, i.e., both trees are empty.
To insert or delete a number, press the appropriate button, you will be prompted to enter the number you wish to add or delete. If you try to delete a number not in the collection, the command is ignored. No duplicates are allowed and request to add a number already in the collection is ignored.
To add a random collection of numbers to the existing trees, press the "Random Tree" button. You will be asked how many items are to be added, all the new items will be in the range 1 to 1000. Keep in mind that these numbers will be added to the existing collection, the old numbers will still be there.
The "Rest All" button clears the collection, and both trees become empty.
"Display Properties" on the menu bar. You can select one of the following options for the display of the nodes:

Data in each node and the height of the tree below
Data in the node only
An outline of the node only

The slider bar between the two panels maybe dragged left or right to give more room to one side or the other

Navigating the tree:

To display the content of a node, right click on a node and hold. The content of the node and the height of the tree below the chosen node will be displayed in a blue rectangle, for as long as you keep pressing the right button of the mouse. Mac users are encouraged to envision the action in their mind.
To display only a portion of either tree, left click the node you wish to emphasize. That node will become the root and the portion of the tree below that root will be displayed. The tree is not lost, see next item.
To "move the tree up one level" click in the upper left corner of the relevant pane
The displays of both trees are independent of each other, moving up or down of one has no effect on the display of the other.
After each addition and/or deletion, both trees are redrawn completely, with both the trees being displayed in their entirety. This is because the addition and/or deletion may cause the tree to change the shape. This is particularly true for an AVL tree.

Any comments are always welcomed: drobot@vdrobot.com
Back to Drobot's home page