AVL Tree WITH PYTHON3

02 Aug 2020

Reading time ~4 minutes

What is an AVL tree?

AVL trees are named for the prefix alphabet of the people who wrote the first paper on them. The purpose of an AVL tree is to maintain the balance of a BST.

Basic Concepts

Binary Search Tree can be unbalanced, depending on the order of insertion. For example, let 1,2,3,4,5 be inserted into the BST. In this case, there is no difference from a list, that is, the time complexity to search is just O(N). In other words, the advantage of the BST would be lost. So, Maintaining the balance is really important in the BST. In the AVL tree, There are 2 basic rotation operations to maintain the balance. So, maintaining balance is critical to a BST. In the AVL tree, there are 2 basic rotation operations to maintain this balance.

Right Rotation

As shown above, right rotation makes every node move one position to the right from its current position. Basically, Beta moves from its current position to a position under the root. This happens because the Beta node value is larger than the value of the pivot node.

 B                                      A
/ \            Right Rotation          /  \
A   GAMMA      - - - - - - - >     ALPHA   B
/      \       < - - - - - - -            / \
ALPHA  BETA     Left Rotation          BETA  GAMMA

def rightRotate(self, z):
   y = z.left
   T3 = y.right

   y.right = z
   z.left = T3

   z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
   y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))

   return y

Left Rotation

Left rotation is implemented in the opposite way from right rotation.

def leftRotate(self, z):
    y = z.right
    T2 = y.left

    y.left = z
    z.right = T2

    z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
    y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))

    return y

Double Rotation

The explanations given above are for single rotation. But sometimes, it is not sufficient to rotate only once (perform single rotation). For example, let’s imagine a tree with in-order 3,1,2; neither left rotation nor right rotation can solve the imbalance. Therefore, we have to conduct double rotation, which is composed of RL(Right Left) and LR(Left Right) rotation.

RL(Right-Left) rotation.

RL rotation is a rotation that processes the right rotation and left rotation in that sequence. Let’s take a look at the case that 3,5,4 are inserted. First, let 4 be a pivot and rotate right. Then, let 5 be a pivot and rotate left. After that, the tree would be balanced. The following diagram depicts these processes.

 3                            3                              4
/ \                          / \                           /    \
A   5   Right Rotate (4)    A   4      Left Rotate(3)      3      5
  /  \  - - - - - - - - ->     /  \   - - - - - - - - -->  / \    / \
  4   B                        D   5                       A  D  C  B
 / \                              / \
 D C                              C   B

LR(Left-Right) rotation.

LR rotation is simply the opposite order of RL rotation.

3                               5                            4
/ \                            /   \                        /  \
4   B  Left Rotate (y)         4    B    Right Rotate(3)    3      5
/ \      - - - - - - - - ->  /  \      - - - - - - - ->    / \    / \
A   5                       3    C                          A  D C  B
/ \                       / \
D   C                    A   D

Balance Factor

How can we know whether the parts of a tree are balanced or not? How can we decide which rotation is appropriate? The answer to both of these questions is the Balance Factor. Balance factor is as follows.

Balance Factor = The height of the left tree - The height of the right tree.

The diagram below shows the steps needed to transform an unbalanced tree into a balanced tree.

Insertion of the AVL tree

If you understand the explanations so far, the insertion process of an AVL Tree will be easy to understand.
Let’s just take it step by step.

Insert the node as a BST tree.
Update the height value of the visited node.
Balance the tree through the rotations (with balance factor).

Note that the height of nodes have to be updated after the rotation is conducted.

That’s all. It seems to be quite easy, but the implementation is not really.

Time Complexity (Big O notation)

Both the time complexity of insertion and deletion are O(logN).