java albero binario di ricerca

Question

Ho una domanda su come avrei rimuovere un bambino da un nodo (root)? Dal momento che non posso chiamare rimuovere, se faccio il nulla del bambino, saranno i figli di quel bambino spostarsi verso l'alto? Come, dovrei proprio inizializzare come null ?? O dovrei puntare al bambino del bambino?

Answer 1

In un tradizionale albero binario di ricerca, la rimozione di un nodo può avere conseguenze diverse a seconda di quanti figli il nodo ha:

• Un nodo senza figli può essere semplicemente rimossa
• Un nodo con un bambino può essere rimosso, e il nodo viene sostituito con il suo unico figlio. Ciò vale indipendentemente dal fatto che il bambino è un bambino a sinistra oa destra.
• Un nodo con due figli ha una regola un po 'più complicato: si deve trovare la successore in ordine o in-order predecessore del nodo da rimuovere, sostituire il valore del nodo corrente con il suo successore di o il valore di precedente, quindi eliminare il successore o precedente (in base a queste regole).

Answer 2

E 'questo compito? Niente di male ... abbiamo appena piace aiutare le persone a imparare, piuttosto che dire loro le risposte.

Se è sufficiente impostare il nodo figlio a null perderai tutte le informazioni sui Childs bambini.

Answer 3

Una classe albero standard sarà conoscere i suoi figli, di solito bloccato in un array o Collection - nel caso di un albero binario, hai solo due figli diretti, in modo da una matrice fissa di dimensioni funzionerà. A causa di ciò, di solito attuare una sorta di metodo "removeMe" che il bambino chiama a ottenere da quella stessa lista dei bambini.

Come accennato in precedenza, questo si complica se il bambino si sta rimuovendo ha dei figli.

Answer 4

La risposta di Tim sembra migliore. Ma sì, si vuole fare una delle tre cose a seconda di quale tipo di bambino è il vostro rimozione. Se si effettua un bambino nullo, i figli di essa non si muove in su perché hai perso riferimento ad essi. Invece, ti consigliamo di determinare se i bambini sinistro o destro del bambino vostra rimozione deve essere impostato al puntatore che punta al bambino il vostro rimozione. Dopo aver impostato il precedente nodi puntatore (destra o sinistra) per il bambino (sinistra o destra) del nodo vostra rimozione, non dovrete un riferimento più a quel nodo, quindi non c'è nessun bisogno di impostare a NULL (si puo' t accesso più. a meno che non hai scritto una sorta di BST doppiamente-linked, nel qual caso non è questo il BST classico)

Answer 5

Questo codice dovrebbe aiutare a

public Node<T> getParentOf(Node<T> child){
    findParentOf(this.root, child);
    return temp;
}

private void findParentOf(Node<T> ROOT, Node<T> child){
    if(ROOT.hasLeft()){
        findParentOf(ROOT.left, child);
    }

    if(ROOT.left == child || root.right == child){
        temp = ROOT;
    }

    if(ROOT.hasRight()){
        findParentOf(ROOT.right, child);
    }
}


private void replaceNode(Node<T> original, Node<T> newNode){
    Node<T> tempParent = getParentOf(original);
    if(original == tempParent.left){
        tempParent.left = newNode;
    }else if(original == tempParent.right){
        tempParent.right = newNode;
    }
}

private void traverseChildrenAndAdd(Node<T> newParent, Node<T> oldParent){
    newParent.insert(oldParent.data);
    if(oldParent.hasLeft()){
        traverseChildrenAndAdd(newParent,oldParent.left);
    }



    if(oldParent.hasRight()){
        traverseChildrenAndAdd(newParent,oldParent.right);
    }
}
private void deleteNode(Node<T> ROOT, Node<T> d){
    if(d.data.compareTo(ROOT.data) < 0){
        deleteNode(ROOT.left, d);
    }else if(d.data.compareTo(ROOT.data) > 0){
        deleteNode(ROOT.right, d);
    }else if(d == this.root){
        if(this.root.hasLeft()){
            traverseChildrenAndAdd(root.left, root.right);
            root = root.left;
        }else if(root.hasRight()){
            root = root.right;
        }else{
            root = null;
        }
    }else{
        if(ROOT.hasLeft()&&ROOT.hasRight()){
            Node<T> successor = getMinNode(ROOT);
            replaceNode(successor, successor.right);
        }else if(ROOT.hasLeft() || ROOT.hasRight()){
            if(ROOT.hasLeft()){
                replaceNode(ROOT, ROOT.left);
            }else{
                replaceNode(ROOT, ROOT.right);
            }
        }else{
            replaceNode(ROOT, null);
        }
    }
}

public void remove(T data){
    deleteNode(this.root, new Node<T>(data));
}

Answer 6

Si può fare qualcosa di simile (pseudo codice):

Dato un la radice dell'albero "root" e il nodo di cancellare alcuni dati o "x" effettuare le seguenti

 if x < root
      recurse to left child
 if x > root
      recurse to right child
 else //node found
      find the min item of the node right child //min item should be left most leaf node node
      replace the value of the node you want to delete with min nodes value
      now delete the min node
 return root;

codice:

delete(Node root, Object x){
    if(root == null){
        return null;
    }

    if(data < root.data){
        root = delete(root.left);
    }else if(root.data < data){
        root = delete(root.right);
    }else{
        if(root.left != null && root.right != null){
            Object tmp = findMin(root.right);
            root.data = tmp;
            root.right = delete(root.right, tmp);
        }else{
            return (root.left != null) ? root.left : root.right;    
        }
    }
return root;

}