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

голоса
8

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

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

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

Задан 05/08/2008 в 16:40
источник пользователем
На других языках...                            


4 ответов

голоса
3

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

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

Ответил 29/08/2008 d 01:10
источник пользователем

голоса
3

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

Ответил 05/08/2008 d 16:59
источник пользователем

голоса
0

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

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

Ответил 05/08/2008 d 16:50
источник пользователем

голоса
-2

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

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

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

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

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

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

Ответил 01/02/2009 d 13:49
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more