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