1962 год
Московские математики Г.М.Адельсон-Вельский и Е.М.Ландис предложили схему самобалансирующегося поискового дерева. Для балансировки дерева требуется произвести каждый раз небольшие преобразования, которые затрагивают не более трех узлов.
Высота дерева – длина наибольшего пути в этом дереве.
Вершина дерева называется сбалансированной, если высота ее левого и правого поддерева отличается не более чем на 1.
Дерево называется подравненным, если все его вершины сбалансированы.
При добавлении в дерево новых вершин, некоторые вершины могут стать несбалансированными. Сбалансированность может пропасть только у вершин, лежащих на пути от корня дерева к новой вершине, и разность высот достигает значения 2.
Обозначим a самую нижнюю вершину с нарушенным балансом. Две следующие вершины на этом пути обозначим как b и c.
Возможные схемы взаимного расположения вершин (для нижней части дерева вниз от a) для случая, когда левый путь длиннее правого на 2, изображен на рисунке.
Все остальные части дерева изображены условными блоками. Достаточно небольшого изменения вершин a, b, c и прицепленных к ним деревьев, чтобы балланс восстановился во всех вершинах. Эти изменения представлены на рисунке.
Фактически нужна только одна операция – поднятие вершины на один уровень наверх. Для первого случая нужно поднять наверх вершину b один раз, а во втором случае – вершину c два раза.
В настоящее время в некоторых схемах, где требуется быстрый доступ к часто меняющейся информации, применяется адаптирующееся дерево, основанное на АВЛ-преобразованиях.
В современных информационных системах данные хранятся преимущественно во внешней памяти, а время, расходуемое на одно обращение к диску существенно больше времени, требуемого на сопутствующие вычисления.
Поэтому целесообразно в каждом узле дерева ветвить поиск не на два варианта, а на много.
В информационных системах АВЛ деревья уступили место более прогрессивной конструкции В-дерева и различным его обобщениям.
Различные классы балансирующихся двоичных деревьев и В-деревьев рассмотрены в книге Т.Кормен, Ч.Лейзерсон, З. Ривест Алгоритмы: построение и анализ. М.:МЦНМО, 1999.-960 с.