Python 数据结构：二叉搜索树（BST）删除操作

# /*
# Python 数据结构：二叉搜索树（BST）删除操作
# --------------------------------------------------------
# 概念：
# 删除操作分三种情况：
# 1) 删除叶子节点：直接删除即可
# 2) 删除只有一个子节点的节点：用子节点替代
# 3) 删除有两个子节点的节点：用右子树最小值（或左子树最大值）替代，然后删除替代节点
# */

# ========================================================
# BST 节点定义
# ========================================================
class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# ========================================================
# BST 操作类（插入 + 查找 + 删除）
# ========================================================
class BST:
    def __init__(self):
        self.root = None

    # 插入节点
    def insert(self, data):
        self.root = self._insert_recursive(self.root, data)

    def _insert_recursive(self, node, data):
        if node is None:
            return BSTNode(data)
        if data < node.data:
            node.left = self._insert_recursive(node.left, data)
        elif data > node.data:
            node.right = self._insert_recursive(node.right, data)
        return node

    # 查找节点
    def search(self, target):
        return self._search_recursive(self.root, target)

    def _search_recursive(self, node, target):
        if node is None:
            return False
        if target == node.data:
            return True
        elif target < node.data:
            return self._search_recursive(node.left, target)
        else:
            return self._search_recursive(node.right, target)

    # 删除节点
    def delete(self, key):
        self.root = self._delete_recursive(self.root, key)

    def _delete_recursive(self, node, key):
        if node is None:
            return None

        if key < node.data:
            node.left = self._delete_recursive(node.left, key)
        elif key > node.data:
            node.right = self._delete_recursive(node.right, key)
        else:
            # 找到节点，执行删除
            # 情况1：叶子节点或只有一个子节点
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            # 情况2：有两个子节点
            min_larger_node = self._find_min(node.right)
            node.data = min_larger_node.data
            node.right = self._delete_recursive(node.right, min_larger_node.data)
        return node

    # 找右子树最小节点
    def _find_min(self, node):
        while node.left:
            node = node.left
        return node

    # 中序遍历（升序）
    def inorder_traversal(self, node=None):
        if node is None:
            node = self.root
        result = []
        def _inorder(n):
            if n:
                _inorder(n.left)
                result.append(n.data)
                _inorder(n.right)
        _inorder(node)
        return result

# ========================================================
# 示例演示
# ========================================================
bst = BST()
for value in [50, 30, 70, 20, 40, 60, 80]:
    bst.insert(value)

print("初始中序遍历：", bst.inorder_traversal())

# 删除叶子节点
bst.delete(20)
print("删除叶子节点 20 后：", bst.inorder_traversal())

# 删除只有一个子节点的节点
bst.delete(30)
print("删除节点 30（只有一个子节点）后：", bst.inorder_traversal())

# 删除有两个子节点的节点
bst.delete(50)
print("删除节点 50（有两个子节点）后：", bst.inorder_traversal())

# ========================================================
# 要点总结：
# --------------------------------------------------------
# 1) BST 删除根据节点情况分三类：叶子、单子节点、双子节点；
# 2) 双子节点删除可用右子树最小节点替代或左子树最大节点替代；
# 3) 删除操作保持 BST 特性不变；
# 4) 时间复杂度平均为 O(log n)，最坏为 O(n)；
# 5) 删除后可通过中序遍历验证 BST 正确性。
# */
#
# 初始中序遍历：
# [20, 30, 40, 50, 60, 70, 80]
# 删除叶子节点 20 后：
# [30, 40, 50, 60, 70, 80]
# 删除节点 30（只有一个子节点）后：
# [40, 50, 60, 70, 80]
# 删除节点 50（有两个子节点）后：
# [40, 60, 70, 80]