Löschen von einer Balanced-Binary-Suchstruktur

Question

Ich möchte einen Knoten aus einer Balanced BST löschen. Ich schrieb den folgenden Code, und es funktioniert beim Löschen eines Kindes, aber wenn ich einen Knoten mit zwei Kindern löschen möchte, wird eine Verbindung wiederhergestellt, aber ich verliere den anderen Knoten. Dies ist mein Code:

Nod* minValue(Nod *p) 
{ 
    Nod *q = p; 

    while (q->stg != NULL) 
     q = q->stg; 

    return q; 
} 

Nod* os_delete(Nod *p, int k) 
{ 
    if (p == NULL) 
     return p; 

    if (k < p->ch) 
    { 
    p->stg = os_delete(p->stg, k); 
    } 

    else if (k > p->ch) 
    { 
    p->dr = os_delete(p->dr, k); 
    } 

    else 
    { 
     p->size--; 
     if (p->stg = NULL) 
     { 
      Nod* aux = p->dr; 
      free(p); 
      return aux; 
     } 
     else if (p->dr == NULL) 
     { 
      Nod* aux = p->stg; 
      free(p); 
      return aux; 
     } 

     Nod* aux = minValue(p->dr); 
     p->ch = aux->ch; 
     p->dr = os_delete(p->dr, aux->ch); 
    } 
    return p; 

}

Zum Beispiel:

  9 
    4   15 
1  7 10  18 

Wenn ich den Knoten mit dem Schlüssel 4 ist das Ergebnis Baum wird gelöscht werden soll:

 9 
7   15 
      10  18 

Bearbeiten:

typedef struct nod 
{ 
    int ch, size; // ch - key of the node; size - size of node's subtree 
    struct nod *stg, *dr; // stg - left; dr - right 
}Nod; 

Answer 1

Eine Möglichkeit zum Löschen aus einem ausgeglichenen Binärbaum ist das Erstellen einer Funktion balance(). Dies wird verwendet, um den Baum neu zu balancieren. Kopieren Sie die Referenzzeiger der Elemente im Binärbaum in eine Liste in Inorder. Dann finden Sie das mittlere Element der Liste (die Liste wird in zwei Hälften geteilt). Es wird dein neuer Wurzelknoten sein. Das linke Kind des Wurzelknotens wird die Mitte der linken Hälfte der Liste sein, und das rechte Kind des Wurzelknotens wird die Mitte der rechten Hälfte der Liste sein. Führen Sie dies rekursiv durch, um einen ausgeglichenen Baum zu erstellen. Verwenden Sie diese Funktion jetzt im Löschprozess. Während Sie den Knoten finden, der gelöscht werden soll, behalten Sie den Überblick über den übergeordneten Knoten. Erstellen Sie nun die Löschlogik wie im Falle einer BST, aber verwenden Sie diese balance() -Funktion, um den Baum bei Bedarf neu zu balancieren. Quelle: http://www.codeproject.com/Articles/68500/Balanced-Binary-Search-Tree-BST-Search-Delete-InOr

Ich bin nicht sicher, wie Sie versuchen, den Baum ausgeglichen zu halten, aber ein anderer einfacher Weg ist die Implementierung von selbstausgleichenden binären Suchbäumen wie AVL oder R-B-Baum.