Какие решения следует учитывать при выборе типа самобалансирующейся БСТ?
Например, я знаю концепцию и идеи 2-3 дерева и красно-черного дерева, но не могли бы вы дать мне несколько ситуаций, когда одно из них лучше другого? Какие вопросы я должен задать себе?
Поскольку речь идет не только о 2-3 дереве и красно-черном дереве, не стесняйтесь приводить примеры и из других самоуравновешенных деревьев, я собираюсь изучить их. Просто хотел задать вопрос с общей точки зрения, чтобы облегчить поиск в Google тем, кто задается подобным или тем же вопросом.
1 ответ
Основное внимание уделяется количеству вставок / стираний по сравнению с количеством поисков. И обычно выбор сводится либо к красно-черному, либо к АВЛ.
AVL поддерживает гораздо более строгий баланс за счет более сложных операций с балансом. AVL также требует немного больше информации для каждого узла, но как RB, так и AVL обычно могут быть реализованы так, чтобы необходимая информация была скрыта в уже существующих членах (то есть в младших битах буферов, выделенных по выровненным адресам).
И обратите внимание, если ваше дерево не будет огромным, вероятно, не имеет значения, какое дерево вы выберете (или даже дерево, список или даже массив, вероятно, подойдут, если у вас есть только дюжина элементов). И если ваше дерево не будет насчитывать десятки тысяч, даже очень грубый баланс, скорее всего, будет "достаточно хорошим".
Если вы собираетесь перейти к работе с деревом с несколькими значениями в каком-то более крупном узле (как в дереве 2-3, вероятно, имеет смысл перейти к полному b-дереву и использовать гораздо большие коэффициенты. Я только когда-либо встречал 2-3 и 2-3-4 дерева во время обучения на пути к более полезным постройкам.