AVL Trees

randerson112358

Dec 12, 2017·4 min read

An AVL Tree is a self balancing binary search tree (BST). It is named after Adelson-Velsky and Landis, the inventors of the AVL tree. The height of an AVL sub-tree can differ at most by 1. This allows us to search for an element in the AVL tree in log base 2 n time or O(log n), where n is the number of elements in the tree. As a matter of fact this allows for operations such as max, min, insertion, and deletion to all be O( log n).

AVL Tree Insertion

When inserting values into the AVL tree, the tree may become unbalanced, we can check if it is balanced or not by using the balance factor to make sure the height of the sub-tree doesn’t differ by more than 1.

The balance factor of a node (N) in a binary tree is defined as the height difference.

BalanceFactor(N) = Height(RightSubtree(N) ) — Height(LeftSubtree(N))
or
BalanceFactor(N) = Height(LeftSubtree(N)) — Height(RightSubtree(N) )
BalanceFactor(N) belongs to the set {-1,0,1}

If the balance factor doesn’t equal -1,0, or 1 then our tree is unbalanced, and we need to perform certain operations to balance the tree. Specifically we need to do one or more of 4 tree rotations (Left Rotation, Right Rotation, Left Right Rotation, Right Left Rotation).

There are 4 cases to balance an AVL Tree

Right Right Case: Left Rotation

When a node is inserted in the right subtree of the right subtree and the tree becomes unbalanced, meaning the balance factor of a node/subtree isn’t -1, 0, or 1, then we need to perform a left rotation.

Left Left Case: Right Rotation

When a node is inserted in the left subtree of the left subtree and the tree becomes unbalanced, meaning the balance factor of a node/subtree isn’t -1, 0, or 1, then we need to perform a left rotation.

Left Right Case & Rotation:

A left right rotation is a combination of the left rotation followed by a right rotation. This occurs when a node is inserted into the right subtree of the left subtree, and the tree becomes unbalanced. First we need to execute the left rotation on the left subtree, note the node will still be unbalanced because of the left subtree of the left subtree. Next we need to perform the right rotation to balance the tree.

Right Left Case & Rotation:

A right left rotation is a combination of the right rotation followed by a left rotation. This is another type of double rotation like the left right rotation. This operation needs to be performed when a node is inserted into the left subtree of the right subtree and the tree becomes unbalanced. The first thing we do is perform the right rotation followed by the left rotation to balance the tree.

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )