Разница между красно-черными деревьями и деревьями AVL

Ответ 1

Деревья AVL поддерживают более жесткий баланс, чем красно-черные деревья. Путь от корня до самого глубокого листа в дереве AVL не более ~ 1,44 lg (n + 2), а в красных черных деревьях он не более ~ 2 lg (n + 1).

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

Ответ 2

Для небольших данных:

вставить: дерево RB и avl дерево имеют постоянное число максимального вращения, но дерево RB будет быстрее, потому что в среднем дерево RB использует меньшее вращение.

поиск: дерево AVL выполняется быстрее, поскольку дерево AVL имеет меньшую глубину.

удалить. Дерево RB имеет постоянное число максимального вращения, но дерево AVL может иметь O (log N) раз вращение как наихудшее. и в среднем дерево RB также имеет меньшее количество оборотов, поэтому дерево RB быстрее.

для больших данных:

вставить: дерево AVL выполняется быстрее. потому что перед вставкой вам нужно найти конкретный node. поскольку у вас больше данных, разница во времени при поиске конкретного node растет пропорционально O (log N). но дерево AVL и дерево RB все еще нуждаются в постоянном числе вращений в худшем случае. Таким образом, горловина бутылки станет временем, когда вы будете искать этот конкретный node.

поиск: дерево AVL работает быстрее. (так же, как в случае с маленькими данными)

удалить: дерево AVL в среднем быстрее, но в худшем случае дерево RB быстрее. потому что вам также нужно искать очень глубокую node для свопинга перед удалением (аналогично причине вставки). в среднем оба дерева имеют постоянное число вращений. но дерево RB имеет постоянную верхнюю границу для вращения.

Ответ 3

Цитата из этого: Разница между AVL и красно-черными деревьями

RB-деревья, а также деревья AVL, самобалансируются. Оба они обеспечивают O (log n) поиск и производительность вставки. Разница в том, что RB-деревья гарантируют O (1) вращения на операцию вставки. Это то, что на самом деле стоит производительность в реальных реализациях. Упрощенные, RB-деревья получают это преимущество от концептуального создания 2-3 деревьев, не несущих накладных расходов динамических структур node. Физически RB-деревья реализованы как двоичные деревья, красные/черные флаги имитируют поведение 2-3.

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

Ответ 4

Максимальная высота деревьев имеет первостепенное значение для поддержания равновесия. Он почти равен 1.44 * log(n) для AVL, но для дерева RB это 2 * log(n). Таким образом, мы можем прийти к выводу, что лучше использовать AVL, когда проблема является стимулом поиска. Важно еще один вопрос для дерева AVL и RB. Дерево RB лучше, чем AVL, когда сталкивается с случайной вставкой при меньшей стоимости вращения, но AVL, который хорош для вставки восходящих или нисходящих данных. Поэтому, если проблема заключается в стимуле внедрения, мы можем использовать дерево RB.

Ответ 5

Деревья AVL часто сравниваются с красно-черными деревьями, потому что они поддерживают один и тот же набор операций и принимают O(log n) время для основных операций. Для приложений с интенсивным поиском деревья AVL быстрее, чем красно-черные деревья, потому что они более жестко сбалансированы. Подобно красно-черным деревьям, деревья AVL сбалансированы по высоте. Оба они, как правило, не сбалансированы по весу, а μ-сбалансированы для любого μ ≤ ½; то есть узлы-братья могут иметь чрезвычайно различное количество потомков.

Из статьи Википедии на AVL Trees

Ответ 6

Из того, что я видел, кажется, что деревья AVL выполняют столько поворотов (иногда рекурсивно вверх по дереву), сколько необходимо, чтобы получить желаемую высоту дерева AVL (Log n). Это делает его более жестко сбалансированным.

Для красных черных деревьев существует 5 наборов правил, необходимых для того, чтобы вы могли оставаться в режиме вставки и удаления, которые вы можете найти здесь http://en.wikipedia.org/wiki/Red-black_tree.

Главное, что может помочь вам для красных черных деревьев, состоит в том, что в зависимости от этих пяти правил вы можете рекурсивно окрасить дерево до корня, если дядя красный. Если дядя черный, вам понадобится сделать максимум два оборота, чтобы исправить любые проблемы, которые у вас есть, но после этих двух или двух поворотов ВЫ СДЕЛАНЫ. Упакуйте его и говорите добрую ночь, потому что это конец манипуляции, который вам нужно сделать.

Большое правило - это номер 5...    "Каждый простой путь от данного node к любому из его потомков оставляет одно и то же число черных узлов".

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

Ответ 7

Вкратце: AvlTrees немного лучше сбалансированы, чем RedBlackTrees. Оба дерева берут O (log n) общее время для поиска, вставки и удаления, но для вставки и удаления первый требует O (log n) вращений, в то время как последний принимает только O (1) вращения.

Поскольку вращения означают запись в память, а запись в память дорого, RedBlackTrees на практике быстрее обновляется, чем AvlTrees

Ответ 8

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

Ответ 9

Чтобы получить представление о том, как работает дерево AVL, this > интерактивная визуализация помогает.

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

Обе реализации масштабируются как O(lg N), где N - количество листьев, но на практике дерево AVL быстрее работает с интенсивными задачами поиска: используя преимущества лучшей балансировки, обходы дерева в среднем короче. С другой стороны, вставка и удаление мудрый, дерево AVL медленнее: требуется большее число оборотов для правильной коррекции структуры данных при модификации.

Для реализаций общего назначения (то есть a-priori неясно, являются ли поиски преобладающими для операций), RedBlack Trees являются предпочтительными: их проще реализовать и быстрее в обычных случаях - везде, где структура данных изменяется как часто в поиске. Например, TreeMap и TreeSet в Java используют фоновое дерево RedBlack.