Обработка дубликатов ключей в дереве AVL

Question

Я хочу, чтобы моя avl-tree поддерживала дубликаты ключей, но есть проблема с поведением по умолчанию binary search tree с дубликатами, из-за которого при повороте узлы с одинаковым ключом могли быть слева и справа от родителя.

Например, при добавлении трех узлов с ключом A дерево будет вращаться примерно так:

   A
  /  \ 
 A    A

Таким образом, получение всех записей с этим ключом будетпроблема ... и поиск в обоих направлениях не годится.

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

Существуют ли другие методы для обработки дубликатов?

Вставкаitem принимает ключ и значение .. поэтому мне нужно сохранить значения в порядке, чтобы они возвращались методом findAll с определенным методом ключа.

Answer 1

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

Чтобы найти ключ, не зная значения, вы должны сделать что-то вроде (псевдокод):

searchResult = myTree.SearchGreaterOrEqual(Key);
found = (searchResult != null) && (searchResult.Key == Key);

Answer 2

У каждого узла есть счетчик: добавление дубликатов будет увеличивать счет, удаления будут уменьшать счет, если только он не равен 1, и в этом случае весь узел будет удален.