Binary Seach дерево, удалить узел, нужна помощь здесь (перепроведении)

Question

Мой код выглядит так:

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) 

Все о моем коде работает, и я просто добавил (см скопирована) метод удаления и метод удаления. Im отчаянно пытается понять метод удаления, но я не могу его понять. Я использую этот код для запуска вещи и посмотреть, как реализуется дерево:

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() 

Я пытаюсь нарисовать его на бумаге и увидеть, особенно, как в то время как контур работает. Согласно моему приведенному выше коду, я бы подумал, что это так:

child = self.left (child = 3) grandchild = child.right = self, left.right = 6. Если внук (да, 6), в то время как grandchild.right (да, 7) ребенок = внук, 3 -> 6 grandchild = child.right (это даже нужно, 6 ---> 6?) Self.data = grandchild. данные (8 ---> 6) child.right = grandchild.left (6 ----> 4) ??

Но это не может быть так, потому что тогда цикл while никогда не кончится. Есть ли кто-нибудь, кто может помочь мне понять, где я потерял себя?

Answer 1

Я рекомендую вам этот материал из алгоритма Принстон: http://algs4.cs.princeton.edu/32bst/

Функция удаления метод использует этот подход, чтобы удалить узел из BST.

Удалить. Мы можем действовать аналогичным образом, чтобы удалить любой узел с одним ребенком (или без детей), но что мы можем сделать, чтобы удалить узел, в котором имеет двух детей? Мы остаемся с двумя ссылками, но имеем место в родительском узле только для одного из них. Ответ на эту дилемму, первый , предложенный Т. Хибардом в 1962 году, заключается в удалении узла x путем его замены его . Поскольку x имеет правильный дочерний элемент, его преемником является узел с наименьшим ключом в его правом поддереве. Замена сохраняет заказ в дереве, потому что между x.key и ключем преемника нет ключей. Мы выполняем задачу заменяющего х его преемником

в четыре простых шага (!):

• Сохранить ссылку на узел будет удален в т
• Set х, чтобы указать на его преемника min (t.right)
• Установите правильную ссылку x (которая должна указывать на BST, содержащую все ключи, большие, чем x.key), чтобы удалить Min (t.right), ссылку на BST, содержащую все ключи, которые больше, чем x.key
  после удаления.
• Установите левую ссылку x (которая была равна null) на t.left (все ключи, которые меньше, чем удаленный ключ и его преемник).