實現二叉搜索樹處理重複鍵在Python

Question

下面是這個例子的網站，我發現幫助我學習Python好一點上給予代碼：Interactive Python

筆者解釋說：

我們實現插入的一個重要問題是重複鍵處理不當。在我們的樹被實現時，重複鍵將在具有原始鍵的節點的右子樹中創建具有相同鍵值的新節點。這樣做的結果是在搜索期間將不會找到具有新密鑰的節點。處理插入重複鍵的更好方法是與新鍵關聯的值替換舊值。 我們將修復這個bug作爲練習。「

我在這裏的問題是，我該如何解決這個問題，妥善處理重複鍵嗎？如果一個關鍵的樹已經存在，那麼新的有效載荷應該替換舊值。這樣做的目的是不加使用相同的密鑰，但我不知道其他節點在哪裏甚至開始這樣做。我不知道爲什麼會是這樣混亂。

class BinarySearchTree: 

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

    def length(self): 
     return self.size 

    def __len__(self): 
     return self.size 

    def __iter__(self): 
     return self.root.__iter__() 

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 

    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) 

Answer 1

的_put()方法執行測試和插入，並且它從來沒有測試的等於。它只測試插入的key是否較小（將密鑰插入l eft孩子），否則它會插入正確的孩子。

簡單地測試了平等和替換：

def _put(self,key,val,currentNode): 
    if key == currentNode.key: 
     currentNode.value = val 

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