Strategia per trovare le voci duplicate in un albero di ricerca binario

Question

Ho un BST che ha voci duplicate. Sto cercando di trovare voci duplicate. Ora ovviamente posso scrivere un algoritmo stupido che attraversa l'intero albero, che è facile.

Tuttavia, desidero scriverne uno più efficiente. Ecco cosa ho fatto/pensato finora:

Assumere l'albero seguente.

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

Se voglio trovare tutte 8 di, io per prima trovare il 8 sulla sottoalbero sinistro del 10. Per trovare un duplicato, se non ha figlio destro, sta andando essere più a sinistra nodo nella sottostruttura di destra del primo genitore che è più grande di quel nodo (8)? E se ha avuto un figlio giusto, allora può essere o nel nodo più a sinistra del suo sottoalbero destro o nel nodo più a destra nel suo sottoalbero sinistro?

Sono tutti questi casi, che possono essere raggiunti con una serie di loop e if-statement?

In caso negativo, qual è l'approccio migliore? Qualcuno può aiutare?

Grazie

EDIT: In realtà ho appena capito che non può essere il "più nodo di sinistra" o "nodo più a destra". Quello troverebbe il nodo che è il prossimo valore più alto o il valore più basso precedente. Prima sarebbe un nodo?

EDIT 2:

fisso il mio esempio BST. Segue il seguente metodo di inserimento:

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

Ciò significa che i duplicati saranno aggiunti alla destra dei loro duplicati .. giusto?

Answer 1

1. Trova un elemento che corrisponde al tasto utilizzando il solito binario di algoritmo di ricerca albero. Se non si trova, fermati.
2. Esaminare il ramo secondario LH. Se la sua chiave corrisponde, rendi il nodo corrente e ripeti questo passaggio.
3. Ora sei al primo elemento dell'albero con quella chiave. Ora fai un albero a piedi da questo nodo mentre i tasti sono uguali, cioè visita questo nodo, il sottoalbero destro, il genitore, il sottoalbero destro del genitore, ecc., Lasciato come esercizio per il lettore.

Answer 2

L'albero che mostri presume (beh, almeno presumo ... ;-)) che meno di quanto sono a sinistra, e maggiore di quello a destra, ho ragione?

Quindi ci sono due cose che si dovrebbero prendere in considerazione:

1. Il tuo albero è sbagliato! Il secondo "8" a destra della testa "10" non può essere lì, poiché è inferiore a 10. Un inserimento corretto, e un bilanciamento corretto, sarebbero entrambi molto vicini, se non proprio alla "prossima" iterazione dalla "sinistra 8".

2. Definendo l'albero come "meno-o-uguale" a sinistra e "maggiore di" a destra, si otterrebbe il risultato desiderato: tutti gli "8" saranno incatenati al lasciati l'uno dall'altro su un semplice albero di inserimento.

Answer 3

Un algoritmo ricorsivo può risolvere questo rapidamente. Non è necessario ricorrere all'intero albero, poiché è possibile utilizzare la struttura del BST per rintracciare i valori necessari.

Quello che hai disegnato non è strettamente un BST, potrei sbagliarmi, ma credo che sia piuttosto rotto - tutti i numeri nell'albero di sinistra dovrebbero essere meno di 10, e viceversa.

Answer 4

Questa implementazione utilizza metodo ricorsivo e restituire una serie di voci duplicate

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