Какие решения следует учитывать при выборе типа самоуравновешенного БСТ?

Question

Например, я знаю концепцию и идеи 2-3 дерева и красно-черного дерева, но не могли бы вы дать мне несколько ситуаций, когда одно из них лучше, чем другое? Какие вопросы я должен задать себе?

Поскольку речь идет не только о 2-3 дереве и красно-черном дереве, не стесняйтесь приводить примеры и с других самоуравновешенных деревьев, я собираюсь смотреть на них. Просто хотел задать вопрос с общей точки зрения, чтобы облегчить поиск в Google тем, кто задается подобным или тем же вопросом.

Answer 1

Основное внимание уделяется количеству вставок / стираний по сравнению с количеством поисков. И обычно выбор сводится к красно-черному или AVL.

AVL поддерживает гораздо более строгий баланс за счет более сложных операций с балансом. AVL также требует немного больше информации на узел, но как RB, так и AVL обычно могут быть реализованы так, чтобы необходимая информация была скрыта в уже существующих членах (то есть в младших битах буферов, выделенных по выровненным адресам).

И обратите внимание, если ваше дерево не будет огромным, вероятно, не имеет значения, какое дерево вы выберете (или даже дерево вообще, список или даже массив, вероятно, подойдут, если у вас есть только дюжина элементов). И если ваше дерево не будет состоять из десятков тысяч, даже очень грубый баланс, вероятно, будет «достаточно хорошим».

Если вы собираетесь go работать с деревом с несколькими значениями в некоторых узел большего размера (например, в 2-3 дереве, вероятно, имеет смысл использовать go для полного b-дерева и использовать гораздо более крупные коэффициенты. Я когда-либо встречал только 2-3 и 2-3-4 дерева во время обучения путь к более полезным строениям.