Ошибка атрибута Python для дерева двоичного поиска

Question

Я создал дерево с: mytree [3] = "red" mytree [4] = "blue" mytree [6] = "yellow" mytree [2] = "at" , Но если я попытаюсь удалить корневой узел, 3, с помощью mytree.delete (3), я получаю AttributeError. Объект «TreeNode» не имеет атрибута «findSuccessor». Любая идея, почему это происходит?

class TreeNode: 
    def __init__(self,key,val,left=None,right=None,parent=None): 
     self.key = key 
     self.payload = val 
     self.leftChild = left 
     self.rightChild = right 
     self.parent = parent 

    def hasLeftChild(self): 
     return self.leftChild 

    def hasRightChild(self): 
     return self.rightChild 

    def isLeftChild(self): 
     return self.parent and self.parent.leftChild == self 

    def isRightChild(self): 
     return self.parent and self.parent.rightChild == self 

    def isRoot(self): 
     return not self.parent 

    def isLeaf(self): 
     return not (self.rightChild or self.leftChild) 

    def hasAnyChildren(self): 
     return self.rightChild or self.leftChild 

    def hasBothChildren(self): 
     return self.rightChild and self.leftChild 

    def replaceNodeData(self,key,value,lc,rc): 
     self.key = key 
     self.payload = value 
     self.leftChild = lc 
     self.rightChild = rc 
     if self.hasLeftChild(): 
      self.leftChild.parent = self 
     if self.hasRightChild(): 
      self.rightChild.parent = self 


class BinarySearchTree: 

    def __init__(self): 
     self.root = None 
     self.size = 0 

    def length(self): 
     return self.size 

    def __len__(self): 
     return self.size 

    def put(self,key,val): 
     if self.root: 
      self._put(key,val,self.root) 
     else: 
      self.root = TreeNode(key,val) 
     self.size = self.size + 1 

    def _put(self,key,val,currentNode): 
     if key < currentNode.key: 
      if currentNode.hasLeftChild(): 
       self._put(key,val,currentNode.leftChild) 
      else: 
       currentNode.leftChild = TreeNode(key,val,parent=currentNode) 
     else: 
      if currentNode.hasRightChild(): 
       self._put(key,val,currentNode.rightChild) 
      else: 
       currentNode.rightChild = TreeNode(key,val,parent=currentNode) 

    def __setitem__(self,k,v): 
     self.put(k,v) 

    def get(self,key): 
     if self.root: 
      res = self._get(key,self.root) 
      if res: 
       return res.payload 
      else: 
       return None 
     else: 
      return None 

    def _get(self,key,currentNode): 
     if not currentNode: 
      return None 
     elif currentNode.key == key: 
      return currentNode 
     elif key < currentNode.key: 
      return self._get(key,currentNode.leftChild) 
     else: 
      return self._get(key,currentNode.rightChild) 

    def __getitem__(self,key): 
     return self.get(key) 

    def __contains__(self,key): 
     if self._get(key,self.root): 
      return True 
     else: 
      return False 

    def delete(self,key): 
     if self.size > 1: 
      nodeToRemove = self._get(key,self.root) 
      if nodeToRemove: 
       self.remove(nodeToRemove) 
       self.size = self.size-1 
      else: 
       raise KeyError('Error, key not in tree') 
     elif self.size == 1 and self.root.key == key: 
      self.root = None 
      self.size = self.size - 1 
     else: 
      raise KeyError('Error, key not in tree') 

    def __delitem__(self,key): 
     self.delete(key) 

    def spliceOut(self): 
     if self.isLeaf(): 
      if self.isLeftChild(): 
       self.parent.leftChild = None 
      else: 
       self.parent.rightChild = None 
     elif self.hasAnyChildren(): 
      if self.hasLeftChild(): 
       if self.isLeftChild(): 
        self.parent.leftChild = self.leftChild 
       else: 
        self.parent.rightChild = self.leftChild 
        self.leftChild.parent = self.parent 
      else: 
       if self.isLeftChild(): 
        self.parent.leftChild = self.rightChild 
       else: 
        self.parent.rightChild = self.rightChild 
        self.rightChild.parent = self.parent 

    def findSuccessor(self): 
     succ = None 
     if self.hasRightChild(): 
      succ = self.rightChild.findMin() 
     else: 
      if self.parent: 
       if self.isLeftChild(): 
        succ = self.parent 
       else: 
        self.parent.rightChild = None 
        succ = self.parent.findSuccessor() 
        self.parent.rightChild = self 
     return succ 

    def findMin(self): 
     current = self 
     while current.hasLeftChild(): 
      current = current.leftChild 
     return current 

    def remove(self,currentNode): 
     if currentNode.isLeaf(): #leaf 
      if currentNode == currentNode.parent.leftChild: 
       currentNode.parent.leftChild = None 
      else: 
       currentNode.parent.rightChild = None 
     elif currentNode.hasBothChildren(): #interior 
      succ = currentNode.findSuccessor() 
      succ.spliceOut() 
      currentNode.key = succ.key 
      currentNode.payload = succ.payload 

     else: # this node has one child 
      if currentNode.hasLeftChild(): 
       if currentNode.isLeftChild(): 
        currentNode.leftChild.parent = currentNode.parent 
        currentNode.parent.leftChild = currentNode.leftChild 
       elif currentNode.isRightChild(): 
        currentNode.leftChild.parent = currentNode.parent 
        currentNode.parent.rightChild = currentNode.leftChild 
       else: 
        currentNode.replaceNodeData(currentNode.leftChild.key, 
            currentNode.leftChild.payload, 
            currentNode.leftChild.leftChild, 
            currentNode.leftChild.rightChild) 
      else: 
       if currentNode.isLeftChild(): 
        currentNode.rightChild.parent = currentNode.parent 
        currentNode.parent.leftChild = currentNode.rightChild 
       elif currentNode.isRightChild(): 
        currentNode.rightChild.parent = currentNode.parent 
        currentNode.parent.rightChild = currentNode.rightChild 
       else: 
        currentNode.replaceNodeData(currentNode.rightChild.key, 
            currentNode.rightChild.payload, 
            currentNode.rightChild.leftChild, 
            currentNode.rightChild.rightChild) 




