具有键和值的 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.right"没有这样的属性等错误......我想这是有道理的，因为self.root被声明为None。

但是我现在如何实际修复它以使插入功能正常工作？

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

Answer 1

早上 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)

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

Answer 2

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

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