Почему красно-черные деревья так популярны?

Кажется, что везде, где я смотрю, структуры данных реализуются с использованием красно-черных деревьев ( std::setв C ++, SortedDictionaryв C # и т. Д.)

Только что покрыв (a, b), красно-черные и AVL деревья в своем классе алгоритмов, вот что я получил (также из бесед с профессорами, просмотра нескольких книг и поиска в Google):

• Деревья AVL имеют меньшую среднюю глубину, чем красно-черные деревья, и, следовательно, поиск значения в дереве AVL всегда происходит быстрее.
• Красно-черные деревья вносят меньше структурных изменений в баланс, чем деревья AVL, что может сделать их потенциально более быстрыми для вставки / удаления. Я говорю потенциально, потому что это будет зависеть от стоимости структурных изменений в дереве, так как это будет сильно зависеть от времени выполнения и реализации (может также быть совершенно другим в функциональном языке, когда дерево неизменяемое?)

В Интернете есть много тестов, которые сравнивают AVL и красно-черные деревья, но что меня поразило, так это то, что мой профессор в основном сказал, что обычно вы делаете одну из двух вещей:

• Либо вас не очень заботит производительность, и в этом случае разница между AVL и красно-черным в 10-20% в большинстве случаев не будет иметь никакого значения.
• Или вы действительно заботитесь о производительности, в этом случае вы отказываетесь от AVL и красно-черных деревьев и переходите на B-деревья, которые можно настроить, чтобы они работали намного лучше (или (a, b) -деревьями, я Я собираюсь положить все это в одну корзину.)

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

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

При этом существует ли конкретная причина, по которой красно-чёрные деревья используются повсеместно, когда B-деревья должны превосходить их, основываясь на том, что сказано выше? (в качестве единственного эталонного теста, который я смог найти, также показано http://lh3lh3.users.sourceforge.net/udb.shtml , но это может быть просто вопросом конкретной реализации). Или причина, по которой все используют красно-черные деревья, потому что их довольно легко реализовать, или, говоря другими словами, сложно реализовать плохо?

Кроме того, как это меняется, когда вы переходите в область функциональных языков? Похоже, что и Clojure, и Scala используют попытки сопоставления массивов Hash , где Clojure использует коэффициент ветвления 32.

Цитата из ответа на вопрос « Обходы от корня деревьев AVL и Red Black Trees »

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

Таким образом, вставка дерева RedBlack может быть реализована без рекурсии, на некоторых процессорах рекурсия обходится очень дорого, если вы переполняете кэш вызова функции (например, SPARC из-за использования окна Register )

(Я видел, как программное обеспечение выполнялось в Sparc в 10 раз быстрее, удаляя один вызов функции, что приводило к тому, что часто вызываемый путь кода был слишком глубоким для окна регистра. Поскольку вы не знаете, насколько глубоко будет окно регистра система вашего клиента, и вы не знаете, как далеко внизу стека вызовов вы находитесь в «горячем пути кода», не используя рекурсию, что делает ее более предсказуемой.)

Также не рискует выбежать из стека.

Я также недавно исследовал эту тему, так что вот мои выводы, но имейте в виду, что я не эксперт в структурах данных!

В некоторых случаях вы вообще не можете использовать B-деревья.

Один известный случай std::mapиз C ++ STL. Стандарт требует, чтобы insertне делать недействительными существующие итераторы

Никакие итераторы или ссылки не являются недействительными.

http://en.cppreference.com/w/cpp/container/map/insert

Это исключает B-дерево как реализацию, потому что вставка будет перемещаться вокруг существующих элементов.

Другим аналогичным случаем использования являются навязчивые структуры данных. То есть вместо того, чтобы хранить ваши данные внутри узла дерева, вы храните указатели на детей / родителей внутри вашей структуры:

// non intrusive
struct Node<T> {
    T value;
    Node<T> *left;
    Node<T> *right;
};
using WalrusList = Node<Walrus>;

// intrusive
struct Walrus {
    // Tree part
    Walrus *left;
    Walrus *right;

    // Object part
    int age;
    Food[4] stomach;
};

Вы просто не можете сделать B-дерево навязчивым, потому что оно не является структурой данных только по указателю.

Навязчивые красно-черные деревья используются, например, в jemalloc для управления свободными блоками памяти. Это также популярная структура данных в ядре Linux.

Я также считаю, что реализация «однопроходной хвостовой рекурсии» не является причиной популярности красного черного дерева как изменяемой структуры данных.

$\log{n}$

$O(1)$

$O(1)$

Вариант, описанный в opendatastructures, использует родительские указатели, рекурсивный нисходящий проход для вставки и итеративный цикл вверх для исправлений. Рекурсивные вызовы находятся в хвостовых позициях, и компиляторы оптимизируют это до цикла (я проверял это в Rust).

$O(1)$

Ну, это не авторитетный ответ, но всякий раз, когда мне приходится кодировать сбалансированное двоичное дерево поиска, это красно-черное дерево. Есть несколько причин для этого:

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

2) Они требуют только 1 бит дополнительной информации на узел, и вы часто можете найти способ получить это бесплатно.

3) Мне не нужно делать это очень часто, поэтому каждый раз, когда я делаю это, я должен понять, как сделать это снова и снова. Простые правила и соответствие с 2-4 деревьями делают его кажущимся простым каждый раз , хотя код оказывается сложным каждый раз . Я все еще надеюсь, что когда-нибудь код окажется простым.

4) То, как красно-черное дерево разделяет соответствующий узел дерева 2-4 и вставляет средний ключ в родительский узел 2-4, просто перекрашивая, является очень элегантным. Я просто люблю это делать.

Красно-черные или AVL-деревья имеют преимущество перед B-деревьями и т. П., Когда ключ длинный или по какой-то другой причине перемещение ключа обходится дорого.

Я создал свою собственную альтернативу std::setкрупному проекту по ряду причин производительности. По соображениям производительности я выбрал AVL вместо красно-черного (но это небольшое повышение производительности не оправдывало замену собственного вместо std :: set). «Ключ», являющийся сложным и трудным для перемещения, был существенным фактором. Имеют ли смысл деревья (a, b), если вам нужен еще один уровень косвенности перед клавишами? AVL и красно-черные деревья могут быть реструктурированы без перемещения клавиш, поэтому они имеют то преимущество, когда ключи дороги в перемещении.