Лучший самобалансирующийся BST для быстрой вставки большого количества узлов

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

Я хочу, BSTчтобы это было оптимальным для хранения свыше десяти миллионов узлов. Порядок вставки узлов в основном случайный, и мне никогда не понадобится удалять узлы, поэтому единственное, что нужно оптимизировать, - это время вставки.

Я намерен использовать его для хранения ранее посещенных состояний игры в игре-головоломке, чтобы я мог быстро проверить, встречалась ли предыдущая конфигурация.

5.08.2008 15:40:24
4 ОТВЕТА
РЕШЕНИЕ

Красно-черный лучше, чем AVL для приложений с интенсивным вводом. Если вы предвидите относительно равномерный поиск, тогда красно-черный - это то, что вам нужно. Если вы предвидите относительно несбалансированный поиск, в котором более недавно просмотренные элементы с большей вероятностью будут снова просмотрены, вы захотите использовать Splay Tree .

4
7.02.2013 17:28:39

Два самобалансируемых BSTэлемента, с которыми я больше всего знаком, - это красно-черный и AVL, поэтому я не могу с уверенностью сказать, являются ли какие-либо другие решения лучше, но, насколько я помню, красно-черный имеет более быструю вставку и более медленный поиск по сравнению с AVL.

Поэтому, если вставка имеет более высокий приоритет, чем извлечение, красно-черный может быть лучшим решением.

0
7.02.2013 14:40:26

Зачем BSTвообще использовать? Из вашего описания словарь будет работать так же хорошо, если не лучше.

Единственная причина для использования была BSTбы, если вы хотите перечислить содержимое контейнера в ключевом порядке. Это, конечно, не звучит так, как будто вы хотите это сделать, и в этом случае перейдите к хеш-таблице. O(1)вставка и поиск, не беспокойтесь об удалении, что может быть лучше?

3
7.02.2013 14:40:03

[Хеш-таблицы имеют] O (1) вставка и поиск

Я думаю, что это неправильно.

Прежде всего, если вы ограничите пространство клавиш до конечного, вы можете сохранить элементы в массиве и выполнить O (1) линейное сканирование. Или вы можете перемешать массив и затем выполнить линейное сканирование за O (1) ожидаемое время. Когда вещи конечны, вещи легко O (1).

Допустим, ваша хеш-таблица будет хранить любую произвольную строку битов; это не имеет большого значения, пока существует бесконечный набор ключей, каждый из которых конечен. Затем вы должны прочитать все биты любого запроса и ввода, иначе я вставлю y0 в пустой хеш и запрос на y1, где y0 и y1 отличаются в одной позиции бита, на которую вы не смотрите.

Но скажем, длина ключа не является параметром. Если ваша вставка и поиск занимают O (1), в частности, хеширование занимает O (1) времени, а это означает, что вы смотрите только конечное количество выходных данных из хэш-функции (из которых, вероятно, будет только конечный выход, предоставленный ).

Это означает, что с конечным числом сегментов должен существовать бесконечный набор строк, которые имеют одинаковое значение хеш-функции. Предположим, я вставил много, т. Е. Ω (1), и начал запрашивать. Это означает, что ваша хеш-таблица должна использовать другой механизм вставки / поиска O (1) для ответа на мои запросы. Какой, и почему бы просто не использовать это напрямую?

-2
8.02.2013 18:25:09
Это общепринятая мудрость. В лучшем случае, O (1), очевидно, реализации будут отличаться. Существует также множество различных алгоритмов хэш-таблиц.
ApplePieIsGood 22.04.2009 23:22:47
«Это общепринятая мудрость». - Я слышал это много раз, но я до сих пор не видел доказательств. Я думаю, что было бы неплохо бросить вызов этой части фольклора, если вы хотите получить теоретический результат «это O (1)», или измерить различные структуры поиска, если вы хотите «быстро на практике». «Наилучший случай, O (1)» - несбалансированные деревья поиска также имеют это, но никто не утверждает, что у них есть «O (1) вставка и поиск».
Jonas Kölker 4.05.2009 07:38:26
В лучшем случае несбалансированное дерево поиска будет одним узлом из сбалансированного. Наилучший случай вставки / поиска по-прежнему log (n)
µBio 20.11.2009 00:55:51
В лучшем случае пользователь ищет значение, хранящееся в корневом узле, что занимает O (1) время для доступа ...
Jonas Kölker 21.11.2009 04:51:52
@MeNoMore Джонас правильно использовал формат цитаты для первой строки своего ответа, потому что это была цитата кого-то другого. Не вносите такие изменения в будущем.
Andrew Barber 7.02.2013 17:27:58