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

Question

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

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

1

data-structures splay-tree 2-3-4-tree

Источник

user479988 16 дек '10 в 02:34

1 ответ

Решение

Другие вопросы по тегам data-structures splay-tree 2-3-4-tree

user501217 16 дек '10 в 03:58 2010-12-16 03:58 · Accepted Answer · 2010-12-16 03:58

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

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

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