Самостоятельная работа-2 Студент: 3 курс Группа: ки-12-20(С)(Р)

АВЛ-деревья

В 1962 году советские математики Адельсон-Вельский Г.М. и Ландис Е.А. предложили метод балансировки, требующий после включения или исключения узла лишь локальные изменения вдоль пути от корня к данному узлу, то есть времени не более O(log2n). При этом деревьям разрешается отклоняться от идеальной сбалансированности, но в небольшой степени, чтобы среднее время доступа к узлам было лишь немногим больше, чем в идеально сбалансированном дереве. Такие деревья называются АВЛ-деревьями.
Критерий сбалансированности АВЛ-дерева. Дерево называется сбалансированным тогда и только тогда, когда для каждого его узла высоты его левого и правого поддеревьев отличаются не более чем на единицу.
Примеры АВЛ-сбалансированных деревьев:

Уровень 0 Уровень 1 Уровень 2 Уровень 3

Примеры деревьев, не являющихся АВЛ-сбалансированными:

Уровень 0 Уровень 1 Уровень 2 Уровень 3

Для каждого узла дерева можно определить показатель сбалансированности как разность между высотой правого и левого поддерева данного узла. Пусть h_R - высота правого поддерева, - высота левого. Тогда показатель сбалансированности есть h_R - h_L.
Если дерево АВЛ-сбалансировано, то для каждого узла выполняется: |h_R - h_L| <= 1. Если хотя бы для одного узла дерева это не так, то дерево не является АВЛ-сбалансированным. Приведем примеры АВЛ-сбалансированного и АВЛ-несбалансированного дерева (у каждого узла указан показатель сбалансированности):

АВЛ-сбалансированное дерево

АВЛ-несбалансированное дерево