I made an animation of items being added to a balanced binary tree (specifically AVL tree), and rotations of the tree nodes as the tree balances itself.
The number in the subscript is the height of a node (its distance from its deepest descendent leaf). The tree uses the height detail to balance itself. Essentially, balancing in the tree is achieved by making sure that for each node, the heights of its child nodes do not differ by more than one. If they do, the tree performs rotations to lower this difference. The animation shows some typical rotations as the tree balances itself.
Using the input data field, you can try your own numbers to see how items are inserted into the tree. Enter your custom values (comma separated), and hit enter to restart the animation with the new data.
The source code for this animation/demo can be found here. Kindly request permission before using / copying.
Comments