The AVL tree is similar to the self-balancing red-black tree, but instead of augmenting a binary search tree with a colour to help it achieve it’s balancing goals, it keeps track of the height of each node. Usage: Enter an integer key and click the Search button to search the key in the tree. Preemtive Split / Merge (Even max degree only) Animation Speed: w: h: Click the Remove button to remove the key from the tree.

In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. An Example Tree that is an AVL Tree The above tree is AVL because differences between heights of left and right subtrees for every node is less than or equal to 1. For the best display, use integers between 0 and 99. AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. Click the Insert button to insert the key into the tree. When the height of the node’s children are not balanced, a rebalancing operation is performed.