Red Black Tree Löschen der Wurzel

Question

Mein Rot-Schwarz-Baum-Algorithmus zum Löschen funktioniert gut, es sei denn, ich lösche die Wurzel. Wo nur eines der Kinder gespeichert wird und der Rest der Baumwerte verloren geht.

Ich glaube, das Problem in den removeNode() Verfahren in den Leitungen ist, wo

if (remove == root) 
{ 
    root = child; 
} 

die Methoden zum Löschen verwenden Hier sind:

//Searching for value to remove 
public void removeSearch(int value) 
{ 
    RedBlackNode rt = root; 
    while (rt != sentinel) 
    { 
     int compare = value.CompareTo(rt.getItem()); 
     if (compare == 0) 
     { 
      if (rt.getLeft() == sentinel || rt.getRight() == sentinel) 
      { 
       removeNode(rt); 
      } 
      else 
      { 
       RedBlackNode successor = inOrderSuccessor(rt); 
       rt.setItem(successor.getItem()); 
       removeNode(rt);       
      } 
      return; 
     } 
     else 
     { 
      rt = rt.getChild(compare); 
      //return true; 
     } 
    } 
} 

protected RedBlackNode inOrderSuccessor(RedBlackNode node) 
{ 
    RedBlackNode descendant = node.getRight(); 

     while (descendant.getLeft() != sentinel) 
     { 
      descendant = descendant.getLeft(); 
     } 
    return descendant; 
} 

protected void removeNode(RedBlackNode remove) 
{ 
    count -= 1; 
    RedBlackNode child; 
    if (remove.getLeft() != sentinel) 
    { 
     child = remove.getLeft(); 
    } 
    else 
    { 
     child = remove.getRight(); 
    } 
    linkParentAndChild(remove.getParent(), child, comparison(remove, remove.getParent())); 

    if(remove==root) 
    { 
     root = child; 
    } 
    if(remove.isBlack()) 
    { 
     DeleteFix(child); 
    } 
} 

protected void DeleteFix(RedBlackNode node) 
{ 
    while((node!=root)&&(node.isBlack())) 
    { 
     RedBlackNode parent = node.getParent(); 
     int compare = comparison(node, parent); 
     RedBlackNode sibling = parent.getChild(-compare); 
     if(sibling.isRed()) 
     { 
      sibling.setBlack(); 
      parent.setRed(); 
      rotate(-compare, parent); 
      sibling = node.getParent().getChild(-compare); 
     } 
     if(sibling.hasTwoBlackChildren()) 
     { 
      sibling.setRed(); 
      node = node.getParent(); 
     }else 
     { 
      if(sibling.getChild(-compare).isBlack()) 
      { 
       sibling.getChild(compare).setBlack(); 
       sibling.setRed(); 
       rotate(compare, sibling); 
       sibling = parent.getChild(-compare); 
      } 
      sibling.setColour(parent.getColour()); 
      parent.setBlack(); 
      sibling.getChild(-compare).setBlack(); 
      rotate(-compare, parent); 
      node = root; 
     } 
    } 
    node.setBlack(); 
} 

Jede Hilfe wäre toll. Dank

Answer 1

Spaziergang durch das mit mir:

if (remove.getLeft() != sentinel) 
{ 
    child = remove.getLeft(); 
} 
else 
{ 
    child = remove.getRight(); 
} 
linkParentAndChild(remove.getParent(), child, comparison(remove, remove.getParent())); 

if(remove==root) 
{ 
    root = child; 
} 

Zunächst sei angenommen remove == root. Angenommen, das linke Kind des Stammverzeichnisses lautet sentinel. Der erste if-Zweig wird als false ausgewertet, die else-Klausel wird ausgeführt und child wird zum rechten Knoten. Dann versuchst du, die Eltern der Wurzel zu bekommen (vermutlich null, aber ich habe keine Ahnung) und verbinde das mit dem richtigen Knoten ... Ich schätze, dass das nichts bringt, aber ich weiß es nicht genau, weil du es nicht getan hast. t stellen diese Methode zur Verfügung. Dann ersetzen Sie die Wurzel mit child, die der rechte Knoten ist, und weil linkParentAndChild (vermutlich) in null übergeben wurde, gab es keine Möglichkeit, den linken Knoten wiederherzustellen, so dass Sie es überlisten und es ist weg. Wenn der linke Knoten nicht sentinel ist, dann ist der Prozess genau der gleiche, aber Sie behalten die linke Seite statt der rechten Seite.

Hoffentlich sollte das aufklären, warum es passiert. Ich werde dir aus zwei Gründen nicht sagen, wie man es löst:

1. Das ist fast sicher Hausaufgaben, niemand implementiert einen rot-schwarzen Baum, es sei denn, es ist für die Hausaufgaben.
2. Ich erinnere mich nicht wirklich die Implementierungsdetails der rot-schwarzen Bäumen sehr gut, vor allem aufgrund Grund Nummer 1.

Viel Glück es zu lösen!