### 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.