BST-innsetting og -søk
Implementer rekursiv og iterativ innsetting og søking, følg stien gjennom treet for ulike nøkler, og analyser verst tenkelig kompleksitet for ubalanserte trær.
BST-innsetting og -søk er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 1 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
BST-egenskapen definert
Et binært søketre oppfyller én invariant: For hver node er alle verdier i det venstre undertreet strengt mindre enn nodens verdi, og alle verdier i det høyre undertreet strengt større. Denne ordensegenskapen — som opprettholdes i hele undertreet, ikke bare hos de nærmeste barna — muliggjør søk, innsetting og sletting i O(log n) i balanserte trær og skiller et BST fra et generelt binært tre.
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')Rekursivt BST-søk
BST-søk fungerer som binærsøk: sammenlign målet med verdien til den gjeldende noden, og rekursér til det riktige undertreet. Hvis målet er lik den gjeldende verdien, returnerer du noden. Hvis målet er mindre, går du til venstre; hvis det er større, går du til høyre. Returner null hvis du når en tom node. Tidskompleksiteten er O(h) — O(log n) for balanserte trær og O(n) for skjeve trær.
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 foundIterativt BST-søk
Det iterative søket unngår belastning på kallstakken og foretrekkes i produksjonskode. Bruk en peker curr som går nedover i treet ved å følge venstre eller høyre side, basert på sammenligningene. Dette er en enkel while-løkke med tre tilfeller: null (ikke funnet), treff (funnet) eller juster retningen. Iterativt søk bruker også O(h), men bare O(1) plass, sammenlignet med O(h) for den rekursive varianten.
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)) # NoneRekursiv innsetting i BST
Ved innsetting i et BST finner du riktig plassering ved å følge de samme venstre/høyre-valgene som ved søk, og fester deretter en ny node på den første null-posisjonen du når. Den rekursive tilnærmingen returnerer den (eventuelt nye) roten til hvert undertre: Hvis den gjeldende noden er null, returnerer du en ny TreeNode; ellers oppdaterer du root.left eller root.right med resultatet av det rekursive kallet. Dette mønsteret er ryddig og vanlig i intervjuløsninger.
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) # 5Iterativ innsetting i BST
Ved iterativ innsetting bruker du en parent-peker til å holde oversikt over den siste noden som ikke var null, før du når innsettingspunktet. Gå nedover i treet som ved søk, og hold oversikt over forelderen og hvilken retning du sist gikk i. Når du når null, fester du den nye noden på riktig side av forelderen. Håndter alltid spesialtilfellet med et tomt tre (root er null) separat.
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 i verste fall: Skjeve trær
Hvis du setter inn en sortert sekvens i et BST, får du et skjevt tre som degenererer til en lenket liste. Søk, innsetting og sletting blir alle O(n). Dette er grunnen til at balanserte BST-er (AVL-trær og rød-svarte trær) finnes. I intervjuer bør du alltid nevne dette verste tilfellet når du blir spurt om kompleksiteten til BST — å si «O(log n) i gjennomsnitt, O(n) i verste fall for ubalanserte trær» viser god forståelse.
# 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)Finne minimum og maksimum
I et BST er minimumsverdien alltid den noden som ligger lengst til venstre (fortsett mot venstre til du når null), og maksimumsverdien er noden lengst til høyre. Disse operasjonene, som bruker O(h), brukes ofte som hjelperutiner ved sletting i BST (for å finne in-order-etterfølgeren) og i intervallspørringer. Når du kan disse hjelperutinene utenat, sparer du tid i intervjuer.
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) # 9In-order-etterfølger og forgjenger
In-order-etterfølgeren til en node er noden med den minste verdien som er større enn den. Hvis noden har et høyre undertre, er etterfølgeren find_min(node.right). Hvis den ikke har et høyre undertre, er etterfølgeren den laveste stamfaren der den aktuelle noden ligger i det venstre undertreet. Å forstå dette er avgjørende for problemer med sletting i BST og BST-iteratorer.
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) # 1Analyse av kompleksiteten til BST-søk
Ytelsen til BST avhenger helt av trehøyden. For et balansert BST med n noder er høyden O(log n), noe som gir O(log n) for søk, innsetting og sletting. For et skjevt BST er høyden O(n), noe som gir O(n) for alle operasjoner. Python har ikke et innebygd balansert BST (i motsetning til Java sitt TreeMap), så du må enten implementere AVL eller Red-Black selv, bruke sortedcontainers.SortedList eller benytte en heap for brukstilfeller med prioritetskø.
# 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')Sette inn i BST: Spesialtilfeller
Kontroller alltid at innsettingen håndterer: tomt tre (returner den nye noden som rot), duplikatverdier (bestem om de skal ignoreres, settes inn til venstre eller settes inn til høyre — vær konsekvent), og svært store eller små verdier. I intervjuer bør du oppgi antakelsen din om duplikater før du begynner å kode. Den vanligste konvensjonen i LeetCode-problemer er at alle verdier er forskjellige, med mindre noe annet er angitt.
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 fra sortert array
Å bygge et høydebalansert BST fra en sortert array (LeetCode #108) bruker del-og-hersk-teknikken: Midtelementet blir roten, den venstre halvdelen blir det venstre undertreet, og den høyre halvdelen blir det høyre undertreet. Dette garanterer et balansert tre med høyde O(log n). Tidskompleksiteten er O(n), siden hvert element behandles én gang.
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) # 9Hurtigsjekk
Test forståelsen din av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte du: BST-egenskapen (venstre undertre er strengt mindre, høyre undertre er strengt større), søk og innsetting både rekursivt og iterativt med O(h)-tid, og skjeve trær i verste fall der høyden er lik n. Deretter tar vi for oss sletting i BST og de tre tilfellene.
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «BST-innsetting og -søk» gratis?
Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «BST-innsetting og -søk», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Hva lærer jeg i «BST-innsetting og -søk»?
Implementer rekursiv og iterativ innsetting og søking, følg stien gjennom treet for ulike nøkler, og analyser verst tenkelig kompleksitet for ubalanserte trær. Du øver på DSA Interview Prep med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med DSA Interview Prep?
Ingen tidligere erfaring er nødvendig. DSA Interview Prep på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «BST-innsetting og -søk»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne DSA Interview Prep-leksjonen?
Ja. Alle DSA Interview Prep-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- BST-innsetting og -søk
- BST-sletting: tre tilfeller
- Validering av BST og egenskaper ved in-order
- K-te minste, intervallsum og BST til sortert array