My<cod/>.net
Лучшая самобалансировка BST для быстрого ввода большого количества узлов
Я смог найти подробности о нескольких самобалансирующихся BST через несколько источников, но я не нашел хороших описаний, детализирующих, какой из них лучше всего использовать в разных ситуациях (или если это действительно не имеет значения).
Я хочу BST , который является оптимальным для хранения более десяти миллионов узлов. Порядок вставки узлов в основном случайный, и мне никогда не нужно будет удалять узлы, поэтому время вставки-это единственное, что нужно будет оптимизировать.
Я намерен использовать его для хранения ранее посещенных игровых состояний в игре-головоломке, чтобы я мог быстро проверить, была ли уже обнаружена предыдущая конфигурация.
Красно-черный лучше, чем AVL для вставки тяжелых приложений. Если вы предвидите относительно равномерный взгляд вверх,то красно-черный-это путь. Если вы предвидите относительно несбалансированный поиск, где более недавно просмотренные элементы с большей вероятностью будут просмотрены снова ,вы хотите использовать деревья splay.
Зачем вообще использовать BST ? Из вашего описания словарь будет работать так же хорошо, если не лучше.
Единственная причина для использования BST была бы, если бы вы хотели перечислить содержимое контейнера в ключевом порядке. Это, конечно, не похоже на то, что вы хотите это сделать, и в этом случае перейдите к таблице hash. O(1) вставка и поиск, не беспокойтесь об удалении, что может быть лучше?
Два самобалансирующихся BST s, с которыми я больше всего знаком, - это red-black и AVL, поэтому я не могу точно сказать, лучше ли какие-либо другие решения, но, насколько я помню, red-black имеет более быструю вставку и более медленный поиск по сравнению с AVL .
Поэтому, если вставка имеет более высокий приоритет, чем извлечение, красный-черный может быть лучшим решением.