python 二叉搜索树

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树结构，它的每个节点都包含一个键值，并且具备以下性质：

1. 左子树中的所有节点的键值小于根节点的键值。
2. 右子树中的所有节点的键值大于根节点的键值。
3. 左子树和右子树也分别为二叉搜索树。

通过这样的性质，二叉搜索树可以进行高效的查找、插入和删除操作。

在Python中，你可以使用类来实现二叉搜索树。下面是一个简单的示例：

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

class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = TreeNode(key)
        else:
            self._insert_recursive(self.root, key)

    def _insert_recursive(self, node, key):
        if key < node.key:
            if node.left is None:
                node.left = TreeNode(key)
            else:
                self._insert_recursive(node.left, key)
        else:
            if node.right is None:
                node.right = TreeNode(key)
            else:
                self._insert_recursive(node.right, key)

    def search(self, key):
        return self._search_recursive(self.root, key)

    def _search_recursive(self, node, key):
        if node is None or node.key == key:
            return node
        if key < node.key:
            return self._search_recursive(node.left, key)
        else:
            return self._search_recursive(node.right, key)

    def delete(self, key):
        self.root = self._delete_recursive(self.root, key)

    def _delete_recursive(self, node, key):
        if node is None:
            return node
        if key < node.key:
            node.left = self._delete_recursive(node.left, key)