Использование дерева 2-3-4 вместо дерева сплайнов

Question

Я сейчас на курсе по структурам данных, и мы узнали о 2-3-4 деревьях и splay-деревьях. Мне было интересно, при каких обстоятельствах вы бы использовали дерево 2-3-4 вместо дерева? Они оба уравновешены и отсортированы, поэтому я не вижу особой разницы между ними.

Answer 1

A 2-3-4 дерево изменяет структуру только при вставках и удалениях, в то время как splay-tree также реорганизует узлы при поиске.

Сплайновые деревья, благодаря реорганизации при поиске, обеспечат более быстрые ответы, если ваш типичный шаблон использования в большинстве случаев ищет небольшой набор элементов.

Возможно реализовать 2-3-4 дерева, так что наименьший элемент можно найти в O (1), но, как правило, предлагают и вставку, и удаление при амортизированном O (log n).