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

Question

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

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

   A
  /  \ 
 A    A

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

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

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

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

Answer 1

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

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

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

Answer 2

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