带key和valu的Python二叉搜索树

Question

我需要实现一个二叉搜索树类作为家庭作业，但我很难使插入函数。我在Google上查了很多遍，想找到一些解决方案或者可能的方法，但是他们没有一个使用键和值（主要是值），或者如果他们也使用了一个键，他们有很多独立的功能，我想我是不允许这样做的。在

因此，预建只是为了：

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声明为“无”。在

但我现在该如何修复它以使insert函数正常工作呢？在

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

Answer 1

您没有指定，但是我猜这些键的作用是确定树中是否已经有一个特定的键，如果已经存在，则替换O(1)运行时复杂性中相关节点的值。在

因此，当您插入一个节点时，您将首先检查字典中的键（您将自己在__init__中初始化一个空字典）。如果你已经需要替换这个节点的值。否则，您将以与在任何BST中相同的方式添加新节点，并记住更新字典以将键映射到其节点。在

Answer 2

现在是早上5点，所以这可能是错误的，但是这里是：
键是我们排序的依据，值不有趣
您的insert函数应该如下所示：

^{1}$

你能从这里弄清楚吗？还是你想要更多的方向