Usuwanie z BST: trzy przypadki
Obsłużą Państwo usuwanie liścia, węzła z jednym dzieckiem i węzła z dwojgiem dzieci, korzystając z następnika inorder i implementując algorytm od podstaw.
Usuwanie z BST: trzy przypadki to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Dlaczego usuwanie z BST jest trudne
Usuwanie z BST jest najbardziej złożoną z trzech podstawowych operacji, ponieważ usunięcie węzła musi zachować własność BST w całym drzewie. Istnieją trzy odrębne przypadki, zależne od dzieci danego węzła: węzeł nie ma dzieci (jest liściem), ma jedno dziecko albo ma dwoje dzieci. Każdy przypadek wymaga innej strategii. Rekruterzy lubią ten problem, ponieważ sprawdza on manipulowanie wskaźnikami, rozumowanie o przypadkach brzegowych oraz znajomość pojęcia następnika w porządku inorder.
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')Przypadek 1: usuwanie liścia
Liść nie ma dzieci. Usunięcie jest proste: należy zwrócić None z wywołania rekurencyjnego, co powoduje, że rodzic ustawia swój wskaźnik (lewy lub prawy) na null. Jest to przypadek bazowy, który musi obsługiwać każda implementacja usuwania z BST. Należy sprawdzić, czy działa również szczególny przypadek drzewa zawierającego tylko jeden węzeł, w którym root jest liściem.
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 intactPrzypadek 2: węzeł z jednym dzieckiem
Jeśli węzeł ma dokładnie jedno dziecko, należy zastąpić węzeł tym dzieckiem. Należy zwrócić dziecko inne niż null z wywołania rekurencyjnego, aby wskaźnik rodzica został zaktualizowany i pomijał usunięty węzeł. Działa to niezależnie od tego, czy jedyne dziecko znajduje się po lewej, czy po prawej stronie — wystarczy zwrócić to, które istnieje.
# 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')Przypadek 3: węzeł z dwojgiem dzieci
Jeśli węzeł ma dwoje dzieci, nie można go po prostu usunąć. Zamiast tego należy znaleźć następnika inorder tego węzła (najmniejszą wartość w prawym poddrzewie), skopiować jego wartość do bieżącego węzła, a następnie usunąć następnika inorder z prawego poddrzewa. Następnik ma co najwyżej jedno dziecko (nie ma lewego dziecka), więc jego usunięcie sprowadza się do przypadku 1 lub 2 — a te przypadki są już znane.
# 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')Pełna implementacja usuwania z BST
Pełna rekurencyjna implementacja usuwania uwzględnia wszystkie trzy przypadki. Należy znaleźć węzeł do usunięcia, porównując wartości, a następnie obsłużyć odpowiedni przypadek. Wzorzec polegający na zwracaniu (możliwie zmodyfikowanego) korzenia na każdym poziomie i przypisywaniu go z powrotem do root.left lub root.right elegancko obsługuje wszystkie aktualizacje wskaźników bez jawnego śledzenia rodzica. Złożoność czasowa wynosi 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)Dlaczego następnik inorder?
Następnik inorder (minimum prawego poddrzewa) jest używany zamiast maksimum lewego poddrzewa, ponieważ obie możliwości są poprawne — użycie dowolnej z nich zachowuje własność BST. Działa również poprzednik inorder (maksimum lewego poddrzewa). Niektóre implementacje stosują te możliwości naprzemiennie, aby utrzymać równowagę drzewa. Na rozmowach kwalifikacyjnych częściej oczekuje się wersji z następnikiem inorder; warto wspomnieć, że poprzednik działa równie dobrze.
# 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')Usuwanie wszystkich węzłów o danej wartości
W pewnym wariancie zadania należy usunąć wszystkie węzły, których wartości należą do określonego zakresu lub spełniają dany warunek. W przypadku BST jest to wydajne: na podstawie porównań należy przechodzić rekurencyjnie do odpowiedniego poddrzewa i wykonywać operację usuwania wszędzie tam, gdzie warunek jest spełniony. Rekurencyjna struktura usuwania z BST naturalnie rozszerza się na takie scenariusze i nie wymaga osobnego przejścia po drzewie.
# 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 2Wzorzec iteratora BST
Iterator BST (LeetCode #173) zwraca elementy w kolejności posortowanej, po jednym, ze średnią złożonością czasową O(1) i złożonością pamięciową O(h). Należy zaimplementować go za pomocą stosu symulującego iteracyjne przejście inorder: podczas tworzenia należy odłożyć na stos wszystkie lewe węzły, zaczynając od korzenia. Przy wywołaniu next() należy zdjąć element ze szczytu stosu, a następnie odłożyć na stos wszystkie lewe węzły prawego poddrzewa. Jest to kontrolowane rozwinięcie iteracyjnego algorytmu przejścia inorder.
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 15Analiza złożoności usuwania węzła
Usuwanie z BST wykonuje się w czasie O(h), gdzie h oznacza wysokość drzewa. W przypadku zrównoważonego BST jest to O(log n). W przypadku drzewa o strukturze łańcucha złożoność pogarsza się do O(n). Znalezienie następnika inorder wymaga co najwyżej jednego dodatkowego przejścia o złożoności O(h) po prawym poddrzewie, co nie zmienia ogólnej złożoności. Złożoność pamięciowa rekurencyjnej implementacji wynosi O(h) ze względu na stos wywołań.
# 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')Two Sum w BST
Two Sum IV w BST polega na sprawdzeniu, czy suma wartości dowolnych dwóch węzłów jest równa wartości docelowej. Jedno z podejść korzysta ze zbioru: podczas przejścia inorder zbiera wartości i sprawdza, czy target - current znajduje się już w zbiorze. Bardziej eleganckie podejście jednocześnie korzysta z iteratora BST przechodzącego do przodu i iteratora BST przechodzącego wstecz (jak z dwóch wskaźników) — pozwala to uniknąć dodatkowej przestrzeni poza O(h) na stos każdego iteratora.
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)) # FalseKonwersja BST do drzewa sum większych wartości
Drzewo sum większych wartości (LeetCode #538) zastępuje wartość każdego węzła sumą wszystkich wartości większych lub równych tej wartości w BST. Kluczowa obserwacja jest następująca: należy wykonać odwrotne przejście inorder (prawe poddrzewo → korzeń → lewe poddrzewo), aby odwiedzać węzły w kolejności malejącej i gromadzić bieżącą sumę. Złożoność czasowa wynosi O(n), a pamięciowa 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 = 18Sprawdzenie wiedzy
Proszę sprawdzić, czy rozumieją Państwo pojęcia z lekcji Data Structures & Algorithms — Coding Interview Prep.
Podsumowanie lekcji
W tej lekcji poznali Państwo: trzy przypadki usuwania z BST (liść, jedno dziecko, dwoje dzieci), technikę następnika inorder przy usuwaniu węzła z dwojgiem dzieci oraz przejrzyste wzorce rekurencyjne, takie jak iterator BST i konwersja BST do drzewa sum większych wartości. W dalszej części zweryfikujemy poprawność BST i wykorzystamy właściwości przejścia inorder.
Często zadawane pytania
Czy lekcja „Usuwanie z BST: trzy przypadki” jest bezpłatna?
Tak — pełny tekst „Usuwanie z BST: trzy przypadki” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Usuwanie z BST: trzy przypadki”?
Obsłużą Państwo usuwanie liścia, węzła z jednym dzieckiem i węzła z dwojgiem dzieci, korzystając z następnika inorder i implementując algorytm od podstaw. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Usuwanie z BST: trzy przypadki”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Wstawianie i wyszukiwanie w BST
- Usuwanie z BST: trzy przypadki
- Sprawdzanie BST i właściwości inorder
- K-ty najmniejszy element, suma zakresu i BST do posortowanej tablicy