AVL Tree — это сбалансированное двоичное дерево поиска. В посте представлены бинарные деревья поиска. Время поиска, вставки и удаления двоичного дерева зависит от высоты дерева. В худшем случае высота равна O(n). Если дерево идеально сбалансировано – т.е. полное двоичное дерево – его высота равна log n. Можем ли мы сохранить идеально сбалансированное дерево? Да, но это будет стоить дорого. Компромисс состоит в том, чтобы поддерживать хорошо сбалансированное дерево — то есть, чтобы высоты двух поддеревьев каждого узла были примерно одинаковыми.

Деревья AVL хорошо сбалансированы. Деревья AVL были изобретены в 1962 году двумя российскими учеными-компьютерщиками Г. М. Адельсоном-Вельским и Э. М. Ландисом (отсюда и название AVL). В дереве AVL разница между высотами двух поддеревьев каждого узла равна 0 или 1. Можно показать, что максимальная высота AVL-дерева равна O(log n).

Процесс вставки или удаления элемента в дереве AVL такой же, как и в обычном двоичном дереве поиска, за исключением того, что вам может потребоваться перебалансировать дерево после операции вставки или удаления. коэффициент баланса узла — это высота его правого поддерева минус высота его левого поддерева. Узел называется сбалансированным, если его коэффициент балансировки равен -1, 0 или 1. Узел считается тяжелым слева, если его коэффициент баланса равен -1, и тяжелым справа, если его коэффициент баланса равен 1.