Entfernen eines Knotens mit zwei Kindern in BST

Question

Ich versuche, einen binären Suchbaum zu implementieren, und ich habe ein Problem mit Knoten entfernen. Ich habe einige Tests gemacht und ich denke, das einzige Problem mit meiner Funktion ist der Fall, in dem der zu entfernende Knoten hat zwei Kinder. Ich habe irgendwo in den Referenzen versaut. Es scheint ein einfaches Problem zu sein, aber ich habe versucht, es zu lange selbst zu beheben.

Answer 1

Es gibt mehrere Probleme.

Erstens, was auch immer der Fall ist, wenn Sie die x==k->val Bedingung erreichen und es ist wahr, Sie immer müssen den Knoten löschen, der derzeit von k gezeigt wird.

if (x == k->val) 
{ 
    tmp=k;  // keep track of the node to delete 
    ...   // update k but don't return (and don't change tmp) 
    delete tmp; // get rid of the deleted node for good 
} 

Dann hat der Artikel überhaupt kein Kind, man muss nur den Zeiger in der übergeordneten auf nullptr. Wenn der iem ein Kind hat, machst du einfach einen Pass-trough.

if (k->l==nullptr && k->r==nullptr) 
     k=nullptr; 
    else if (k->l==nullptr) 
     k=k->r; 
    else if (k->r==nullptr) 
     k=k->l; 
    else { //two children 
     ... 
    } 

Wenn der Knoten auf Kinder hat, ist es komplizierter

else { //two children 
     k=k->l; // take the left subtree 
     for (rem=k; rem->r!=nullptr; rem=rem->r) 
      ;  // find the end of its right subtree 
     rem->r = tmp->r; // append the right subtree at its end. 
    } 

Hier die grafische Erklärung dessen, was hier passiert:

Es gibt Sie!