Обработка делает дубликаты ключа в дереве AVL
Я хочу сделать мой avl-tree поддержка делает дубликаты ключа, но существует проблема с поведением по умолчанию binary search tree с дубликатами, что вращение могло заставить узлы с равным ключом быть слева и справа от родителя.
Например, при добавлении трех узлов все с ключом A заставят дерево делать вращение, чтобы быть чем-то вроде этого:
A
/ \
A A
Так получение всех записей с тем ключом будет проблемой..., и ищущий в обоих направлениях не хорошо.
Решение, о котором я думал, делает каждые хранилища узла массивом дубликатов поэтому при добавлении нового объекта, который уже существует, будет просто добавлять, что новый объект к массиву, удаляя объект с ключом удалит целый узел, в то время как находка все объекты с ключом возвратит тот массив.
Есть ли существуют какие-либо другие методы для обработки дубликатов?
Объект вставки берет ключ и значение.. таким образом, я должен сохранить значения inorder для возврата их findAll с определенным ключевым методом.
2 ответа
Другой общий подход состоит в том, чтобы внутренне сделать значение частью ключа, чтобы у вас больше не было дублирующихся ключей. В любом случае вам понадобятся и ключ, и значение, чтобы удалить запись из дерева, допускающего дублирование.
Чтобы найти ключ, не зная значения, вы должны сделать что-то вроде (псевдокода):
searchResult = myTree.SearchGreaterOrEqual(Key);
found = (searchResult != null) && (searchResult.Key == Key);
Сделайте так, чтобы каждый узел содержал счетчик: добавление дубликатов приведет к увеличению счетчика, при удалении будет уменьшаться счетчик, если он не равен 1, и в этом случае будет удален весь узел.