The AVL tree is named after the initials of the surnames of its inventors, Adelson-Velskii and Landis. He came forward in the publication of an article in 1962: "An algorithm for the organization of information" ("An algorithm for the organization of information").



AVL tree are always balanced such that for all nodes, the height of the left branch does not differ by more than one unit of the height of the right branch or vice versa. With this form of equilibrium (or balance), the complexity of a search in one of these trees is always in order of complexity O (log n). The equilibrium factor can be stored directly on each node or be computed from the heights of the subtrees.