การลบใน BST: สามกรณี

เหตุใดการลบใน BST จึงซับซ้อน

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

# Three cases for deleting a node:
# Case 1: Leaf node (no children) -> simply remove it
# Case 2: One child -> replace node with its child
# Case 3: Two children -> replace value with in-order successor
#          then delete the in-order successor
print('BST delete: 3 cases based on number of children')

กรณีที่ 1: การลบโหนดใบ

def find_min(node):
    while node.left:
        node = node.left
    return node

# Demonstrating leaf deletion:
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(1)  # leaf
root.left.right = TreeNode(4)  # leaf

# To delete node 1 (leaf): set root.left.left = None
root.left.left = None
print(root.left.left)  # None -- deleted
print(root.left.val)   # 3 still intact

กรณีที่ 2: โหนดที่มีโหนดลูกหนึ่งโหนด

# Demonstrating one-child deletion:
# Tree:  5
#       / \
#      3   7
#       \   
#        4  
# Delete node 3 (has only right child 4):
# Result: 5
#        / \
#       4   7

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.right = TreeNode(4)

# In the recursive implementation:
# When we reach node 3 and it has no left child,
# we return root.right (node 4) to the parent.
# Parent sets its left pointer to 4, skipping 3.
print('One-child case: return the surviving child')

กรณีที่ 3: โหนดที่มีโหนดลูกสองโหนด

# Demonstrating two-child deletion:
# Tree:  5
#       / \
#      3   7
#         / \
#        6   9
# Delete node 5 (two children 3 and 7):
# In-order successor = 6 (smallest in right subtree)
# Step 1: replace 5's value with 6
# Step 2: delete 6 from right subtree
# Result:  6
#         / \
#        3   7
#             \
#              9
print('Two-child case: replace with in-order successor')

การใช้งานการลบ BST ฉบับสมบูรณ์

def delete_node(root, key):
    if not root:
        return None  # key not found
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:  # found the node to delete
        if not root.left:   # Case 1 or 2: no left child
            return root.right
        if not root.right:  # Case 2: no right child
            return root.left
        # Case 3: two children -> find in-order successor
        successor = find_min(root.right)
        root.val = successor.val  # copy successor value up
        root.right = delete_node(root.right, successor.val)  # delete successor
    return root

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
root = delete_node(root, 5)
print(root.val)  # 6 (successor replaced 5)

เหตุใดจึงใช้โหนดถัดไปตามลำดับอินออร์เดอร์

# Both approaches are valid for two-child deletion:

# Option A: Replace with in-order SUCCESSOR (min of right subtree)
# - Successor goes to current position
# - Delete successor from right subtree

# Option B: Replace with in-order PREDECESSOR (max of left subtree)
# - Predecessor goes to current position
# - Delete predecessor from left subtree

def find_max(node):
    while node.right:
        node = node.right
    return node

# Using predecessor:
def delete_node_pred(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = delete_node_pred(root.left, key)
    elif key > root.val:
        root.right = delete_node_pred(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        pred = find_max(root.left)
        root.val = pred.val
        root.left = delete_node_pred(root.left, pred.val)
    return root

print('Both successor and predecessor deletion are correct')

ลบโหนดทั้งหมดที่มีค่าเดียวกัน

# Delete all nodes with values outside [low, high]
def trim_bst(root, low, high):
    if not root:
        return None
    if root.val < low:
        # Entire left subtree is also < low, skip to right
        return trim_bst(root.right, low, high)
    if root.val > high:
        # Entire right subtree is also > high, skip to left
        return trim_bst(root.left, low, high)
    # Current node is within range
    root.left = trim_bst(root.left, low, high)
    root.right = trim_bst(root.right, low, high)
    return root

root = TreeNode(3)
root.left = TreeNode(0)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
root.left.right.left = TreeNode(1)
root = trim_bst(root, 1, 3)
print(root.val, root.left.val)  # 3 2

รูปแบบตัววนซ้ำ BST

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self):
        node = self.stack.pop()
        if node.right:
            self._push_left(node.right)
        return node.val

    def has_next(self):
        return bool(self.stack)

root = TreeNode(7)
root.left = TreeNode(3)
root.right = TreeNode(15)
root.right.left = TreeNode(9)
it = BSTIterator(root)
while it.has_next():
    print(it.next(), end=' ')  # 3 7 9 15

การลบโหนด: การวิเคราะห์ความซับซ้อน

# Complexity summary for BST operations:
# Operation | Balanced  | Skewed
# ----------|-----------|-------
# Search    | O(log n)  | O(n)
# Insert    | O(log n)  | O(n)
# Delete    | O(log n)  | O(n)
# Min/Max   | O(log n)  | O(n)
# In-order  | O(n)      | O(n)   (visits all nodes)

# The key: BST guarantees these complexities only when balanced.
# Python standard library has no balanced BST.
# Use sortedcontainers.SortedList for O(log n) ops in practice.
print('All BST core ops are O(h): O(log n) balanced, O(n) skewed')

ผลรวมสองค่าใน BST

def find_target_bst(root, k):
    seen = set()
    def inorder(node):
        if not node:
            return False
        if inorder(node.left):
            return True
        if k - node.val in seen:
            return True
        seen.add(node.val)
        return inorder(node.right)
    return inorder(root)

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.right.right = TreeNode(7)
print(find_target_bst(root, 9))  # True (2+7)
print(find_target_bst(root, 28)) # False

แปลง BST เป็นต้นไม้ผลรวมค่าที่มากกว่า

def bst_to_gst(root):
    acc = [0]  # running accumulated sum

    def reverse_inorder(node):
        if not node:
            return
        reverse_inorder(node.right)   # visit larger values first
        acc[0] += node.val
        node.val = acc[0]             # replace with cumulative sum
        reverse_inorder(node.left)

    reverse_inorder(root)
    return root

root = TreeNode(4)
root.left = TreeNode(1)
root.right = TreeNode(6)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
bst_to_gst(root)
print(root.val)       # 4+5+6+7 = 22
print(root.right.val) # 5+6+7 = 18

ตรวจสอบความเข้าใจอย่างรวดเร็ว

ทบทวนบทเรียน