Binary Suchanfrage Baum, entfernen Sie Knoten muss hier helfen (reposting)

Question

Mein Code ist wie folgt aussehen:

class Treenode: 
    def __init__(self,data,left=None,right=None): 
     self.data=data 
     self.left=left 
     self.right=right 

    def __str__(self): 
     return str(self.data) 

    def delete(self): 
     child=self.left 
     grandchild=child.right 
     print(grandchild) 
     if self.left == self.right==None: 
      return None 
     if self.left==None: 
      return self.right 
     if self.right==None: 
      return self.left 
     if grandchild: 
      while grandchild.right: 
       child = grandchild 
       grandchild = child.right 
      self.data = grandchild.data 
      child.right = grandchild.left 
     else: 
      self.left = child.left 
      self.data = child.data 
     return self 

class Bintree: 
    def __init__(self): 
     self.root = None 

    def put(self,data): 
     if self.root == None: 
      self.root = Treenode(data) 
      return 
     p = self.root 
     while True: 
      if data < p.data: 
       if p.left == None: 
        p.left = Treenode(data) 
        return 
       else: 
        p = p.left 
      elif data > p.data: 
       if p.right == None: 
        p.right = Treenode(data) 
        return 
       else: 
        p = p.right 
      elif data == p.data: 
       return False 
      else: 
       return 

    def exists(self, data): 
     return finns(self.root, data) 

    def isempty(self): 
     return self.root == None 

    def height(self): 
     def hp(tree): 
      if tree is None: 
       return 0 
      else: 
       return 1 + max(hp(tree.left), hp(tree.right)) 
     return hp(self.root) 

    def printTree(self): 
     skriv(self.root) 

    def remove(self, data): 
     if self.root and self.root.data == data: #self.root kanske inte behövs, undersök 
      self.root = self.root.delete() 
      return 
     else: 
      parent = self.root 
      while parent: 
       if data < parent.data: 
        child = parent.left 
        if child and child.data== data: 
         parent.left = child.delete() 
         return 
        parent = child 
       else: 
        child = parent.right 
        if child and child.data == data: 
         parent.right = child.delete() 
         return 
        parent = child 



def skriv(tree): 
    if tree == None: 
     return 
    skriv(tree.left) 
    print(tree.data) 
    skriv(tree.right) 

def finns(roten, key): 
    if roten == None: 
     return False 
    if key == roten.data: 
     return True 
    elif key < roten.data: 
     return finns(roten.left, key) 
    else: 
     return finns(roten.right, key) 

Alles über meinen Code funktioniert, und ich habe einfach (siehe kopiert), um die Löschmethode hinzugefügt und die Entfernungsmethode. Ich versuche verzweifelt die Löschmethode zu verstehen, aber ich kann es nicht verstehen. Ich benutze diesen Code, um die Sache zu laufen und zu sehen, wie der Baum implementiert:

from labb8test import Bintree 
from labb8test import Treenode 

tree = Bintree()  
tree.put(8)  
tree.put(3) 
tree.put(1) 
tree.put(6) 
tree.put(4) 
tree.put(7) 
tree.put(10) 
tree.put(14) 
tree.put(13) 
tree.remove(6) 
tree.printTree() 

Ich versuche es auf einem Papier zu zeichnen und sehen, vor allem, wie die while-Schleife arbeitet. Nach meinem obigen Code würde ich denken, dass es so ist:

child = self.left (Kind = 3) enkel = child.right = self, left.right = 6. Wenn Enkelkind (ja, 6) während Enkelkind.rechts (ja, 7) Kind = Enkelkind, 3 -> 6 Enkelkind = Kind.rechts (ist das überhaupt nötig, 6 ---> 6?) Self.data = Enkelkind. Daten (8 ---> 6) child.right = enkelkind.left (6 ----> 4) ??

Aber es kann nicht so sein, denn dann würde die While-Schleife nie enden. Gibt es jemanden, der mir helfen kann zu verstehen, wo ich mich selbst verliere?

Answer 1

Ich empfehle Ihnen, dieses Material aus Algorithmus Princeton: http://algs4.cs.princeton.edu/32bst/

Die Löschmethode diesem Ansatz wird mit einem Knoten von einem bst zu löschen.

Löschen. Wir können in ähnlicher Weise vorgehen, um einen Knoten zu löschen, der ein Kind (oder keine Kinder) hat, aber was können wir tun, um einen Knoten zu löschen, der zwei Kinder hat? Wir haben links zwei Links, aber haben einen Platz im Elternknoten für nur einen von ihnen. Eine Antwort auf dieses Dilemma, das 1962 von T. Hibbard vorgeschlagen wurde, lautet , einen Knoten x zu löschen, indem er durch seinen Nachfolger ersetzt. Da x ein rechtes Kind hat, ist sein Nachfolger der Knoten mit dem kleinsten Schlüssel in seinem rechten Teilbaum. Die Ersetzung behält die Reihenfolge in der Struktur bei, da zwischen x.key und dem Schlüssel des Nachfolgers keine Schlüssel vorhanden sind. Wir erreichen die Aufgabe, zu ersetzen x durch seine Nachfolger

in vier einfachen Schritten (!):

• Speichern Sie einen Link zu dem Knoten in t
• Set x zu seinem Nachfolger Punkt gelöscht werden min (t.rechts)
• Setzen Sie die rechte Verknüpfung von x (die auf die BST zeigen soll, die alle Schlüssel größer als x.key enthält) auf deleteMin (t.right), die Verbindung zur BST, die alle enthält die Schlüssel, die größer sind als x.key
  nach dem Löschen.
• Setzen Sie den linken Link von x (der null war) zu t.left (alle Schlüssel, die kleiner als der gelöschte Schlüssel und sein Nachfolger sind).