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

Question

Хорошо, это еще один вопрос в области теории для парней CS.

В 90-е годы я довольно хорошо справлялся с реализацией BST. Единственное, что я никогда не мог разглядеть, это сложность алгоритма балансировки двоичного дерева (AVL).

Можете ли вы, ребята, помочь мне в этом?

Answer 1

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

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

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

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

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

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

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

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

Тогда есть бизнес, переводящий все это в код.

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

Answer 2

Я не думаю, что здесь полезно размещать полные коды для алгоритмов балансировки узлов, так как они становятся довольно большими. Однако статья Википедии о red-black trees содержит полную реализацию алгоритма C, а статья на AVL trees содержит несколько ссылок на высококачественные реализации.

Эти две реализации достаточно для большинства сценариев общего назначения.

Answer 3

Согласен, полная программа не подходит.

В то время как классическое дерево AVL и RB использует детерминированный подход, я бы предложил взглянуть на «Randomized binary search trees», которые являются менее дорогостоящими, чтобы сбалансировать и гарантировать хорошую балансировку независимо от статистического распределения ключей.

Answer 4

Дерево AVL неэффективно, потому что вы должны делать потенциально много поворотов на вставку/удаление.

Красно-черное дерево, вероятно, является лучшей альтернативой, поскольку вставки/удаления намного эффективнее. Эта структура гарантирует самый длинный путь к листу, не более чем в два раза кратчайший путь. Поэтому, будучи менее сбалансированным, чем дерево AVL, избегают худших несбалансированных случаев.

Если ваше дерево будет много раз читаться и не будет изменено после его создания, может оказаться полезным накладные расходы на полностью сбалансированное дерево AVL. Кроме того, для дерева Red-Black требуется один дополнительный бит памяти для каждого узла, который дает «цвет» узла.

Answer 5

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

Лучшая помощь, которую я смог найти, как сбалансировать их, - это поиск в google.

Я просто кодировал этот псевдокод (если вы понимаете, как делать вращения, его довольно легко реализовать).

IF tree is right heavy 
{ 
    IF tree's right subtree is left heavy 
    { 
    Perform Double Left rotation 
    } 
    ELSE 
    { 
    Perform Single Left rotation 
    } 
} 
ELSE IF tree is left heavy 
{ 
    IF tree's left subtree is right heavy 
    { 
    Perform Double Right rotation 
    } 
    ELSE 
    { 
    Perform Single Right rotation 
    } 
} 

Answer 6

Для балансировки дерева AVL я просто написал кучу функций, которые, как я думал, делятся со всеми здесь. Я предполагаю, что эта реализация безупречна. Запросы/вопросы/критика, конечно, прием:

http://uploading.com/files/5883f1c7/AVL_Balance.cpp/

Будучи новичком в Stackoverflow, я попытался разместить свой код здесь, но застрял с плохими вопросы форматирования. Итак, загрузите файл по указанной выше ссылке.

Cheers.

Answer 7

Существует полная реализация самобалансирующегося avl-дерева @http://code.google.com/p/self-balancing-avl-tree/. он также реализует логарифмическое время конкатенации и сплит-операций, а также карты/мультимарочные коллекции