Описание тега avl-tree

Названное в честь его изобретателей Адельсона-Вельского и Ландиса, дерево AVL представляет собой самобалансирующееся двоичное дерево поиска. Это были первые предложенные динамически сбалансированные деревья.

Подобно красно-черным деревьям, они не идеально сбалансированы, но пары поддеревьев различаются по высоте не более чем на 1, что обеспечивает время поиска O(logn).