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

Question

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

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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

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