Как программист, когда следует рассмотреть использование дерева RB, дерева B или дерева AVL? Каковы ключевые моменты, которые необходимо учитывать, прежде чем принимать решение о выборе?
Может кто-нибудь объяснить сценарий для каждой древовидной структуры, почему он выбирается над другими со ссылкой на ключевые моменты?
Возьмите это с щепоткой соли:
B-tree, когда вы управляете более чем тысячами элементов, и вы выгружаете их с диска или на какой-то медленный носитель.
Дерево RB, когда вы делаете довольно частые вставки, удаления и поиска на дереве.
Дерево AVL, когда ваши вставки и удаления нечасты относительно ваших поисков.
Я думаю, что деревья B + - хорошая структура данных упорядоченного контейнера общего назначения, даже в основной памяти. Даже когда виртуальная память не является проблемой, часто возникает необходимость в кэшировании, а деревья B + особенно хороши для последовательного доступа - та же асимптотическая производительность, что и связанный список, но с удобством кеширования, близким к простому массиву. Все это и O (log n) искать, вставлять и удалять.
В деревьях B + есть проблемы - например, элементы, перемещающиеся внутри узлов, когда вы вставляете/удаляете, недействительные указатели на эти элементы. У меня есть библиотека контейнеров, которая выполняет "обслуживание курсора" - курсоры присоединяются к листу node, которые они в настоящее время ссылаются в связанном списке, поэтому они могут быть исправлены или аннулированы автоматически. Поскольку редко бывает более одного или двух курсоров, он работает хорошо - но это лишний бит работы все равно.
Другое дело, что дерево B + по сути является именно этим. Я предполагаю, что вы можете отключить или воссоздать не-листовые узлы в зависимости от того, нужны они вам или нет, но с бинарными узлами дерева вы получаете гораздо большую гибкость. Двоичное дерево может быть преобразовано в связанный список и обратно без копирования узлов - вы просто изменяете указатели, а затем помните, что теперь рассматриваете его как другую структуру данных. Помимо всего прочего, это означает, что вы легко получаете O (n) слияние деревьев - конвертируете оба дерева в списки, объединяете их, а затем конвертируете обратно в дерево.
Еще одна вещь - выделение и освобождение памяти. В двоичном дереве это можно отделить от алгоритмов - пользователь может создать node, затем вызвать алгоритм вставки, а удалять можно извлечь узлы (отсоединить их от дерева, но не освобождать память). В B-дереве или B + -tree это, очевидно, не работает - данные будут жить в многопозиционном элементе node. Написание методов вставки, которые "планируют" операцию без изменения узлов, пока они не узнают, сколько новых узлов необходимо и что они могут быть выделены, является проблемой.
Красный черный против AVL? Я не уверен, что это имеет большое значение. В моей собственной библиотеке есть класс "инструмент", основанный на политике, для управления узлами, с методами для двусвязных списков, простых бинарных деревьев, деревьев разметки, красно-черных деревьев и скинов, включая различные преобразования. Некоторые из этих методов были реализованы только потому, что мне было скучно в тот или иной момент. Я не уверен, что даже проверял методы treap. Причина, по которой я выбрал красно-черные деревья, а не AVL, состоит в том, что я лично лучше понимаю алгоритмы - это не значит, что они проще, это просто случайность истории, с которой я знаком с ними.
Последнее: я только изначально разработал свои контейнеры дерева B + в качестве эксперимента. Это один из тех экспериментов, которые никогда не заканчивались на самом деле, но это не то, что я бы побудил других повторить. Если все, что вам нужно, это упорядоченный контейнер, лучшим ответом является использование той, которую предоставляет ваша существующая библиотека. std:: map и т.д. на С++. Моя библиотека развивалась в течение многих лет, и потребовалось довольно много времени, чтобы получить ее стабильную, и я недавно сравнительно недавно обнаружил ее технически не переносной (в зависимости от бит W90T).
В памяти B-Tree имеет то преимущество, когда количество элементов больше 32000... Посмотрите speedtest.pdf из stx-btree.
При выборе структур данных вы торгуете такими факторами, как
Я бы начал с чтения статей в Википедии, на которые ссылался Роберт Харви.
Прагматически, при работе на таких языках, как Java, средний программист имеет тенденцию использовать предоставленные классы коллекции. Если в процессе настройки производительности обнаруживается, что производительность коллекции является проблематичной, можно искать альтернативные реализации. Редко это первое, что нужно учитывать при разработке бизнеса. Чрезвычайно редко, что нужно реализовать такие структуры данных вручную, обычно используются библиотеки, которые можно использовать.