Реализация бинарного дерева поиска для обработки дубликатов ключей в Python

Ниже приведен код из примера, приведенного на веб-сайте, который я нашел, чтобы помочь мне немного лучше изучить python: Interactive Python

Автор поясняет, что:

Одна важная проблема с нашей реализацией insert заключается в том, что дубликаты ключей не обрабатываются должным образом. Поскольку наше дерево реализовано, дубликат ключа создаст новый узел с тем же значением ключа в правом поддереве узла, имеющего исходный ключ. Результатом этого является то, что узел с новый ключ никогда не будет найден во время поиска. Лучшим способом обработки вставки дубликата ключа является замена старого значения значением, связанным с новым ключом. мы оставляем исправление этой ошибки в качестве упражнения для вас. "

Вот мой вопрос: как исправить это, чтобы правильно обрабатывать дубликаты ключей? Если ключ уже существует в дереве, то новая полезная нагрузка должна заменить старое значение. Цель состояла бы в том, чтобы не добавлять другой узел с тем же ключом, но я понятия не имею где даже начать это делать. Я не знаю, почему это так сбивает с толку.

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)
1 2
python binary-search-tree

1 ответ:

Метод _put() выполняет проверку и вставку, и онникогда не проверяет равенство . Он только проверяет, если вставленный key меньше (вставляя ключ в левый дочерний элемент), в противном случае он вставит в правый дочерний элемент.

Просто проверьте на равенство и замените: 

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