BST:n lisäys ja haku
Toteuttakaa lisäys ja haku rekursiivisesti ja iteroivasti, jäljittäkää polku puun läpi eri avaimilla ja analysoikaa tasapainottamattomien puiden pahimman tapauksen vaativuus.
BST:n lisäys ja haku on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Binäärihakupuun ominaisuus määriteltynä
Binäärihakupuulla on yksi invariantti: jokaisen solmun vasemman osapuun kaikki arvot ovat aidosti pienempiä kuin solmun arvo ja oikean osapuun kaikki arvot ovat aidosti suurempia. Tämä koko osupuussa, ei vain välittömissä lapsissa, säilyvä järjestysominaisuus mahdollistaa haun, lisäyksen ja poiston ajassa O(log n) tasapainotetuissa puissa ja erottaa binäärihakupuun yleisestä binääripuusta.
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')Rekursiivinen haku binäärihakupuusta
Binäärihakupuusta etsiminen toimii kuten binäärihaku: verratkaa kohdetta nykyisen solmun arvoon ja kutsukaa rekursiota sopivassa osapuussa. Jos kohde on yhtä suuri kuin nykyinen arvo, palauttakaa solmu. Jos kohde on pienempi, siirtykää vasemmalle; jos suurempi, siirtykää oikealle. Palauttakaa null, jos saavutatte tyhjän solmun. Aikavaativuus on O(h) — tasapainotetussa puussa O(log n) ja vinossa puussa 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 foundIteratiivinen haku binäärihakupuusta
Iteratiivinen haku välttää kutsupinon yleiskustannukset, ja sitä suositaan tuotantokoodissa. Käyttäkää osoitinta curr, joka kulkee puussa alaspäin vasemmalle tai oikealle vertailujen perusteella. Kyseessä on yksinkertainen while-silmukka, jossa on kolme tapausta: null (ei löydy), osuma (löytyy) tai suunnan muuttaminen. Myös iteratiivisen haun aikavaativuus on O(h), mutta se käyttää O(1) tilaa rekursiivisen version O(h):n sijaan.
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)) # NoneRekursiivinen lisäys binäärihakupuuhun
Binäärihakupuuhun lisääminen etsii oikean paikan tekemällä samat vasen/oikea-päätökset kuin haku ja kiinnittää sitten uuden solmun ensimmäiseen saavutettuun null-kohtaan. Rekursiivinen lähestymistapa palauttaa kunkin osapuun mahdollisesti uuden juuren: jos nykyinen solmu on null, palautetaan uusi TreeNode; muussa tapauksessa päivitetään root.left tai root.right rekursiivisen kutsun tuloksella. Tämä kuvio on selkeä ja yleinen haastatteluratkaisuissa.
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) # 5Iteratiivinen lisäys binäärihakupuuhun
Iteratiivisessa lisäyksessä käytetään parent-osoitinta seuraamaan viimeistä ei-null-solmua ennen lisäyskohtaa. Kulkekaa puussa kuten haussa ja pitäkää samalla kirjaa vanhemmasta sekä viimeksi kuljetusta suunnasta. Kun saavutatte null-arvon, kiinnittäkää uusi solmu vanhemman oikealle puolelle. Käsitelkää tyhjän puun erityistapaus (root on null) aina erikseen.
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) # 3Binäärihakupuun pahin tapaus: vinot puut
Jos lisäätte järjestetyn jonon binäärihakupuuhun, tuloksena on vino puu, joka rappeutuu linkitetyksi listaksi. Haun, lisäyksen ja poiston aikavaativuus muuttuu kaikissa tapauksissa O(n):ksi. Tästä syystä on olemassa tasapainotettuja binäärihakupuita, kuten AVL-puut ja puna-mustat puut. Mainitkaa haastatteluissa aina tämä pahin tapaus, kun teiltä kysytään binäärihakupuun aikavaativuudesta — toteamus ”keskimäärin O(log n), epätasapainotetussa puussa pahimmillaan O(n)” osoittaa syvällistä ymmärrystä.
# 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)Minimin ja maksimin etsiminen
Binäärihakupuussa minimiarvo on aina vasemmanpuoleisimmassa solmussa: jatkakaa vasemmalle, kunnes saavutatte null-arvon. Maksimiarvo on vastaavasti oikeanpuoleisimmassa solmussa. Näitä O(h)-operaatioita käytetään usein binäärihakupuusta poistamisen apurutiineina, esimerkiksi sisäjärjestyksen seuraajan etsimiseen, sekä aluekyselyissä. Näiden apufunktioiden ulkoa osaaminen säästää aikaa haastatteluissa.
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) # 9Sisäjärjestyksen seuraaja ja edeltäjä
Solmun sisäjärjestyksen seuraaja on solmu, jonka arvo on solmun arvoa suurempi mutta kaikista tällaisista arvoista pienin. Jos solmulla on oikea osapuu, seuraaja on find_min(node.right). Jos oikeaa osapuuta ei ole, seuraaja on alin esi-isä, jonka vasemmassa osapuussa annettu solmu sijaitsee. Tämän ymmärtäminen on olennaista binäärihakupuusta poistamisessa ja binäärihakupuu-iteraattorin ongelmissa.
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) # 1Binäärihakupuun haun aikavaativuuden analyysi
Binäärihakupuun suorituskyky riippuu täysin puun korkeudesta. Tasapainotetussa binäärihakupuussa, jossa on n solmua, korkeus on O(log n), joten haku, lisäys ja poisto toimivat ajassa O(log n). Vinossa binäärihakupuussa korkeus on O(n), joten kaikkien operaatioiden aikavaativuus on O(n). Pythonissa ei ole sisäänrakennettua tasapainotettua binäärihakupuuta, toisin kuin Java-kielen TreeMap-rakenteessa, joten voitte toteuttaa AVL- tai puna-mustan puun itse, käyttää sortedcontainers.SortedList-rakennetta tai hyödyntää kekoa prioriteettijonon käyttötapauksissa.
# 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')Binäärihakupuuhun lisääminen: erityistapaukset
Varmistakaa aina, että lisäys käsittelee seuraavat tapaukset: tyhjä puu (palautetaan uusi solmu juureksi), toistuvat arvot (määritelkää, jätetäänkö ne huomiotta vai lisätäänkö ne vasemmalle tai oikealle — toimikaa johdonmukaisesti) sekä erittäin suuret tai pienet arvot. Ilmoittakaa haastatteluissa oletuksenne toistuvista arvoista ennen koodaamista. LeetCode-tehtävissä yleisin käytäntö on, että kaikki arvot ovat erisuuria, ellei toisin ilmoiteta.
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 7Binäärihakupuu järjestetystä taulukosta
Korkeudeltaan tasapainotetun binäärihakupuun rakentaminen järjestetystä taulukosta (LeetCode #108) perustuu hajota ja hallitse -menetelmään: keskimmäisestä alkiosta tulee juuri, vasemmasta puoliskosta vasen osapuu ja oikeasta puoliskosta oikea osapuu. Näin puu pysyy tasapainotettuna ja sen korkeus on O(log n). Aikavaativuus on O(n), koska jokainen alkio käsitellään kerran.
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) # 9Pikatarkistus
Testatkaa ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheista.
Oppitunnin kertaus
Tässä oppitunnissa opitte binäärihakupuun ominaisuuden (vasen osapuu on aidosti pienempi ja oikea osapuu aidosti suurempi), haun ja lisäyksen sekä rekursiivisesti että iteratiivisesti ajassa O(h) sekä vinot puut pahimmassa tapauksessa, jolloin korkeus on n. Seuraavaksi käsittelemme binäärihakupuusta poistamista ja sen kolmea tapausta.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”BST:n lisäys ja haku” ilmainen?
Kyllä – oppitunnin ”BST:n lisäys ja haku” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”BST:n lisäys ja haku”?
Toteuttakaa lisäys ja haku rekursiivisesti ja iteroivasti, jäljittäkää polku puun läpi eri avaimilla ja analysoikaa tasapainottamattomien puiden pahimman tapauksen vaativuus. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”BST:n lisäys ja haku”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- BST:n lisäys ja haku
- BST:n poisto: kolme tapausta
- BST:n kelvollisuuden ja in-order-ominaisuuksien tarkistaminen
- K:nneksi pienin, alueen summa ja BST järjestetyksi taulukoksi