Спецификация производительности для обработки повторяющихся ключей в двоичном дереве поиска

Question

Я читал книгу Введение в алгоритмы поиск лучших способов обработки повторяющихся ключей в двоичном дереве поиска.

Там несколько способов, указанные для этого случая использования:

1. Keep булево флаг x:b в узле x, и установить x к либо x:left или x:right на основе значения x:b, который чередуется между FALSE и TRUE каждый раз, когда мы посетим x, вставляя узел с тем же ключом, что и x.

2. Сохраните список узлов с равными ключами на x и вставьте 'в список.

3. Произвольно установлено x либо x:left, либо x:right.

Я понимаю, каждая реализация имеет свои хиты производительности/промахи, и STL может реализовать его по-разному от Boost Containers.

Является ли ограничение производительности упомянутым в спецификации C++11 наихудшей производительностью обработки дубликатов ключей, например, для multimap?

Answer 1

С точки зрения времени вставки/удаления 2 всегда лучше, потому что это не увеличит размер дерева и не потребует сложных изменений структуры при вставке или удалении дубликата.

Вариант 3 является оптимальным пространством, если имеется небольшое количество дубликатов.

Вариант 1 потребует хранения 1 дополнительный бит информации (которая, в большинстве реализации занимает 2 байта), но высота дерева будет оптимальным по сравнению с 1.

TL; DR: Реализация 2 является немного сложно, но стоит, если количество дубликатов велико. В противном случае используйте 3. Я бы не использовал 1.