Когда выбрать дерево RB, B-дерево или дерево AVL?

Как программисту, когда мне следует рассмотреть возможность использования дерева RB, B-дерева или дерева AVL? Какие ключевые моменты необходимо учесть, прежде чем определиться с выбором?

Может ли кто-нибудь объяснить со сценарием для каждой древовидной структуры, почему она выбрана по сравнению с другими со ссылкой на ключевые моменты?

Возьмите это со щепоткой соли:

B-дерево, когда вы управляете более чем тысячами элементов и выгружаете их с диска или какого-либо медленного носителя.

Дерево RB, когда вы делаете довольно частые вставки, удаления и извлечения в дереве.

Дерево AVL, когда ваши вставки и удаления нечасты по сравнению с вашими поисками.

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

Однако у деревьев B + действительно есть проблемы - например, элементы, перемещающиеся внутри узлов, когда вы выполняете вставку / удаление, аннулируя указатели на эти элементы. У меня есть контейнерная библиотека, которая выполняет «обслуживание курсора» - курсоры присоединяются к конечному узлу, на который они в настоящее время ссылаются в связанном списке, поэтому их можно исправить или сделать недействительными автоматически. Так как курсоров редко бывает больше, чем один или два, он работает хорошо, но, тем не менее, это дополнительная работа.

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

Еще одна вещь - это выделение и освобождение памяти. В двоичном дереве это может быть отделено от алгоритмов - пользователь может создать узел, затем вызвать алгоритм вставки, а удаление может извлекать узлы (отсоединять их от дерева, но не освобождать память). В B-дереве или B + -дереве это явно не работает - данные будут жить в многопозиционном узле. Создание методов вставки, которые «планируют» операцию без изменения узлов, пока они не узнают, сколько новых узлов необходимо и что они могут быть выделены, является сложной задачей.

Красный черный против AVL? Я не уверен, что это имеет большое значение. В моей собственной библиотеке есть класс «инструмента» на основе политик для управления узлами с методами для двусвязных списков, простых двоичных деревьев, растянутых деревьев, красно-черных деревьев и переходов, включая различные преобразования. Некоторые из этих методов были реализованы только потому, что мне время от времени было скучно. Я не уверен, что даже тестировал методы treap. Причина, по которой я выбрал красно-черные деревья, а не AVL, заключается в том, что я лично лучше понимаю алгоритмы - что не означает, что они проще, это просто случайность истории, что я лучше знаком с ними.

И последнее - я изначально разрабатывал контейнеры B + tree только в качестве эксперимента. Это один из тех экспериментов, которые на самом деле так и не закончились, но я бы не побуждал других повторять его. Если все, что вам нужно, это упорядоченный контейнер, лучший ответ - использовать тот, который предоставляет ваша существующая библиотека, например std :: map и т. Д. В C ++. Моя библиотека развивалась годами, потребовалось довольно много времени, чтобы она стала стабильной, и я только относительно недавно обнаружил, что она технически непереносима (зависит от некоторого неопределенного поведения WRT offsetof).

В памяти B-Tree имеет преимущество, когда количество элементов больше 32000 ... Посмотрите speedtest.pdf из stx-btree .

При выборе структур данных вы жертвуете такими факторами, как

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

Я бы начал с чтения статей в Википедии, на которые ссылается Роберт Харви.

С практической точки зрения, при работе с такими языками, как Java, средний программист стремится использовать предоставленные классы коллекций. Если в процессе настройки производительности обнаруживается, что производительность сбора данных проблематична, можно искать альтернативные реализации. Это редко первое, что нужно учитывать при разработке под руководством бизнеса. Реализовать такие структуры данных вручную крайне редко, обычно есть библиотеки, которые можно использовать.