Стратегия поиска повторяющихся записей в бинарном дереве поиска

Question

У меня есть BST, в котором есть повторяющиеся записи. Я пытаюсь найти повторяющиеся записи. Теперь, очевидно, я могу написать тупой алгоритм, который пересекает все дерево, что легко.

Однако я хочу написать более эффективный. Вот что я сделал / подумал до сих пор:

Предположим следующее дерево.

      10
     /   \
    5    15
   /\    / \
  2  8   10 16
      \    \
       8   12

Если я хочу найти все 8, я сначала найду 8 в левом поддереве из 10. Чтобы найти дубликат, если у него нет правого потомка, это будет самый левый узел справа -дерево первого родителя, который больше этого узла (8)? И если у него был правый потомок, то он может находиться либо в самом левом узле своего правого поддерева, либо в самом правом узле левого поддерева?

Это все случаи, которых можно достичь с помощью набора циклов и операторов if?

Если нет, то какой подход лучше? Кто-нибудь может помочь?

Спасибо

EDIT: На самом деле я только что понял, что это не может быть «самый левый узел» или «самый правый узел». Это найдет узел, который является следующим самым высоким значением или предыдущим самым низким значением. Будет ли это один узел раньше?

РЕДАКТИРОВАТЬ 2:

Исправлен мой пример BST. Следует следующий метод вставки:

if (node == null) 
    return new NodeBST<Value>(name, value);

if (node.key().compareTo(name) > 0)
    node.setLeft(insert(node.left(), name, value));     
else
    node.setRight(insert(node.right(), name, value));

Это означает, что дубликаты будут добавлены справа от их дубликатов .. верно?

Answer 1

1. Найдите элемент, соответствующий вашему ключу, используя обычный алгоритм поиска в двоичном дереве. Если не найдено, остановитесь.
2. Изучите подразделение LH. Если его ключ совпадает, сделайте его текущим узлом и повторите этот шаг.
3. Теперь вы находитесь на первом элементе дерева с этим ключом. Теперь выполните обход дерева этого узла, пока ключи равны, то есть посетите этот узел, правое поддерево, родительский элемент, правое поддерево родителя и т. Д., Оставленные в качестве упражнения для читателя.

Answer 2

Дерево, которое вы показываете, предполагает (ну, по крайней мере, я предполагаю ... ;-)), что меньше, чем слева, и больше, чем справа, я прав?

Итак, есть две вещи, которые вы должны рассмотреть:

1. Ваше дерево не так! Вторая «8» справа от головки «10» не может быть там, так как она меньше 10. Правильная вставка и правильная балансировка будут очень близки, если не прямо на «следующей» итерации от "левого 8".

2. Определив дерево как «меньше или равно» слева и «больше чем» справа, вы получите желаемый результат: все «8» будут прикованы к слева друг от друга на простом дереве вставки.

Answer 3

Эта реализация использует рекурсивный метод и возвращает массив повторяющихся записей

public class TreeNode<E> {
    public int data;
    public TreeNode left;
    public TreeNode right;
}

public Integer[] findDuplicate(TreeNode tree) {
    Map<Integer, Integer> entries = new HashMap<>();
    List<Integer> duplicates = new LinkedList<>();

    return (Integer[]) findDuplicate(tree, entries, duplicates);
}

private Integer[] findDuplicate(TreeNode tree, Map entries, List duplicates) {
    if (tree == null) 
        return (Integer[]) duplicates.toArray(new Integer[] {});

    if (entries.containsKey(tree.data))
        duplicates.add(tree.data);
    else 
        entries.put((int) tree.data, 1);

    findDuplicate(tree.left, entries, duplicates);
    findDuplicate(tree.right, entries, duplicates);

    return (Integer[]) duplicates.toArray(new Integer[] {});
}

Answer 4

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

То, что вы нарисовали, не является строго BST, я могу ошибаться,но я полагаю, что он довольно разбит - все числа в левом дереве должны быть меньше 10, и наоборот.