Удаление из BST: три случая
Обрабатывайте удаление листа, удаление узла с одним потомком и удаление узла с двумя потомками с помощью следующего узла при симметричном обходе, реализуя алгоритм с нуля
«Удаление из BST: три случая» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Почему удаление из BST — сложная задача
Удаление из 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: удаление листа
Лист не имеет потомков. Удаление просто: верните None из рекурсивного вызова, после чего родитель установит свой указатель (левый или правый) в пустое значение. Это базовый случай, который должны обрабатывать все реализации удаления из BST. Убедитесь, что решение работает и в особом случае, когда дерево состоит только из одного узла, а корень является листом.
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: узел с двумя потомками
Если у узла два потомка, его нельзя просто удалить. Вместо этого найдите преемника при симметричном обходе (наименьшее значение в правом поддереве), скопируйте его значение в текущий узел, а затем удалите преемника при симметричном обходе из правого поддерева. У преемника не более одного потомка (левого потомка нет), поэтому его удаление сводится к случаю 1 или случаю 2 — с ними мы уже умеем работать.
# 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
Полная рекурсивная функция удаления объединяет все три случая. Найдите удаляемый узел, сравнивая значения, а затем обработайте соответствующий случай. Шаблон, в котором на каждом уровне возвращается (возможно, изменённый) корень и результат присваивается обратно в root.left или root.right, элегантно обрабатывает все обновления указателей без явного отслеживания родителя. Временная сложность — O(h).
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)Почему используется преемник при симметричном обходе
Преемник при симметричном обходе (минимум правого поддерева) используется вместо максимума левого поддерева, потому что оба варианта допустимы — любой из них сохраняет свойство BST. Также подходит предшественник при симметричном обходе (максимум левого поддерева). В некоторых реализациях эти варианты чередуются, чтобы сохранять сбалансированность дерева. На собеседованиях чаще ожидают вариант с преемником при симметричном обходе; упомяните, что предшественник работает столь же хорошо.
# 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')Удаление всех узлов с заданным значением
В одной из вариаций задачи требуется удалить все узлы со значениями из диапазона или соответствующие условию. Для BST это эффективно: рекурсивно переходите в подходящее поддерево на основе сравнений и применяйте операцию удаления везде, где выполняется условие. Рекурсивная структура удаления из BST естественным образом распространяется на такие сценарии без отдельного прохода по дереву.
# 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
Итератор BST (LeetCode #173) возвращает элементы в отсортированном порядке по одному, со средним временем O(1) и пространством O(h). Реализуйте его с помощью стека, имитирующего итеративный симметричный обход: при создании поместите в стек все левые узлы, начиная с корня. При вызове next() извлеките верхний узел и поместите в стек все левые узлы правого поддерева. Это управляемое разворачивание итеративного алгоритма симметричного обхода.
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Удаление узла: анализ сложности
Удаление из BST выполняется за O(h), где h — высота дерева. Для сбалансированного BST это O(log n). Для вырожденного дерева сложность ухудшается до O(n). Поиск преемника при симметричном обходе добавляет не более одного дополнительного прохода по правому поддереву за O(h), что не меняет общей сложности. Пространственная сложность рекурсивной реализации составляет O(h) из-за стека вызовов.
# 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
Поиск двух слагаемых IV в BST требует определить, существуют ли два узла, сумма которых равна заданному значению. Один из подходов использует множество: при симметричном обходе сохраняйте значения и проверяйте, существует ли target - current среди уже обработанных. Более элегантный подход одновременно использует итератор BST, движущийся вперёд, и итератор BST, движущийся назад (подобно двум указателям). Это позволяет обойтись без дополнительной памяти сверх O(h) для стека каждого итератора.
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 в дерево сумм больших значений
Дерево сумм больших значений (LeetCode #538) заменяет значение каждого узла суммой всех значений, больших или равных ему, в BST. Ключевая идея: выполнить обратный симметричный обход (право → корень → лево), чтобы посещать узлы в порядке убывания и накапливать текущую сумму. Алгоритм выполняется за O(n) времени и использует O(h) памяти.
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Быстрая проверка
Проверьте понимание понятий «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке Вы узнали: три случая удаления из BST (лист, один потомок, два потомка), метод поиска преемника при симметричном обходе для удаления узла с двумя потомками и аккуратные рекурсивные шаблоны, такие как итератор BST и дерево сумм больших значений на основе BST. Далее мы проверим корректность BST и используем свойства симметричного обхода.
Часто задаваемые вопросы
Урок «Удаление из BST: три случая» бесплатный?
Да — полный текст урока «Удаление из BST: три случая» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Удаление из BST: три случая»?
Обрабатывайте удаление листа, удаление узла с одним потомком и удаление узла с двумя потомками с помощью следующего узла при симметричном обходе, реализуя алгоритм с нуля Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Удаление из BST: три случая»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Вставка и поиск в BST
- Удаление из BST: три случая
- Проверка BST и свойств симметричного обхода
- k-й наименьший элемент, сумма диапазона и преобразование BST в отсортированный массив