AVL-дерево

AVL-дерево было предложено Г.М. Адельсоном-Вельским и Е.М. Ландисом в 1962 году.

Дерево с вершинами называется сбалансированным по высоте, если для любой вершины разница высот её левого и правого поддеревьев не превышает единицы ().

Как уже отмечалось, это определение баланса является менее строгим в сравнении с идеально-сбалансированным деревом, но оно приводит к легко выполнимой балансировке, а средняя длина пути до идентификатора остается практически такой же, как и у идеально-сбалансированного дерева.

Представление AVL-дерева:,

где

INFO – информационное поле,

LLINK – указатель на левое поддерево,

RLINK – указатель на правое поддерево,

BAL – поле, отражающее разность высот левого и правого поддеревьев для этой вершины:

.

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