Self Balancing BST

What is a Self Balancing BST?

A self balancing BST is one which always tries to maintain it’s height as minimum as possible. A clearer definition:

In computer science, a self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions - Wikipedia

This project implements the same with the method called AVL Trees (Adelson-Velsky-Landis Trees), invented by Georgy Adelson-Velsky and Evgenii Landis.

How to balance a tree?

Any tree can be brought to balance by a number of rotations. Rotations are mainly of two types:

Left Rotation
          this                          x
           / \       left-rotate       / \
        (T1)  x      ---------->    this (T3)
             / \                     / \
          (T2) (T3)               (T1) (T2)

    values(T1) < this < values(T2) < x < values(T3)
Right Rotation
           this                         x
           / \      right-rotate       / \
          x  (T3)   ----------->    (T1) this
         / \                              / \
      (T1) (T2)                        (T2) (T3)

    values(T1) < x < values(T2) < this < values(T3)

In the above illustrations, T1 ,T2 ,T3 are subtrees.

In both cases, the new BST formed can be looked at as a rotation about x.

AVL Trees - a quick look

The logic behind the successful working of these trees is that each node has a value associated with, called balance factor. It is given by balance factor = height(left sub-tree) - height(right sub-tree).

This method tries to make the balance factor of all nodes in the tree to be in the range {-1,0,1}. Height of a null subtree is treated as 0.

Whenever a node is inserted or deleted, it will check if the new balance factor of all nodes in all the subtrees in which the node in question belongs to, still come in the range. If not, it will do a rotation to make the balance factor come back in the range, thus making the tree balanced.