Балансировка двоичного дерева (AVL)

Дерево козла отпущения возможно имеет самый простой алгоритм определения баланса для понимания. Если какая-либо вставка заставляет новый узел быть слишком глубоким, это находит узел, вокруг которого можно изменять баланс путем рассмотрения баланса веса, а не баланса высоты. Правило для того, изменять ли баланс на, удаляет, также просто. Это не хранит тайной информации в узлах. Это более хитро, чтобы доказать, что это корректно, но Вам не нужно это для понимания алгоритма...

Однако в отличие от AVL это не сбалансировано с высоты в любом случае. Как красно-черный ограничен его дисбаланс, но в отличие от красно-черного это является настраиваемым с параметром, таким образом, для наиболее практических целей это выглядит столь сбалансированным, как Вам нужен он, чтобы быть. Я подозреваю, что при настройке его слишком плотно, тем не менее, это заканчивается как плохое или хуже, чем AVL для вставок худшего случая.

Ответ на редактирование вопроса

я обеспечу свой персональный путь к пониманию деревьев AVL.

Первый необходимо понять, каково древовидное вращение, поэтому проигнорируйте все остальное, что Вы когда-либо слышали алгоритмы AVL и понимаете это. Станьте прямыми в голове, которая является правильным вращением и которая является левым вращением, и что каждый делает к дереву, или иначе описания точных методов просто смутят Вас.

Затем, понимают, что прием для балансировки деревьев AVL - то, что каждый узел записывает в ней различие между высотой его левых и правых поддеревьев. Определение 'высоты, сбалансированной', то, что это между-1 и 1 включительно для каждого узла в дереве.

Затем, понимают, что, если Вы добавили или удалили узел, Вы, возможно, разбалансировали дерево. Но можно было только изменить баланс узлов, которые являются предками узла, который Вы добавили или удалили. Так, что Вы собираетесь сделать, работать, Ваш путь создает резервную копию дерева, с помощью вращений для балансировки любых несбалансированных узлов, которые Вы находите, и обновление их счета баланса, пока дерево не сбалансировано снова.

заключительная часть понимания это должно искать в достойной ссылке определенные вращения, используемые для изменения баланса каждого узла, который Вы находите: это - "техника" его в противоположность высокому понятию. Только необходимо помнить детали при изменении кода дерева AVL или возможно во время экзаменов структур данных. Это - годы, с тех пор как у меня в последний раз был древовидный код AVL так как открытый в отладчике - реализации имеют тенденцию добираться до точки, где они работают и затем остаются рабочими. Таким образом, я действительно не помню. Можно отсортировать, разрабатывают его на таблице с помощью нескольких покерных фишек, но трудно быть уверенным, что Вы действительно получили все случаи (нет многих). Лучше всего только искать его.

Затем существует бизнес перевода всего этого в код.

я не думаю, что рассмотрение листингов кода помогает очень с любым этапом кроме последнего, поэтому проигнорируйте их. Даже в лучшем случае, где код ясно написан, он будет похож на описание учебника процесса, но без схем. В более типичном случае это - путаница управления структурой C. Поэтому просто придерживайтесь книг.