AVL и красно-черные деревья являются самобалансирующимися, за исключением красного и черного цветов в узлах. Какова основная причина выбора красно-черных деревьев вместо деревьев AVL? Каковы применения красно-черных деревьев?
algorithm
data-structures
red-black-tree
уверенный
источник
источник
Ответы:
И красно-черные деревья, и деревья AVL являются наиболее часто используемыми сбалансированными деревьями двоичного поиска, и они гарантированно поддерживают вставку, удаление и поиск
O(logN) time. Однако есть следующие точки сравнения между ними:O(N)дополнительного места. Однако, если мы знаем, что ключи, которые будут вставлены в дерево, всегда будут больше нуля, мы можем использовать знаковый бит ключей для хранения информации о цвете красно-черного дерева. Таким образом, в таких случаях красно-черное дерево не занимает лишнего места.Красно-черные деревья более общего назначения. Они относительно хорошо справляются с добавлением, удалением и поиском, но деревья AVL имеют более быстрый поиск за счет более медленного добавления / удаления. Красно-черное дерево используется в следующем:
java.util.TreeMap,java.util.TreeSetисточник
In general, the rotations for an AVL tree are harder to implement and debug than that for a Red-Black tree.это не правда.std:: mapи друзья используют какую-либо конкретную структуру. Это осталось на усмотрение реализации, хотя libstdc ++ и Dinkumware по крайней мере используют красно-черные деревья, и на практике кажется, что вы правы.Попробуйте прочитать эту статью
Он предлагает хорошее представление о различиях, сходствах, производительности и т. Д.
Вот цитата из статьи:
Насколько я понимаю, деревья AVL и деревья RB не так уж далеки с точки зрения производительности. Дерево RB - это просто вариант B-дерева, и балансировка реализована иначе, чем дерево AVL.
источник
Наше понимание различий в производительности улучшилось с годами, и теперь основной причиной использования красно-черных деревьев вместо AVL будет отсутствие доступа к хорошей реализации AVL, поскольку они немного менее распространены, возможно, потому, что они не охвачены в CLRS.
Оба дерева теперь считаются формами деревьев со сбалансированным рангом, но красно-черные деревья стабильно медленнее примерно на 20% в реальных тестах . Или даже на 30-40% медленнее при вставке последовательных данных .
Поэтому люди, которые изучали красно-черные деревья, но не АВЛ-деревья, склонны выбирать красно-черные деревья. Основное использование красно-черных деревьев подробно описано в статье о них в Википедии .
источник
Другие ответы здесь хорошо суммируют плюсы и минусы деревьев RB и AVL, но я нашел эту разницу особенно интересной:
Источник: Mehlhorn & Sanders (2008) (раздел 7.4).
Таким образом, хотя деревья RB и AVL гарантируют наихудшее время O (log (N)) для поиска, вставки и удаления, восстановление свойства AVL / RB после вставки или удаления узла может быть выполнено за O (1) амортизированное время для красно-черные деревья.
источник
Программисты обычно не любят динамически выделять память. Проблема с деревом avl заключается в том, что для "n" элементов вам нужно как минимум log2 (log2 (n)) ... (height-> log2 (n)) бит для хранения высоты дерева! Поэтому, когда вы обрабатываете огромные данные, вы не можете быть уверены в том, сколько бит нужно выделить для хранения высоты в каждом узле.
Например, если вы используете 4 байта int (32 бита) для хранения высоты. Максимальная высота может быть: 2 ^ 32 и, следовательно, максимальное количество элементов, которые вы можете сохранить в дереве, составляет 2 ^ (2 ^ 32) - (кажется, очень большим, но в этом возрасте данных, я думаю, ничего не слишком велико). И, следовательно, если вы превысите этот предел, вам придется динамически выделять больше места для хранения высоты.
Это ответ, предложенный профессором моего университета, который мне показался разумным! Надеюсь, я понимаю.
Изменения: деревья AVL более сбалансированы по сравнению с красно-черными деревьями, но они могут вызывать большее вращение во время вставки и удаления. Поэтому, если ваше приложение включает в себя много частых вставок и удалений, предпочтительнее использовать деревья Red Black. И если вставки и удаления происходят реже, а поиск - более частая операция, то дерево AVL должно быть предпочтительнее красного черного дерева. --Источник GEEKSFORGEEKS.ORG
источник
you need need atleast log2(log2(n))...(height->log2(n)) bits to store the height of [an AVL] treeМне не нужна высота какого-либо узла в AVL-дереве для его реализации. Вам нужен один бит дополнительной информации для каждого узла ( Я САМЫЙ ВЕЛИКИЙ (брат с самым высоким поддеревом))); это более удобно, а также обычные иметь два дополнительных бита (ребенок выше для левой и правой), как представлено на AV & L.Повторная балансировка дерева AVL должна соответствовать следующему свойству. (Ссылка вики - AVL Tree )
Таким образом, это означает, что общая высота дерева AVL не может сходить с ума, т.е. поиск будет лучше с деревьями AVL. И так как дополнительные операции (вращения) должны выполняться, чтобы не упустить высоту, операции модификации дерева могут быть немного дорогостоящими.
источник