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

Question

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

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

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

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

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

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

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

Answer 4

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

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