Дерево козла отпущения, возможно, имеет самый простой для понимания алгоритм определения баланса. Если какая-либо вставка приводит к тому, что новый узел становится слишком глубоким, он находит узел, вокруг которого необходимо выполнить балансировку, рассматривая баланс веса, а не баланс высоты. Правило перебалансировки при удалении также простое. Он не хранит никакой тайной информации в узлах. Труднее доказать, что это правильно, но вам не нужно это понимать алгоритм ...
Однако, в отличие от AVL, он не всегда сбалансирован по высоте. Как и красно-черный, его дисбаланс ограничен, но в отличие от красно-черного он настраивается с помощью параметра, поэтому для большинства практических целей он выглядит настолько сбалансированным, насколько это необходимо. Я подозреваю, что если вы настроите его слишком плотно, он окажется плохим или хуже, чем AVL для худших вставок.
Ответ на вопрос edit
Я предоставлю свой личный путь к пониманию деревьев AVL.
Сначала вы должны понять, что такое ротация деревьев, поэтому игнорируйте все остальное, что вы когда-либо слышали алгоритмы AVL, и поймите это. Получите прямо в своей голове, который является вращением вправо и вращением влево, и то, что каждый из них делает с деревом, иначе описания точных методов просто запутают вас.
Далее, поймите, что хитрость для балансировки деревьев AVL заключается в том, что каждый узел записывает в нем разницу между высотой своего левого и правого поддеревьев. Определение «сбалансированной высоты» состоит в том, что это значение составляет от -1 до 1 включительно для каждого узла в дереве.
Далее, поймите, что если вы добавили или удалили узел, возможно, вы разбалансировали дерево. Но вы можете изменить только баланс узлов, которые являются предками добавленного или удаленного вами узла. Итак, что вы собираетесь сделать, это вернуться обратно к дереву, используя повороты, чтобы уравновесить любые несбалансированные узлы, которые вы найдете, и обновлять их баланс, пока дерево снова не будет сбалансировано.
Заключительная часть понимания этого состоит в том, чтобы найти в приличном справочнике конкретные вращения, используемые для балансировки каждого узла, который вы найдете: это его «техника» в отличие от высокой концепции. Вы должны помнить детали только при изменении кода дерева AVL или, возможно, во время экзаменов структур данных. Прошло много лет с тех пор, как в последний раз у меня был код дерева AVL настолько открытым, насколько он был открыт в отладчике - реализации, как правило, доходят до точки, где они работают, а затем продолжают работать. Поэтому я действительно не помню. Вы можете сортировать это на столе, используя несколько покерных фишек, но трудно быть уверенным, что у вас действительно есть все случаи (их немного). Лучше всего просто посмотреть.
Тогда нужно перевести все это в код.
Я не думаю, что просмотр списков кода очень помогает на любом этапе, кроме последнего, поэтому игнорируйте их. Даже в лучшем случае, когда код четко написан, он будет выглядеть как описание процесса из учебника, но без диаграмм. В более типичном случае это беспорядок манипулирования структурой C. Так что просто придерживайтесь книг.