An AVL tree is a self-balancing binary search tree where the heights of two child subtrees of a node will differ by a maximum of 1. If the height increases, in any case, there will be a rebalance to make the height difference to 1. This gives the AVL tree an added advantage of logarithmic complexity for different operations. Here is an example of an AVL tree: