BST 插入与查找
递归和迭代实现插入与查找，跟踪不同键在树中的路径，并分析非平衡树的最坏情况复杂度。
BST 插入与查找 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
BST 性质定义
二叉搜索树满足一个不变量：对于每个节点，其左子树中的所有值都严格小于该节点的值，而其右子树中的所有值都严格大于该节点的值。这种排序性质会在整个子树范围内保持，而不仅仅适用于直接子节点；它使平衡树能够以 O(log n) 的复杂度完成搜索、插入和删除，也使 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 搜索
BST 搜索的工作方式类似于二分搜索：将目标值与当前节点的值进行比较，然后递归进入相应的子树。如果目标值等于当前值，则返回该节点。如果目标值更小，则向左走；如果更大，则向右走。如果到达空节点，则返回空值。时间复杂度为 O(h)：平衡树为 O(log n)，倾斜树为 O(n)。
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 搜索
迭代搜索可以避免调用栈开销，因此在生产代码中更受欢迎。使用指针 curr 沿树向下移动，并根据比较结果选择左侧或右侧。这是一个简单的 while 循环，包含三种情况：空值（未找到）、匹配（找到）或调整方向。迭代搜索的时间复杂度同样为 O(h)，但空间复杂度为 O(1)，而递归版本为 O(h)。
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 插入
BST 插入通过执行与搜索相同的左右判断来找到正确位置，然后将新节点连接到遇到的第一个 null 位置。递归方法会返回每个子树的（可能是新节点的）根：如果当前节点为空，则返回一个新的 TreeNode；否则，使用递归调用的结果更新 root.left 或 root.right。这种模式清晰明了，在面试解法中也很常见。
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 插入
迭代插入使用 parent 指针跟踪到达插入位置前最后一个非空节点。像搜索一样向下遍历树，同时记录父节点以及上一次移动的方向。到达空值后，将新节点连接到父节点相应的一侧。请始终单独处理空树这一边界情况（根节点为空）。
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：倾斜树
如果将有序序列插入 BST，就会得到一棵退化成链表的倾斜树。搜索、插入和删除的时间复杂度都会变为 O(n)。这就是平衡 BST（AVL 树、红黑树）存在的原因。在面试中，当被问到 BST 的复杂度时，请始终提及这种最坏情况——说明“平衡性不足的树平均为 O(log n)，最坏为 O(n)”能够体现您理解得很深入。
# 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)查找最小值和最大值
在 BST 中，最小值始终位于最左侧的节点（不断向左走，直到遇到空值），而最大值位于最右侧的节点。这些时间复杂度为 O(h) 的操作经常作为 BST 删除（查找中序后继）和范围查询的子程序使用。熟练掌握这些辅助函数可以节省面试时间。
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中序后继与前驱
节点的中序后继是所有大于该节点的值中最小的那个节点。如果该节点有右子树，则后继是 find_min(node.right)。如果没有右子树，则后继是这样一个最低祖先：给定节点位于该祖先的左子树中。理解这一点对于 BST 删除和 BST 迭代器问题至关重要。
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) # 1BST 搜索复杂度分析
BST 的性能完全取决于树高。对于包含 n 个节点的平衡 BST，树高为 O(log n)，因此搜索、插入和删除的复杂度均为 O(log n)。对于倾斜 BST，树高为 O(n)，所有操作的复杂度也都是 O(n)。Python 没有内置的平衡 BST（不同于 Java 的 TreeMap），因此您可以自行实现 AVL 树或红黑树，使用 sortedcontainers.SortedList，或者在优先队列使用场景中依赖堆。
# 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：边界情况
请始终确认插入操作能够处理：空树（将新节点作为根返回）、重复值（明确是忽略、插入左侧还是插入右侧，并保持一致），以及非常大或非常小的值。在面试中，请在编码前说明您对重复值的假设。LeetCode 问题中最常见的约定是：除非另有说明，否则所有值都不重复。
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
从有序数组构建高度平衡的 BST（LeetCode #108）使用分治法：中间元素成为根节点，左半部分成为左子树，右半部分成为右子树。这样可以保证树保持平衡，树高为 O(log n)。时间复杂度为 O(n)，因为每个元素只处理一次。
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快速检查
请测试您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学习了：BST 性质（左子树严格更小，右子树严格更大）、在 O(h) 时间内以递归和迭代方式进行搜索与插入，以及树高等于 n 的最坏情况倾斜树。接下来我们将学习 BST 删除及其三种情况。
常见问题解答
「BST 插入与查找」课时是免费的吗？
是的 — 「BST 插入与查找」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「BST 插入与查找」这节课中我会学到什么？
递归和迭代实现插入与查找，跟踪不同键在树中的路径，并分析非平衡树的最坏情况复杂度。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「BST 插入与查找」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。