AVL Tree

AVL TREE

---English Version---

Before we start to AVL Tree let's review Binary Search Tree (BST).

Binary Search Tree

This picture is the example of a skewed Binary Search Tree (BST). The left BST is inserted by 2, 5, 7, 8, and 13 respectively. 

The right BST is inserted by 9, 1, 6, 3, and 4 respectively.

AVL Tree

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 of all nodes.

Height of a node:

The height of an empty subtree is 0.

The height of a leaf is 1.

The height of an internal node is the maximum height of its children plus 1.

Balance factor:

The difference height of its LEFT subtree and its RIGHT subtree.

The balance factor of all nodes in the AVL Tree should be at most 1.

AVL Tree has two operations such as:

1. Insertion

2. Deletion

AVL Tree Operation (Insertion)

Look at the picture above, isn't it confusing? What should we do?. Okay, let me tell you. So, here is the step:

First, insert the new key as a new leaf just as in ordinary Binary Search Tree insert strategy. (Center Picture).

--But this may cause violation of AVL Tree property.--

Next, restore the balance condition. (Right Picture).

The steps to insertion are:

*First, insert the new key as a new leaf just as in ordinary Binary Search Tree insert strategy.
 But this may cause violation of AVL Tree property.

*Next, restore the balance condition. How?
 Trace the path from the new key to the root. For each node
 P encountered, check if heights of left(P) and right(P) differ by at most 1.
    -If Yes, proceed to the parent (P).
    -If No, fix sub tree P either by single rotation or double rotation.

 Rebalance AVL Tree

Why we have to rebalance AVL Tree and How to rebalance AVL Tree?.

We have to rebalance AVL Tree because after an insertion, only nodes that are on the path from the inserted node to the root that might violate the AVL property. Rebalance the tree at the deepest level of such nodes guarantees that the property of AVL Tree restored.

Rebalance of AVL Tree done by rotation.

Violation on (left-left or right-right) is fixed by a single rotation.

Violation on (left-right or right-left) is fixed by double rotation.

Single Rotation

Example:

 Node (12) is inserted in an AVL Tree and causing node (30) to violate the AVL property.

The picture on the left is the correct AVL Tree.

Double Rotation

Example:

 Node (26) is inserted in an AVL Tree and causing node (30) to violate the AVL property.

First rotation, node (27), and node (22).

Second rotation, node (27), and node (30).

AVL Tree Operations: Deletion

*Delete the node as in ordinary Binary Search Tree.

      -The deleted node will be a leaf or a node with one child.

*Trace the path from the (parent of) deleted leaf towards the root. For each node P encountered,            check if the height of left(P) and right(P) differ by at most 1.

     -If Yes, proceed to the parent(P).

     -If No, fix sub tree P either by single rotation or double rotation (as in insertion).

*After we perform rotation at P, we may have to perform a rotation at some ancestor of P. Thus, we      must continue to trace the path until we reach the root.

Delete node (60), node (55) is unbalanced.

Single rotation on the node (55)-------->

Node (50) is an unbalanced, double rotation on the node (50).

AVL Tree after deletion of the node (60). 

Let's Simulate the AVL Tree

First, insert node (1),(2),(3),(4),(5),(6),(7),(8),(9),(30),(50). See the pictures below.

 The picture above is the AVL Tree that has been balanced. We want to delete node (3),(4),(7), and (8).

First, delete the node (4).

Look at the picture on the left. Node to delete (node 4) has two children. Find the largest node in the left subtree

     



Copy the largest value of the left subtree into the node to delete.

This is the AVL tree after we delete the node (4).

After that, delete the node (3).

                     Deleting node 3.

 Found node to delete ( node 3).

Node to delete has two children. Find the largest node in the left subtree.

Remove the node whose value we copied.

                                           
                         Single rotate left.

This is the AVL tree after we delete the node (3).

After that, delete the node (7).

Searching for node 7: 7<8 (look to left subtree).

Searching for node 7: 7>2 (look to right subtree).

Searching for node 7: 7>6 (look to right subtree).

Searching for node 7: 7=7 (Element found).

Node to delete is a leaf. Delete it.

                      Unwinding recursion.

This is the AVL tree after we delete node (7) and do recursion.








After that, delete the node (8).

 
                     
                     Deleting node 8.

Node 8=8. Found node to delete.

Node to delete has two children. Find the largest node in the left subtree.

Copy the largest value of the left subtree into the node to delete.

Remove the node whose value we copied.

Adjusting height after the recursive call.

This is the AVL tree after we delete node (8) and do recursion.










After the long process, finally, from this AVL Tree, we have deleted node (3),(4),(7), and (8).


The picture below is the AVL Tree that has the node (1),(2),(3),(4),(5),(6),(7),(8),(9),(30),(50).


Then, the picture below is the AVL Tree after we delete the node (3),(4),(7), and (8).

References: -AV Tree simulator (https://www.cs.usfca.edu/~galles/visualization/AVLtree.html).
                    - Binus University resources Data Structures (AVL Tree Session 8).