Estrategia para encontrar entradas duplicadas en un árbol de búsqueda binaria

Question

Tengo una BST que tiene entradas duplicadas. Estoy tratando de encontrar entradas duplicadas. Ahora, obviamente, puedo escribir un algoritmo tonto que atraviesa todo el árbol, lo cual es fácil.

Sin embargo, quiero escribir uno más eficiente. Esto es lo que he hecho/pensado hasta ahora:

Supongamos el siguiente árbol.

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

Si quiero encontrar toda de 8, voy a encontrar primero el 8 en el subárbol izquierdo de la 10. Para obtener un duplicado, si no tiene un hijo derecho, es que va a ser la más a la izquierda nodo en el subárbol derecho del primer padre que es más grande que ese nodo (8)? Y si tenía un hijo correcto, ¿puede estar en el nodo más a la izquierda de su subárbol derecho o en el nodo más a la derecha en su subárbol izquierdo?

¿Son esos todos los casos, que se pueden lograr con un montón de bucles y declaraciones if?

Si no, ¿cuál es el mejor enfoque? ¿Alguien puede ayudar?

Gracias

EDIT: En realidad me di cuenta de que no puede ser el "nodo más a la izquierda" o "derecha nodo más". Eso encontraría el nodo que es el siguiente valor más alto o el valor más bajo anterior. ¿Sería un nodo antes?

EDIT 2:

fijo mi ejemplo BST. De ello se desprende el siguiente método de inserción:

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)); 

Esto significa duplicados se añadirán a la derecha de sus duplicados .. ¿verdad?

Answer 1

1. Encuentra un elemento que coincide con su clave usando el algoritmo de búsqueda de árbol binario de costumbre. Si no se encuentra, parar.
2. Examine la subdivisión LH. Si su clave coincide, haga que el nodo actual y repita este paso.
3. Ahora se encuentra en el primer elemento del árbol con esa clave. Ahora haga una caminata de árbol desde este nodo mientras las claves son iguales, es decir, visite este nodo, el subárbol correcto, el elemento primario, el subárbol derecho de los padres, etc., que dejó como ejercicio para el lector.

Answer 2

El árbol que muestra asume (bueno, al menos asumo ... ;-)) menos que a la izquierda, y mayor que a la derecha, ¿estoy en lo cierto?

Así que hay dos cosas que usted debe considerar:

1. Su árbol está mal! El segundo "8" a la derecha de la cabeza "10" no puede estar allí, ya que es menor que 10. Una inserción correcta y un equilibrio correcto, ambos se pondrían muy cerca, si no es correcto en la "siguiente" iteración de la "izquierda 8".

2. Al definir el árbol como "menor que igual" a la izquierda y "mayor que" a la derecha, obtendría el resultado deseado: todos los "8" estarán encadenados al a la izquierda de cada uno en un árbol de inserción simple.

Answer 3

Un algoritmo recursivo puede resolver esto rápidamente. No tiene que recurrir sobre todo el árbol, ya que puede usar la estructura de BST para buscar los valores que necesita.

Lo que ha dibujado no es estrictamente una BST, podría estar equivocado, pero creo que está bastante roto: todos los números en el árbol de la izquierda deberían ser menos de 10, y viceversa.

Answer 4

Esta aplicación utiliza el método recursivo y devolver una matriz de entradas duplicadas

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[] {}); 
}