Data Structure || AVL Tree

Name: I Putu Raka Natha Nugraha
NIM: 2301865552

AVL Tree is a type of binary search tree in which it balances itself according to the differences in height between the two sub-trees of a node (the delta/difference must be 1 or 0)

For example:

Example of a Binary Search Tree

As you can see 5 is the main node of this tree (the first node to be inserted) and all the other nodes have basically become sub-trees to this node according to its value and of course its insert order. This is how the normal binary search tree works, but this is not an AVL tree since the left and right sub-trees contain different heights.

The difference of the sub-trees renders the tree to be a non-AVL tree

In order to create a functioning AVL tree here we have to 'balance' the two sub-trees by a node rotation in which the main node is replaced by the sub tree that the balance is heavily leaning on. So we have to replace the main node (5) with a node one value lower of the main node, so either (3) or (6). However since the balance heavily favors the left sub-trees we are going to make (3) as the main node to make this BST an AVL tree.

The rotation of the original BST to an AVL tree

As I said, the (5) node functionality as the main node is replaced by (3) to balance the delta height between the two sub-trees. We create a pivot on the (3) node and pull it towards the main node, while erasing the child node (4) so that it can be a main node that still connects node (2) and (5), thus moving the node (4) to the left sub-tree of the node(5).

This is the finished AVL tree where the difference in height of the two sub-tree is 0 (condition of the height must be either 1 or 0)