Animated Binary Tree

This Java applet started with an implementation of an AVL Tree. This is the self-balancing binary search tree invented by G.M Adelson-Belskii and E. M. Landis.

In an AVL tree, when a new node is added or removed, the tree is checked and re-balanced if any of the leaf nodes is more than 1 level different from the other leaf nodes. By keeping the tree in balance, it maintains O(log n) performance for searches.

The keys in my tree are floating point numbers. Enter keys into the text field and watch the tree form.

Design Notes

This is my first attempt at animation. I doubt that my design is the most elegant, but it has the virtue that it works.

Animator Package

This package serves as the foundation for the animations. It provides the Animator class, which extends javax.swing.Timer. It allows users to query for the fraction that represents the amount of time, to calculate how far an object should be moved or changed.

I also needed to coordinate the relationship between different actions, such as having the color of a parent node change when a new node reaches it. I have considered making some sort of "action sequence" class, but as I had started with individual actions with the Animator class, I added an AnimationSynchronizer class to put the animations in sequence. The AnimationSynchronizer keeps a list of the Animations to perform, and the Animations currently active. It starts the Animations as appropriate: Animations are allowed to be blocking -- other Animations have to wait on it -- or non-blocking. The client can also query to see if all of the Animations have completed.

AnimateNode Sub-Package

I created another level, between Animator and GraphicNode, to bridge them. AnimateNodeAction, the parent class, is an ActionListener for the Animator timer. An AnimateNodeAction has members to hold a sound effect, a client GraphNode, as well as the initial delay, and duration values for the timer. It provides a start() method which is called the first time actionPerformed() is called.

The rest of this package are specific actions. Some are animations:

  • AnimationNodeConnection -- extend a line from a node to its parent
  • AnimateNodePosition -- move a node
  • AnimateNodeColor -- change the color of a node
and others are regular method calls that need to be synchronized with the animations:
  • AnimateAllowResize -- Control when the pane can re-layout the tree due height changes
  • AnimationModelAction -- Allows the controller to synchronize the addition or removal of nodes
  • AnimateNodeRemove -- Allows node deletion to be in synch with changing node connections
  • AnimateNodeWait -- Waits for all animations to complete

The Rest of the View

The rest of the view is very similar to the Expression Parser. The main difference is that the model uses call-backs to update the view. The model tells the view which nodes it checks as possible parents, which nodes are being removed and which nodes are out of balance. A modified TreePane, AnimatedTreePane, sets up the appropriate animations that color nodes, moves and connects them.