Использование, плюсы и минусы для бинарного дерева поиска, 2-3 дерева и B-дерева

Question

Я просматривал материалы из своего класса структуры данных, и я немного запутался с использованием этих трех видов деревьев. так в каких ситуациях нам лучше использовать двоичное дерево поиска, 2-3 дерева и B-дерево соответственно? а какие плюсы и минусы?

Спасибо вам большое! я довольно новичок в вещах структуры данных...

Answer 1

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

Деревья двоичного поиска и 2-3 дерева отличаются от B-деревьев тем, что BST и 2-3 дерева (обычно) являются структурами данных основной памяти, а B-деревья (обычно) являются структурами данных внешней памяти. В частности, B-деревья предназначены для хранения на дисках, на которых стоимость чтения или записи страницы диска значительно выше, чем стоимость выполнения простых вычислений. Если вы планируете хранить огромный объем данных, которые не помещаются в основную память, B-деревья являются отличным выбором для структуры данных. С другой стороны, в основной памяти B-деревья с очень большим коэффициентом ветвления будут медленнее, чем BST или 2-3 дерева, потому что каждая вставка или удаление B-дерева может потребовать большого количества переназначений указателей. Для наборов данных, которые вписываются в основную память, 2-3 дерева и BST обычно являются лучшим выбором (хотя было проведено некоторое исследование, показывающее, что B-деревья низкого порядка могут превосходить BST в основной памяти из-за эффектов кэширования.)

Что касается BST и 2-3 деревьев: "дерево двоичного поиска" не является единой структурой данных. Существуют чистые BST без балансировки, красные / черные деревья, деревья AVL, деревья AA, деревья сплайнов, трепы, деревья козла отпущения, деревья с балансировкой веса, деревья RAVL и т. Д. Каждая из этих структур данных пытается сбалансировать BST, используя некоторые правила так что поиск, вставка и удаление выполняются быстро. Дерево 2-3 - это разновидность BST, которая позволяет использовать несколько ключей на узел, чтобы предоставить простые правила для поддержания баланса. Вопрос, как правило, не в том, "когда BST лучше, чем дерево 2-3 или наоборот", а в том, "какие преимущества имеет дерево 2-3 по сравнению с другими сбалансированными BST и наоборот", и это нечто что вы должны выяснить через профилирование.

Надеюсь это поможет!