Что такое AVL-дерево?

Каждый узел в АВЛ-дереве отслеживает свою собственную высоту: количество ребер на самом длинном пути вниз к листу. Лист имеет высоту 1, а пустое поддерево считается высотой 0. На основе высоты двух дочерних узлов можно вычислить его фактор баланса: height(left) - height(right).

Узел считается сбалансированным, когда его фактор баланса равен -1, 0 или 1. Правило АВЛ-дерева простое: каждый отдельный узел должен оставаться сбалансированным все время. Всякий раз, когда вставка или удаление приводит к тому, что фактор баланса узла становится равным 2 или -2, дерево выполняет поворот: локальную перестановку нескольких указателей, которая восстанавливает баланс за константное время, не нарушая порядок дерева поиска.

Существует четыре случая поворота (лево-левый, право-правый, лево-правый, право-левый), но все они сводятся к двум строительным блокам: одиночному левому повороту и одиночному правому повороту. Вы создадите оба с нуля в следующих нескольких уроках.