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

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

76 голосов | спросил Bob John 28 AMpSun, 28 Apr 2013 03:02:13 +040002Sunday 2013, 03:02:13

9 ответов


0

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

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

ответил Fred Foo 24 J000000Wednesday13 2013, 03:32:40
0

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

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

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

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

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

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

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

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

ответил DU Jiaen 4 MaramWed, 04 Mar 2015 07:11:00 +03002015-03-04T07:11:00+03:0007 2015, 07:11:00
0

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

  

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

     

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

ответил taocp 28 AMpSun, 28 Apr 2013 03:06:47 +040006Sunday 2013, 03:06:47
0
  

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

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

ответил user3078685 8 SunEurope/Moscow2013-12-08T02:33:42+04:00Europe/Moscow12bEurope/MoscowSun, 08 Dec 2013 02:33:42 +0400 2013, 02:33:42
0

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

ответил zhpmatrix 15 J0000006Europe/Moscow 2014, 08:00:14
0

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

ответил Jimmy Venema 8 Jpm1000000pmFri, 08 Jan 2016 18:25:20 +030016 2016, 18:25:20
0

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

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

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

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

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

ответил Leon 24 J000000Wednesday13 2013, 02:56:53
0

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

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

ответил beanmoon 11 Maypm15 2015, 20:18:51
0

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

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

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

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

ответил Paolo Maresca 17 ThuEurope/Moscow2015-12-17T17:58:54+03:00Europe/Moscow12bEurope/MoscowThu, 17 Dec 2015 17:58:54 +0300 2015, 17:58:54

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132