python - 创建 BST : python 的最佳实践

Question

因此，我正在实现一个二叉搜索树，但对于我是否应该有一个 Node 类 以及一个 Bst 类 还是只有一个类感到困惑。

原因是因为我知道 BST 是由节点组成的，但在任何时候你都可以使用一个节点和它下面的所有节点，这本质上也是一个 BST。

如果我有以下代码，那么我在插入时可以像这样调用我的代码 self.left.insert(data)

class Bst():
def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None

def insert(self, data):
    node_to_insert = Bst(data)
    if data < self.data:
        if self.left is None:
            self.left = Bst(data)
        else:
            self.left.insert(data)
    else:
        if self.right is None:
            self.right = Bst(data)
        else:
            self.right.insert(data)

如果我用另一种方式做，它们是两个独立的东西 Node 和 BST 那么在我的插入方法中我有 self.insert(data , 节点.left):

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

class Bst():
    def __init__(self, root=None):
        self.root = root

    def insert(self, data, node):
        node_to_insert = Node(data)

        if node is None:
            node = node_to_insert
        else:
            if data < node.data:
                if node.left is None:
                    node.left = node_to_insert
                else:
                    self.insert(data, node.left)
            else:
                if node.right is None:
                    node.right = node_to_insert
                else:
                    self.insert(data, node.right)

所以我的问题是 self.insert(data, node.left) 或 self.left.insert(data) 哪个更好。

我假设 self.left.insert(data) 当用户插入时他们只需要写 bst.insert(5)他们说的一个 bst.insert(bst.root, 5)

Answer 1

我认为第二个更好。算法与数据结构分离，带来更大的灵 active 。例如涉及父节点的删除操作，第二种比第一种更容易实现。