Мне удалось найти детали по нескольким самобалансирующимся BSTэлементам через несколько источников, но я не нашел ни одного хорошего описания, детализирующего, какой из них лучше всего использовать в различных ситуациях (или, если это действительно не имеет значения).
Я хочу, BSTчтобы это было оптимальным для хранения свыше десяти миллионов узлов. Порядок вставки узлов в основном случайный, и мне никогда не понадобится удалять узлы, поэтому единственное, что нужно оптимизировать, - это время вставки.
Я намерен использовать его для хранения ранее посещенных состояний игры в игре-головоломке, чтобы я мог быстро проверить, встречалась ли предыдущая конфигурация.
Красно-черный лучше, чем AVL для приложений с интенсивным вводом. Если вы предвидите относительно равномерный поиск, тогда красно-черный - это то, что вам нужно. Если вы предвидите относительно несбалансированный поиск, в котором более недавно просмотренные элементы с большей вероятностью будут снова просмотрены, вы захотите использовать Splay Tree .
Два самобалансируемых BSTэлемента, с которыми я больше всего знаком, - это красно-черный и AVL, поэтому я не могу с уверенностью сказать, являются ли какие-либо другие решения лучше, но, насколько я помню, красно-черный имеет более быструю вставку и более медленный поиск по сравнению с AVL.
Поэтому, если вставка имеет более высокий приоритет, чем извлечение, красно-черный может быть лучшим решением.
Зачем BSTвообще использовать? Из вашего описания словарь будет работать так же хорошо, если не лучше.
Единственная причина для использования была BSTбы, если вы хотите перечислить содержимое контейнера в ключевом порядке. Это, конечно, не звучит так, как будто вы хотите это сделать, и в этом случае перейдите к хеш-таблице. O(1)вставка и поиск, не беспокойтесь об удалении, что может быть лучше?
[Хеш-таблицы имеют] O (1) вставка и поиск
Я думаю, что это неправильно.
Прежде всего, если вы ограничите пространство клавиш до конечного, вы можете сохранить элементы в массиве и выполнить O (1) линейное сканирование. Или вы можете перемешать массив и затем выполнить линейное сканирование за O (1) ожидаемое время. Когда вещи конечны, вещи легко O (1).
Допустим, ваша хеш-таблица будет хранить любую произвольную строку битов; это не имеет большого значения, пока существует бесконечный набор ключей, каждый из которых конечен. Затем вы должны прочитать все биты любого запроса и ввода, иначе я вставлю y0 в пустой хеш и запрос на y1, где y0 и y1 отличаются в одной позиции бита, на которую вы не смотрите.
Но скажем, длина ключа не является параметром. Если ваша вставка и поиск занимают O (1), в частности, хеширование занимает O (1) времени, а это означает, что вы смотрите только конечное количество выходных данных из хэш-функции (из которых, вероятно, будет только конечный выход, предоставленный ).
Это означает, что с конечным числом сегментов должен существовать бесконечный набор строк, которые имеют одинаковое значение хеш-функции. Предположим, я вставил много, т. Е. Ω (1), и начал запрашивать. Это означает, что ваша хеш-таблица должна использовать другой механизм вставки / поиска O (1) для ответа на мои запросы. Какой, и почему бы просто не использовать это напрямую?