An AVL Tree (Adelson-Velsky and Landis tree) is a self balancing binary search tree such that for every internal node of the tree the heights of the children of node can differ by at most 1. It uses four types of rotations to keep itself balanced and delete, insert and search take O(log N) time