An AVL Tree is a self-balancing binary tree that improves the worst-case searching times of a binary tree. First we have to consider a scenario when a regular Binary Tree would not search through data quickly. What would happen if elements were inserted in order? Elements would always be added to the right subtree. The result would be a tree that looks more like a Linked List.
The problem is that the tree is becoming “unbalanced”. That is, one side of the tree has more height that the other side. A balanced tree will have a height difference between its two subtrees of at most 2. This is where the AVL Tree comes in. An AVL Tree is constantly rebalancing itself to assure that no node ever has a child-height difference of more than 1. In fact, since an AVL Tree rebalances itself every time it is modified (a value is added or removed), the balance factor will never be more than 2.
Balancing an AVL Tree is accomplished by “rotating” groups of nodes left or right. A rotation is basically done by switching the parent-child relationships of a node and either it’s left or right subtree. It sounds simple in theory but in practice care must be exercised to make sure all references are update appropriately.
Rotating nodes might sound like a way to mess up the Binary Tree property that states greater elements must be in right subtrees and lesser elements in left subtrees. However since different rotations are applied depending on the balance factor of the AVL Tree, the property is always preserved. Thus an AVL Tree makes searching times constant no matter how data is inserted or removed.
