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

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

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

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

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

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

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

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

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

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

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

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