python二叉搜索树知识点

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，它的每个节点最多只有两个子节点，且左子节点的值小于等于父节点的值，右子节点的值大于等于父节点的值。这种特殊的结构使得二叉搜索树可以快速地进行查找、插入和删除操作。

Python中可以使用类来实现二叉搜索树，其中每个节点包含一个值、一个左子节点和一个右子节点。以下是一个简单的实现示例：

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

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

    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert(val, self.root)

    def _insert(self, val, node):
        if val < node.val:
            if not node.left:
                node.left = TreeNode(val)
            else:
                self._insert(val, node.left)
        else:
            if not node.right:
                node.right = TreeNode(val)
            else:
                self._insert(val, node.right)

    def search(self, val):
        return self._search(val, self.root)

    def _search(self, val, node):
        if not node:
            return False
        elif node.val == val:
            return True
        elif val < node.val:
            return self._search(val, node.left)
        else:
            return self._search(val, node.right)

    def delete(self, val):
        self.root = self._delete(val, self.root)

    def _delete(self, val, node):
        if not node:
            return None
        elif val < node.val:
            node.left = self._delete(val, node.left)
        elif val > node.val:
            node.right = self._delete(val, node.right)
        else:
            if not node.left:
                return node.right
            elif not node.right:
                return node.left
            else:
                min_node = self._find_min(node.right)
                node.val = min_node.val
                node.right = self._delete(min_node.val, node.right)
        return node

    def _find_min(self, node):
        while node.left:
            node = node.left
        return node

在上面的代码中，insert方法用于插入一个新节点，search方法用于查找一个节点，delete方法用于删除一个节点。其中，_insert、_search和_delete方法是递归实现的。