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

Может кто-нибудь объяснить, в чем основные различия между этими двумя структурами данных? Я пытался найти в Интернете источник, который подчеркивал бы различия / сходства, но не нашел ничего слишком информативного. В каких случаях одно предпочтительнее другого? Какие практические ситуации делают использование одного «лучше» другого?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Из статьи в Википедии о деревьях AVL

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

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

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

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

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

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

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

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

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

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

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

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

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