二分搜索树基本操作

插入操作

二分搜索树（Binary Search Tree, BST）是一种常见的数据结构，它的每个节点都包含一个关键字，并且对于任意非空子树中的所有节点，其左子树中节点的关键字均小于该节点的关键字，右子树中节点的关键字均大于该节点的关键字。插入操作是向二分搜索树中添加一个新节点的过程。

在进行插入之前，先从根节点开始查找合适的插入位置。具体步骤如下：

1. 选择根节点为当前节点。
2. 比较待插入值与当前节点的值：
   • 如果待插入值小于当前节点的值，则移动到左子树继续查找；
   • 如果待插入值大于或等于当前节点的值，则移动到右子树继续查找。
3. 重复步骤1和2，直到找到一个空位置作为新节点的父节点。
4. 将新的节点加入到二分搜索树中。

以下是一个简单的Python实现：

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

def insert(root, key):
    if root is None:
        return TreeNode(key)
    
    current = root
    while True:
        parent = current
        if key < current.key:
            current = current.left
            if current is None:
                parent.left = TreeNode(key)
                break
        else:
            current = current.right
            if current is None:
                parent.right = TreeNode(key)
                break

# 示例用法
root = None
keys = [8, 3, 10, 1, 6, 14, 4, 7, 13]
for key in keys:
    root = insert(root, key)

print("插入操作完成")

查找操作

查找操作是根据给定的关键字在二分搜索树中寻找对应节点的过程。基本思想是从根节点开始，逐步缩小范围直到找到目标节点或判断不存在该关键字。

具体步骤如下：

1. 选择根节点为当前节点。
2. 比较待查找值与当前节点的值：
   • 如果待查找值小于当前节点的值，则移动到左子树继续查找；
   • 如果待查找值大于或等于当前节点的值，则移动到右子树继续查找。
3. 重复步骤1和2，直到找到目标节点或者确定不存在该关键字。

以下是Python代码实现：

def search(root, key):
    current = root
    while current is not None:
        if key == current.key:
            return True
        elif key < current.key:
            current = current.left
        else:
            current = current.right
    return False

# 检查函数
print("查找节点10:", search(root, 10))  # 输出: 查找节点10: True
print("查找节点2:", search(root, 2))   # 输出: 查找节点2: False

删除操作

删除操作是移除二分搜索树中指定关键字所对应的节点的过程。此过程相对复杂，需要考虑不同的情况来保持树的性质。

基本步骤如下：

1. 根据待删除的关键字在二叉搜索树中定位目标节点。
2. 分三种情况进行处理：
   • 如果要删除的节点是叶子节点（没有子节点），则直接将其父节点指向空即可；
   • 如果要删除的节点有一个子节点，则将该节点的父节点指向其子节点；
   • 如果要删除的节点有两个子节点，可以选择用右子树最小值或左子树最大值替代目标节点的位置，并继续处理替代者。

以下是一个简单的Python实现：

def delete(root, key):
    def min_value_node(node):
        current = node
        while current.left is not None:
            current = current.left
        return current
    
    def max_value_node(node):
        current = node
        while current.right is not None:
            current = current.right
        return current
    
    def delete_node(root, key):
        if root is None:
            return root
        
        if key < root.key:
            root.left = delete_node(root.left, key)
        elif key > root.key:
            root.right = delete_node(root.right, key)
        else:
            # 要删除的节点是叶子节点
            if root.left is None and root.right is None:
                return None
            
            # 要删除的节点有一个子节点
            elif root.left is None:
                temp = root.right
                del root
                return temp
            
            elif root.right is None:
                temp = root.left
                del root
                return temp
            
            # 有两个子节点，用右子树最小值替代
            else:
                temp = min_value_node(root.right)
                root.key = temp.key
                root.right = delete_node(root.right, temp.key)
        
        return root
    
    root = delete_node(root, key)

# 示例删除操作
root = None  # 假设我们已经有了一个二分搜索树
delete(root, 10)  # 删除节点10

print("删除成功")

通过上述基本操作，可以有效地管理和使用二分搜索树来存储和检索数据。