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:
  1. 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

    xny

  2. 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:


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