Eliminazione di un nodo e restituzione del valore del nodo eliminato in una struttura di ricerca binaria?

Question

Eliminazione di un nodo e restituzione del valore del nodo eliminato in una struttura di ricerca binaria?

#1 da (2 voti)
#2 da (0 voti)

4

Ciao, ho un progetto di programmazione in cui utilizzo fondamentalmente un albero di ricerca binario per implementare una coda di priorità minima / massima. Sto avendo problemi con i metodi popMin / popMax. Ottengo come ottenere il nodo minimo / massimo e rimuovere un nodo, ma ho problemi a eseguire entrambi con un singolo metodo ricorsivo.

Non capisco come posso restituire il valore nullo da assegnare al valore sinistro del nodo genitore e anche restituire il valore minimo al chiamante del metodo originale.

In questo momento sto solo usando una variabile di classe min per registrare il minimo, ma non sono sicuro che sia assolutamente necessario. La mia classe nodo non è consentita un membro dati padre.

Ecco il mio codice:

private int min;

public int removeMin() {

    if (root == null) { //if Queue is empty
        System.out.println("Queue is empty");
        return 0;
    }
    root = removeMin(root);

    return min;

}


private Node removeMin(Node n){
    if (n.left == null) {
        min = n.key;
        if (n.right != null){ //if a right child exists
            size--;
            return n.right;
            }
        else {
            size--;
            n = null;
            return n;
        }
    } else {
        n.left = removeMin(n.left);
        return n;
    }

}

java data-structures binary-tree

posta Justin 22.11.2016 - 02:03

fonte

2 risposte

0

In Java, puoi tentare di restituire più valori, tramite un oggetto di una classe definita solo per quell'aggregato. Vedi Come vengono restituiti più valori in Java? .

In alternativa, puoi ridisegnare il tuo metodo privato per eseguire il lavoro di assegnazione del nuovo albero al genitore, passando un parametro aggiuntivo. Non testato, ma qualcosa di simile:

public int removeMin () {
    if ( root == null ) { //if Queue is empty
        System.out.println ( "Queue is empty" );
        return 0;
    }
    return popMin ( null, root );
}

private void setParentLeft ( Node parent, Node node ) {
    if ( parent == null )
       root = node;
    else
       parent.left = node;    
}

private int popMin ( Node parent, Node node ) {
    if ( node.left == null ) {
        if ( node.right != null ) { //if a right child exists
            size--;
            setParentLeft ( parent, node.right );
        }
        else {
            size--;
            setParentLeft ( parent, null );
        }
        return node.key;
    } else {
        return popMin ( node, node.left );
    }
}

in questo caso, che ha anche il vantaggio di essere ora ricorsione di coda, su cui possiamo lasciare lavorare il compilatore o, manualmente, qui una semplice versione non ricorsiva:

private int popMin ( Node parent, Node node ) {
    for (;;) {
        if ( node.left == null ) {
            if ( node.right != null ) { //if a right child exists
                size--;
                setParentLeft ( parent, node.right );
            }
            else {
                size--;
                setParentLeft ( parent, null );
            }
            return node.key;
        }

        parent = node;
        node = node.left;
    }
}

risposta data 22.11.2016 - 02:45

fonte

Leggi altre domande sui tag java data-structures binary-tree

Come rendere efficienti gli oggetti in un database? Rimozione di dati non necessari da un oggetto Utente in API

score 2 · Accepted Answer

Elimina la ricorsione. Di solito hai bisogno di una ricorsione quando hai a che fare con gli alberi perché devi visitare tutti i percorsi, ma qui puoi visitare solo un bambino in ogni livello - puoi farlo con un ciclo. Inoltre, mentre il tuo codice sembra come se fosse in grado di aggiornare i nodi a qualsiasi livello mentre si esegue up la ricorsione, in realtà cambia solo un nodo - il genitore del nodo con un valore minimo. Dal momento che rilevi che quel nodo deve essere cambiato di un livello dopo averlo visitato (quando raggiungi la fine del percorso più a sinistra) non hai bisogno di rimescolarlo: puoi semplicemente mantenere il livello genitore in una variabile:

public int removeMin() {
    if (root == null) { //if Queue is empty
        System.out.println("Queue is empty");
        return 0;
    }

    if (root.left == null) { // Edge case - no left child, root is the min
        int min = root.key;
        if (root.right == null) {
            root = null;
        } else {
            root = root.right;
        }
        return min;
    }

    // Start going left
    Node parent = root;
    Node node = parent.left;

    while(node.left != null) {
        parent = node;
        node = parent.left;
    }

    // node.left is null, so node is the min
    parent.right = node.right; // which could be null - it works either way
    return node.key;
}