AVL tree

An AVL tree is a data structure that functions as a height-balanced binary search tree. For each node $x$, the heights of the left and right subtrees of $x$ differ by at most 1.