Вставка и поиск в BST

Определение свойства BST

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

# Valid BST:
#       4
#      / \
#     2   6
#    / \ / \
#   1  3 5  7
# For node 4: left subtree {1,2,3} < 4 < right subtree {5,6,7}
# This holds recursively for EVERY node in the tree.
print('BST property: left < node < right at every level')

Рекурсивный поиск в BST

def search_bst(root, val):
    if not root:
        return None  # not found
    if root.val == val:
        return root  # found
    if val < root.val:
        return search_bst(root.left, val)
    else:
        return search_bst(root.right, val)

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

result = search_bst(root, 2)
print(result.val if result else 'Not found')  # 2
result = search_bst(root, 5)
print(result.val if result else 'Not found')  # Not found

Итеративный поиск в BST

def search_bst_iterative(root, val):
    curr = root
    while curr:
        if val == curr.val:
            return curr
        elif val < curr.val:
            curr = curr.left
        else:
            curr = curr.right
    return None  # not found

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

node = search_bst_iterative(root, 3)
print(node.val if node else 'Not found')  # 3
print(search_bst_iterative(root, 9))     # None

Рекурсивная вставка в BST

def insert_bst(root, val):
    if not root:
        return TreeNode(val)  # create new node here
    if val < root.val:
        root.left = insert_bst(root.left, val)
    elif val > root.val:
        root.right = insert_bst(root.right, val)
    # val == root.val: duplicate, do nothing (or handle as needed)
    return root

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root = insert_bst(root, 1)
root = insert_bst(root, 5)
# Tree is now: 4, left=2(left=1), right=7(left=5)
print(root.right.left.val)  # 5

Итеративная вставка в BST

def insert_bst_iterative(root, val):
    new_node = TreeNode(val)
    if not root:
        return new_node
    curr = root
    while True:
        if val < curr.val:
            if curr.left is None:
                curr.left = new_node
                break
            curr = curr.left
        else:  # val > curr.val
            if curr.right is None:
                curr.right = new_node
                break
            curr = curr.right
    return root

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root = insert_bst_iterative(root, 3)
print(root.left.right.val)  # 3

BST в худшем случае: вырожденные деревья

# Inserting 1, 2, 3, 4, 5 into a BST:
# 1
#  \
#   2
#    \
#     3
#      \
#       4
#        \
#         5
# This is a right-skewed tree: search is O(n) not O(log n)

root = None
for val in [1, 2, 3, 4, 5]:
    root = insert_bst(root, val)

# Verify the skew
node = root
depth = 0
while node:
    depth += 1
    node = node.right
print(f'Height: {depth}')  # 5 = O(n), not O(log n)

Поиск минимума и максимума

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

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

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.right = TreeNode(9)

print(find_min(root).val)  # 1
print(find_max(root).val)  # 9

Преемник и предшественник в порядке обхода

def inorder_successor(root, p):
    successor = None
    while root:
        if p.val < root.val:
            successor = root  # possible successor
            root = root.left
        else:
            root = root.right
    return successor

def inorder_predecessor(root, p):
    predecessor = None
    while root:
        if p.val > root.val:
            predecessor = root  # possible predecessor
            root = root.right
        else:
            root = root.left
    return predecessor

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
p = root.left  # node with val=2
print(inorder_successor(root, p).val)   # 3
print(inorder_predecessor(root, p).val) # 1

Анализ сложности поиска в BST

# Python's BST alternatives:
# 1. heapq - min/max heap, O(log n) push/pop
# 2. sortedcontainers.SortedList (third-party, often allowed)
# 3. Manual AVL or Red-Black (rarely required in interviews)

# When interviews say 'use a BST':
# - LeetCode: implement TreeNode-based solution
# - Real interview: mention sortedcontainers or Java TreeMap equivalent
# - O(log n) operations matter when you need ordered access

# For pure insert/lookup without ordering: use dict (O(1) average)
print('Use heap for priority, dict for lookup, BST for ordered range')

Вставка в BST: особые случаи

def insert_bst_no_duplicates(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_bst_no_duplicates(root.left, val)
    elif val > root.val:
        root.right = insert_bst_no_duplicates(root.right, val)
    # else: val == root.val -> duplicate, skip
    return root

# Test all edge cases:
root = None
root = insert_bst_no_duplicates(root, 5)  # empty tree
root = insert_bst_no_duplicates(root, 5)  # duplicate
root = insert_bst_no_duplicates(root, 3)
root = insert_bst_no_duplicates(root, 7)
print(root.val, root.left.val, root.right.val)  # 5 3 7

BST из отсортированного массива

def sorted_array_to_bst(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sorted_array_to_bst(nums[:mid])
    root.right = sorted_array_to_bst(nums[mid+1:])
    return root

nums = [-10, -3, 0, 5, 9]
root = sorted_array_to_bst(nums)
print(root.val)        # 0 (middle element)
print(root.left.val)   # -3
print(root.right.val)  # 9

Быстрая проверка

Итоги урока