Wstawianie i wyszukiwanie w BST
Zaimplementują Państwo rekurencyjne i iteracyjne wstawianie oraz wyszukiwanie, prześledzą ścieżkę przez drzewo dla różnych kluczy i przeanalizują złożoność pesymistyczną dla drzew niezrównoważonych.
Wstawianie i wyszukiwanie w BST to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 1 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 DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Definicja własności BST
Drzewo wyszukiwania binarnego spełnia jeden niezmiennik: dla każdego węzła wszystkie wartości w jego lewym poddrzewie są ściśle mniejsze od wartości tego węzła, a wszystkie wartości w jego prawym poddrzewie są ściśle większe. Ta własność porządku — zachowywana w całym poddrzewie, a nie tylko w bezpośrednich dzieciach — umożliwia wyszukiwanie, wstawianie i usuwanie w czasie O(log n) w zrównoważonych drzewach oraz odróżnia BST od ogólnego drzewa binarnego.
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')Rekurencyjne wyszukiwanie w BST
Wyszukiwanie w BST działa podobnie jak wyszukiwanie binarne: należy porównać wartość docelową z wartością bieżącego węzła i przejść rekurencyjnie do odpowiedniego poddrzewa. Jeśli wartość docelowa jest równa bieżącej wartości, należy zwrócić węzeł. Jeśli jest mniejsza, trzeba przejść w lewo, a jeśli większa — w prawo. Po dotarciu do pustego węzła należy zwrócić wartość null. Złożoność czasowa wynosi O(h): O(log n) dla drzew zrównoważonych i O(n) dla drzew zdegenerowanych.
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 foundIteracyjne wyszukiwanie w BST
Wyszukiwanie iteracyjne pozwala uniknąć narzutu stosu wywołań i jest preferowane w kodzie produkcyjnym. Należy użyć wskaźnika curr, który przechodzi w dół drzewa, podążając w lewo lub w prawo zależnie od porównań. Jest to prosta pętla while z trzema przypadkami: null (nie znaleziono), dopasowanie (znaleziono) lub zmiana kierunku. Wyszukiwanie iteracyjne również działa w czasie O(h), ale zużywa O(1) pamięci zamiast O(h) jak wersja rekurencyjna.
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)) # NoneRekurencyjne wstawianie do BST
Wstawianie do BST polega na znalezieniu właściwego miejsca przez podejmowanie takich samych decyzji o przejściu w lewo lub w prawo jak podczas wyszukiwania, a następnie dołączeniu nowego węzła w pierwszym napotkanym miejscu null. Podejście rekurencyjne zwraca, być może nowy, korzeń każdego poddrzewa: jeśli bieżący węzeł ma wartość null, należy zwrócić nowy TreeNode; w przeciwnym razie trzeba zaktualizować root.left lub root.right wynikiem wywołania rekurencyjnego. Ten wzorzec jest przejrzysty i często stosowany w rozwiązaniach zadań rekrutacyjnych.
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) # 5Iteracyjne wstawianie do BST
Iteracyjne wstawianie używa wskaźnika parent do śledzenia ostatniego niepustego węzła przed dotarciem do miejsca wstawienia. Należy przechodzić w dół drzewa tak jak podczas wyszukiwania, śledząc rodzica i ostatni obrany kierunek. Po dotarciu do null trzeba dołączyć nowy węzeł po odpowiedniej stronie rodzica. Przypadek brzegowy pustego drzewa (gdy root ma wartość null) należy zawsze obsłużyć osobno.
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) # 3BST w najgorszym przypadku: drzewa zdegenerowane
Jeśli do BST wstawimy posortowaną sekwencję, otrzymamy drzewo zdegenerowane, które przekształca się w listę połączoną. Wyszukiwanie, wstawianie i usuwanie mają wtedy złożoność O(n). Z tego powodu istnieją zrównoważone drzewa BST, takie jak drzewa AVL i czerwono-czarne. Podczas rozmów rekrutacyjnych należy zawsze wspomnieć o tym najgorszym przypadku, gdy pytanie dotyczy złożoności BST — stwierdzenie „średnio O(log n), w najgorszym przypadku O(n) dla niezrównoważonych drzew” pokazuje dobre zrozumienie tematu.
# 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)Znajdowanie minimum i maksimum
W BST wartość minimalna zawsze znajduje się w najbardziej lewym węźle (należy przechodzić w lewo, aż do napotkania null), a wartość maksymalna — w najbardziej prawym węźle. Te operacje o złożoności O(h) są często używane jako podprocedury podczas usuwania z BST (do znajdowania następnika w porządku inorder) oraz w zapytaniach zakresowych. Znajomość tych funkcji pomocniczych na pamięć oszczędza czas podczas rozmów rekrutacyjnych.
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) # 9Następnik i poprzednik w porządku inorder
Następnik w porządku inorder danego węzła to węzeł o najmniejszej wartości większej od jego wartości. Jeśli węzeł ma prawe poddrzewo, następnikiem jest find_min(node.right). Jeśli nie ma prawego poddrzewa, następnikiem jest najniższy przodek, w którego lewym poddrzewie znajduje się dany węzeł. Zrozumienie tej zasady ma kluczowe znaczenie przy usuwaniu z BST i zadaniach dotyczących iteratora 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) # 1Analiza złożoności wyszukiwania w BST
Wydajność BST zależy całkowicie od wysokości drzewa. W przypadku zrównoważonego BST zawierającego n węzłów wysokość wynosi O(log n), co daje O(log n) dla wyszukiwania, wstawiania i usuwania. W przypadku zdegenerowanego BST wysokość wynosi O(n), więc wszystkie operacje mają złożoność O(n). Python nie ma wbudowanego zrównoważonego BST, w przeciwieństwie do języka Java z klasą TreeMap, dlatego należy samodzielnie zaimplementować AVL lub drzewo czerwono-czarne, użyć sortedcontainers.SortedList albo zastosować kopiec w przypadkach użycia kolejki priorytetowej.
# 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')Wstawianie do BST: przypadki brzegowe
Należy zawsze sprawdzić, czy wstawianie obsługuje: puste drzewo (zwrócenie nowego węzła jako korzenia), zduplikowane wartości (trzeba określić, czy je pomijać, wstawiać po lewej, czy po prawej stronie — i konsekwentnie stosować wybraną zasadę) oraz bardzo duże lub bardzo małe wartości. Podczas rozmowy rekrutacyjnej należy przed rozpoczęciem kodowania określić założenie dotyczące duplikatów. Najczęstsza konwencja w zadaniach LeetCode zakłada, że wszystkie wartości są różne, chyba że zaznaczono inaczej.
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 7BST z posortowanej tablicy
Budowanie zrównoważonego co do wysokości BST z posortowanej tablicy (LeetCode #108) wykorzystuje metodę dziel i zwyciężaj: element środkowy staje się korzeniem, lewa połowa — lewym poddrzewem, a prawa połowa — prawym poddrzewem. Gwarantuje to zrównoważone drzewo o wysokości O(log n). Złożoność czasowa wynosi O(n), ponieważ każdy element jest przetwarzany dokładnie raz.
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) # 9Szybkie sprawdzenie
Proszę sprawdzić, czy rozumieją Państwo zagadnienia z kursu Data Structures & Algorithms — Coding Interview Prep omówione w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo: własności BST (lewe poddrzewo zawiera wartości ściśle mniejsze, a prawe ściśle większe), wyszukiwania i wstawiania zarówno rekurencyjnie, jak i iteracyjnie, w czasie O(h), oraz zdegenerowanych drzew w najgorszym przypadku, w których wysokość jest równa n. Następnie zajmiemy się usuwaniem z BST i jego trzema przypadkami.
Często zadawane pytania
Czy lekcja „Wstawianie i wyszukiwanie w BST” jest bezpłatna?
Tak — pełny tekst „Wstawianie i wyszukiwanie w BST” 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 DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Wstawianie i wyszukiwanie w BST”?
Zaimplementują Państwo rekurencyjne i iteracyjne wstawianie oraz wyszukiwanie, prześledzą ścieżkę przez drzewo dla różnych kluczy i przeanalizują złożoność pesymistyczną dla drzew niezrównoważonych. Ćwiczysz DSA 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ąć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA 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 1 z 4.
Ile czasu zajmuje lekcja „Wstawianie i wyszukiwanie w BST”?
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 DSA Interview Prep?
Tak. Każda lekcja DSA 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