Дубликаты в двоичном дереве поиска

Question

Каков элегантный способ обработки дубликатов в двоичном дереве поиска? Предположим, что каждый ключ будет иметь несколько разных значений. То, что мне нужно сделать, это перебрать все значения по порядку. Поэтому, если бы у меня было 2 значения A и B с ключом 1 и одно значение C с ключом 2, я бы хотел получить пары: (1, A), (1, B), (2, C), когда вы вызываете что-то вроде TreeIterator.next();

я могу думать:

• Каждый узел имеет ключ, и массив значений, где значения с тем же ключом идти
• Каждый узел имеет visited флаг

Любые другие предложения? В качестве общего руководства я хотел бы, чтобы реализация Tree была максимально абстрактной.

Answer 1

Похоже, в основном вы do хотите список значений для каждой клавиши, да. Таким образом, процесс добавления на карту:

• Существует ли ключ?
  • Если да, добавьте значение в существующий список.
  • Если нет, то создать новый узел в дереве в соответствующей точке (как обычно), и начните со списком одного значения

При переборе над картой, ваш общий паттерн:

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

Конечно, если вам не нужно осуществить это самостоятельно для целей обучения, вы можете использовать готовые Multimap, такие как Guava «s TreeMultimap. Если вы :, внедряя его для самообразования, я бы начал с реализации «нормальной» бинарной карты поиска, а затем оттуда.