имея дело с дубликатами в BST

Question

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

Answer 1

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

Редактировать (после замечания Симонна):

Если у рассматриваемого «дублирующего узла» уже есть 2 дочерних элемента, просто вставьте «новый дублирующий узел» влево и пусть левый дочерний элемент «старого дублирующего узла» станет левым дочерним элементом «нового дублирующего узла» ».

Позвольте мне уточнить на примере. Дерево перед вставкой дубликата:

    4'
   / \
  2   5
 / \
1   3

А теперь элемент 4'' вставлен:

      4'
     / \
    4'' 5
   /
  2   
 / \
1   3

Пока дерево не является самобалансирующимся, с вами должно быть все в порядке.

Answer 2

Вы можете превратить узлы двоичного дерева поиска в связанные списки.

class Data implements Comparable<Data>
{
   // These are the data elements in your binary search tree
}

class TreeNode
{
  TreeNode left; // elements less than current node, or null
  TreeNode right; // elements greater than current node, or null
  List<Data> items = new LinkedList<Data>();    
}

Здесь treeNode.items - это всегда непустой список, такой что item1.compareTo(item2) == 0 для каждого item1 и item2 в treeNode.items.

Чтобы вставить дубликат элемента, вы найдете соответствующий объект TreeNode и добавите новый элемент в items.

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

Answer 3

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