带有键和值的Python二叉搜索树

Question

我需要实现一个Binary Search Tree类作为家庭作业，但我很难实现insert函数。我在谷歌搜索了很多，想找到一些解决方案或可能的方法，但他们都没有使用过键和值（大多只是值），或者如果他们也使用了键，他们有很多单独的功能，我想这是不允许的。

因此，预构建的只是：

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = self.right = None

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

    def __len__(self):
        return self.size

    def insert(self, key, value):
        pass

    def remove(self, key):
        pass

    def find(self, key):
        pass

现在的问题是，如果我想检查例如值是否小于或大于当前节点以将其放在右侧或左侧，我会收到诸如“root未定义”或“root.right”之类的错误，因此没有这样的属性等...我想这是有道理的，因为 self.root 被声明为“无”。

但我现在如何实际修复它以使insert函数工作呢？

我对这个任务有点困惑，因为它使用键值，所以我需要插入绑定到特定键的值，如果键已经存在，请覆盖其值。

Answer 1

您没有指定，但我猜键的目的是确定特定的键是否已经在树中，如果是，则在< code>O(1)运行时复杂性中替换相关节点的值。

因此，当您插入节点时，您将首先检查字典中的键（您将在__init__中自己初始化一个空字典）。如果它已经存在，那么您只需为该特定键替换节点的值。否则，您将像在任何BST中一样添加新节点，并记住更新字典以将键映射到它的节点。

Answer 2

早上5点，所以这可能是错误的，但这里有：
关键是我们要排序的内容，值不有趣
您的插入函数可能如下所示：

def insert(self, key, value):
        if self.root = None:
            self.root = Node(key,value)
            return
        #regular binary tree traversal (comparing the key) to find where to insert, lets assume we need to insert on the left
        parent.left = Node(key,value)

你能从这里弄清楚吗，或者你想要更多的方向