AVL tree in data structure and algorithm

What is an AVL tree?

What happens if the data entered into the binary search tree (BST) is in ordered form (ascending or descending). It will look like this:

AVL tree in data structure and algorithm Picture 1

In general, the worst-case performance of a binary search tree (BST) is close to linear search algorithms, ie Ο (n). With real-time data, we cannot predict the data pattern and its frequencies. Therefore, it is necessary to balance here to balance the existing binary search tree.

The AVL tree (short for the names of A delson inventors, V elski and L andis) is a highly balanced binary search tree. The AVL plants check the height of the left seedlings and the right seedling and make sure that the difference between them is not greater than 1. This difference is called the Balance Factor .

Below is an example of an illustration of three trees in which the first tree is balanced, the second and third are unbalanced.

AVL tree in data structure and algorithm Picture 2

In the second tree, the tree on the left of C has an elevation of 2 and the right subtree has a height of 0, so the difference is 2. In the third tree, the right subtree of A has the height of 2 and the tree on the left has a height of 0, so the difference is also 2. While the AVL tree only accepts the difference (or Equilibrium factor) of 1.

 BalanceFactor = height(left-sutree) − height(right-sutree)

If the difference between the height of the left subtree and the right subtree is greater than 1, the tree is balanced by using some AVL rotation techniques shown below.

Technology of rotating AVL trees

To make the tree balance itself, an AVL tree can perform the following 4 types of rotation techniques:

Left rotation technique

Right turn technique

Left-right rotation technique

Right-to-left spin technique

The first two spinning techniques are single rotation techniques and the other two rotation techniques are rotation techniques.

In the next section, we will explore in detail each rotation technique with simple and easy-to-understand illustrations.

Fruit rotation technique AVL

If a tree becomes unbalanced when a node is inserted in the right subtree of the right subtree, we can perform a single left rotation technique as follows:

AVL tree in data structure and algorithm Picture 3

In the above illustration, node A becomes unbalanced when a node (node ​​C) is inserted into the subtree to the right of the right subtree of node A. We perform a left-turning technique to make A a tree. left child of B.

The technique turns to the AVL tree

The AVL tree becomes unbalanced if a node is inserted into the subtree to the left of the left subtree. In order to balance the tree, we must make the right rotation as follows:

AVL tree in data structure and algorithm Picture 4

As shown in the figure, an unbalanced node will become the right subtree of its left seedling by right-turning technique.

Technique turns left-right AVL tree

The rotation technique is quite complicated compared to the two techniques of the single rotation just introduced above. In order to understand this rotation technique faster, you need to note each action that is taken while recording. A left-right rotation technique is a combination of left-turning technique followed by right-turning technique.

Action Status AVL tree in data structure and algorithm Picture 5 A button has been inserted in the right subtree of the left subtree. This makes the C node unbalanced. With this situation, the AVL tree can perform left-right rotation. AVL tree in data structure and algorithm Picture 6 First, make a left rotation on the left subtree of C. This makes A the left subtree of B. AVL tree in data structure and algorithm Picture 7 Now button C is still unbalanced, that is due to the appearance of the seedling to the left of the seedling to the left. AVL tree in data structure and algorithm Picture 8 Now we will perform the right rotation technique to make B become the new root node of this tree. The C button now becomes the right subtree of its own left tree. AVL tree in data structure and algorithm Picture 9 Now the tree is balanced.

Right-fruit rotation technology AVL

Another type of rotation technique is the right-to-left rotation technique. This technique is a combination of rotation techniques that must be followed by left-turning techniques.

Action Status AVL tree in data structure and algorithm Picture 10 A button has been inserted in the subtree to the left of the right subtree. This makes the A button become unbalanced because the Balance Factor is 2. AVL tree in data structure and algorithm Picture 11 First, we perform the right-turning technique with node C, making C become a subtree to the right of the subtree on the left B. Now, node B becomes the right subtree of node A. AVL tree in data structure and algorithm Picture 12 Now button A is still unbalanced because of the right subtree of its right subtree. Therefore it is necessary to implement a left rotation technique. AVL tree in data structure and algorithm Picture 13 A left-turning technique is done to make B the new root node of the seedling. Button A becomes the left subtree of its right subtree B. AVL tree in data structure and algorithm Picture 14 Now the tree is balanced.

According to Tutorialspoint

Previous article: Binary Search Tree (Binary Search Tree)

Next lesson: Spanning Tree in data structure and algorithm