mytree = BinarySearchTree() 
mytree[3]="red" 
mytree[4]="blue" 
mytree[6]="yellow" 
mytree[2]="at" 
mytree.delete(3) 

print(mytree[6]) 
print(mytree[2]) 

Answer 1

Вы звоните findSuccessor на примере TreeNode в BinarySearchTree.remove. Ваша реализация TreeNode не имеет метода findSuccessor, но ваш класс BinarySearchTree делает. Либо добавьте метод findSuccessor в TreeNode, либо отредактируйте свой метод remove для вызова метода findSuccessor на BinarySearchTree.

Добавление TreeNode:

class TreeNode: 

    # ...Omitted code 

    def findSuccessor(self): 
     succ = None 
     if self.hasRightChild(): 
      succ = self.rightChild.findMin() 
     else: 
      if self.parent: 
       if self.isLeftChild(): 
        succ = self.parent 
       else: 
        self.parent.rightChild = None 
        succ = self.parent.findSuccessor() 
        self.parent.rightChild = self 
     return succ 

    def findMin(self): 
     current = self 
     while current.hasLeftChild(): 
      current = current.leftChild 
     return current 

или, возможно, вы имели в виду для BinarySearchTree наследовать от TreeNode:

class BinarySearchTree(TreeNode): 
    # ...Omitted code... 

В этом случае вы можете просто заменить ссылки на TreeNode класса с BinarySearchTree ссылки.

class BinarySearchTree(TreeNode): 

    #### OMITTED CODE ##### 

    def put(self,key,val): 
     if self.root: 
      self._put(key,val,self.root) 
     else: 
      self.root = BinarySearchTree(key,val) ### switched TreeNode for BinarySearchTree 
     self.size = self.size + 1 

    def _put(self,key,val,currentNode): 
     if key < currentNode.key: 
      if currentNode.hasLeftChild(): 
       self._put(key,val,currentNode.leftChild) 
      else: 
       currentNode.leftChild = BinarySearchTree(key,val,parent=currentNode) ### switched TreeNode for BinarySearchTree 
     else: 
      if currentNode.hasRightChild(): 
       self._put(key,val,currentNode.rightChild) 
      else: 
       currentNode.rightChild = BinarySearchTree(key,val,parent=currentNode) ### switched TreeNode for BinarySearchTree 

    ########## Omitted Code ####### 

Любой из них будет работать. Я больше поклонник последнего.