二分搜索树学习笔记

简介

二分搜索树（Binary Search Tree）是一种常用的数据结构，它是一棵空树或者具有下列性质的二叉树：

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 任意节点的左、右子树也分别为二叉查找树；
• 没有键值相等的节点。

实例

以下是一个简单的二分搜索树的实现，并演示了如何对其进行插入、查询和删除操作。

pythonCopy Code
class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None


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

    def _insert(self, node, key, value):
        if not node:
            return Node(key, value)
        if key == node.key:
            node.value = value
        elif key < node.key:
            node.left = self._insert(node.left, key, value)
        else:
            node.right = self._insert(node.right, key, value)
        return node

    def insert(self, key, value):
        self.root = self._insert(self.root, key, value)

    def _search(self, node, key):
        if not node:
            return None
        if key == node.key:
            return node.value
        elif key < node.key:
            return self._search(node.left, key)
        else:
            return self._search(node.right, key)

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

    def _delete(self, node, key):
        if not node:
            return None

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

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

    def _find_min(self, node):
        if not node.left:
            return node
        else:
            return self._find_min(node.left)

接下来演示如何使用该二分搜索树：

pythonCopy Code
bst = BST()
bst.insert(3, "apple")
bst.insert(1, "banana")
bst.insert(2, "orange")

# 查询键为 1 的值
print(bst.search(1))  # 输出 "banana"

# 删除键为 2 的节点
bst.delete(2)

# 查询键为 2 的值（已经被删除，输出 None）
print(bst.search(2))  # 输出 None