Хранить миллион ключей миллионной длины, которые лучше будут красное черное дерево или корень дерева?

Question

Я хочу хранить несколько ключей (String) длиной в миллион с привязанными к ним объектами. Так что мне приходится очень часто вставлять данные в структуру данных (дерево rbtree или radix), и приходится искать довольно мало времени по сравнению со вставкой. Любые рекомендации будут оценены. Спасибо.

Answer 1

Поскольку вставка является вашей основной задачей, вам следует использовать красно-черное дерево, поскольку его сложность по времени вставки логарифмически зависит от размера ввода, то есть O(k*log n) с log, являющимся логарифмом основания 2, k являетсяразмер или длина каждого входа, а n - количество входов. Вставка радиального дерева линейна по размеру k каждого входа и по количеству n входов, то есть O(k*n), что хуже, чем для красно-черных деревьев, если только много изстроковые ключи имеют достаточно длинных префиксов для преобразования n в суб-логарифмическое выражение n.