BST:n poisto: kolme tapausta
Käsitelkää lehden, yhden lapsen ja kahden lapsen poistot in-order-seuraajan avulla ja toteuttakaa algoritmi alusta alkaen.
BST:n poisto: kolme tapausta on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/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.
Miksi binäärihakupuusta poistaminen on hankalaa
Binäärihakupuusta poistaminen on kolmesta keskeisestä operaatiosta monimutkaisin, koska solmun poistamisen on säilytettävä binäärihakupuun ominaisuus koko puussa. Tapauksia on kolme erilaista solmun lasten perusteella: solmulla ei ole lapsia eli se on lehti, sillä on yksi lapsi tai sillä on kaksi lasta. Jokainen tapaus vaatii erilaisen strategian. Haastattelijat pitävät tästä ongelmasta, koska se testaa osoittimien käsittelyä, erityistapausten huomioimista ja sisäjärjestyksen seuraajan käsitteen tuntemusta.
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')Tapaus 1: lehtisolmun poistaminen
Lehtisolmulla ei ole lapsia. Poistaminen on yksinkertaista: palauttakaa rekursiivisesta kutsusta None, jolloin vanhempi asettaa osoittimensa, vasemman tai oikean, arvoksi null. Tämä on perustapaus, joka kaikkien binäärihakupuusta poistavien toteutusten on käsiteltävä ensin. Varmistakaa, että tämä toimii myös erityistapauksessa, jossa puussa on vain yksi solmu eli juuri on lehti.
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 intactTapaus 2: solmulla on yksi lapsi
Kun solmulla on täsmälleen yksi lapsi, korvatkaa solmu tällä lapsella. Palauttakaa rekursiivisesta kutsusta ei-tyhjä lapsi, jotta vanhemman osoitin päivittyy ohittamaan poistettu solmu. Tämä toimii samalla tavalla riippumatta siitä, onko ainoa lapsi vasemmalla vai oikealla — palauttakaa vain se, joka on olemassa.
# 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')Tapaus 3: solmulla on kaksi lasta
Kun solmulla on kaksi lasta, sitä ei voi yksinkertaisesti poistaa. Etsikää sen sijaan solmun in-order-seuraaja (oikean alipuun pienin arvo), kopioikaa sen arvo nykyiseen solmuun ja poistakaa sitten in-order-seuraaja oikeasta alipuusta. Seuraajalla on enintään yksi lapsi (ei vasenta lasta), joten sen poistaminen kuuluu tapaukseen 1 tai 2 — ja nämä tapaukset osataan jo käsitellä.
# 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:n poiston täydellinen toteutus
Täydellinen rekursiivinen poistotoiminto yhdistää kaikki kolme tapausta. Etsikää poistettava solmu vertailemalla arvoja ja käsitelkää sitten sopiva tapaus. Malli, jossa kullakin tasolla palautetaan mahdollisesti muokattu juuri ja sijoitetaan se takaisin kohteeseen root.left tai root.right, käsittelee kaikki osoittimien päivitykset elegantisti ilman erillistä vanhempien seurantaa. Aikavaativuus on 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)Miksi in-order-seuraajaa käytetään?
In-order-seuraajaa (oikean alipuun pienintä arvoa) käytetään vasemman alipuun suurimman arvon sijaan, koska molemmat vaihtoehdot ovat kelvollisia — kumpi tahansa säilyttää BST:n ominaisuuden. Myös in-order-edeltäjä (vasemman alipuun suurin arvo) toimii. Joissakin toteutuksissa vaihtoehtoja käytetään vuorotellen puun tasapainottamiseksi. Haastatteluissa in-order-seuraajaan perustuva versio on yleensä odotetumpi; mainitkaa, että myös edeltäjä toimii yhtä hyvin.
# 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')Kaikkien tietyn arvon sisältävien solmujen poistaminen
Muunnelmassa pyydetään poistamaan kaikki solmut, joiden arvot kuuluvat tietylle välille tai täyttävät tietyn ehdon. BST:n tapauksessa tämä on tehokasta: kutsukaa rekursiota vertailujen perusteella vain asianmukaiseen alipuuhun ja soveltakaa poistotoimintoa kaikkialla, missä ehto täyttyy. BST:n poiston rekursiivinen rakenne laajenee luonnollisesti myös näihin tilanteisiin ilman erillistä läpikäyntiä.
# 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 2BST-iteraattorin malli
BST-iteraattori (LeetCode #173) palauttaa alkiot lajitellussa järjestyksessä yksi kerrallaan. Keskimääräinen aikavaativuus on O(1) ja tilavaativuus O(h). Toteuttakaa se pinolla, joka simuloi iteratiivista in-order-läpikäyntiä: työntäkää konstruktorissa kaikki juuresta alkavat vasemmanpuoleiset solmut pinoon. Kutsussa next() poistakaa päällimmäinen solmu ja työntäkää oikean alipuun kaikki vasemmanpuoleiset solmut pinoon. Tämä on iteratiivisen in-order-algoritmin hallittu purkaminen.
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 15Solmun poistaminen: vaativuusanalyysi
BST:n poiston aikavaativuus on O(h), missä h on puun korkeus. Tasapainotetussa BST:ssä tämä on O(log n). Vino puu heikentää vaativuuden arvoon O(n). In-order-seuraajan etsiminen lisää enintään yhden ylimääräisen O(h):n läpikäynnin oikeaan alipuuhun, mikä ei muuta kokonaisvaativuutta. Rekursiivisen toteutuksen tilavaativuus on O(h) kutsupinon vuoksi.
# 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')Kaksi summaa BST:ssä
BST:n Two Sum IV -tehtävässä kysytään, summautuvatko jonkin kahden solmun arvot tavoitearvoksi. Yksi lähestymistapa käyttää joukkoa: in-order-läpikäynnissä arvot kerätään samalla, kun tarkistetaan, löytyykö target - current jo joukosta. Elegantimpi lähestymistapa käyttää samanaikaisesti eteenpäin ja taaksepäin liikkuvia BST-iteraattoreita (kuten kahta osoitinta) — tällöin ylimääräistä tilaa tarvitaan vain O(h) kummankin iteraattorin pinolle.
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)) # FalseBST:n muuntaminen suurempien arvojen summapuuksi
Suurempien arvojen summapuu (LeetCode #538) korvaa kunkin solmun arvon kaikista BST:n arvoista suurempien tai yhtä suurten arvojen summalla. Keskeinen oivallus on tehdä käänteinen in-order-läpikäynti (oikea → juuri → vasen), jolloin solmut käsitellään laskevassa järjestyksessä ja samalla ylläpidetään kumulatiivista summaa. Aikavaativuus on O(n) ja tilavaativuus 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 = 18Pikatesti
Testatkaa, miten hyvin hallitsette tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteet.
Oppitunnin yhteenveto
Tässä oppitunnissa opitte: BST:n poistamisen kolme tapausta (lehtisolmu, yksi lapsi, kaksi lasta), in-order-seuraajatekniikan kahden lapsen solmun poistamiseen sekä selkeät rekursiiviset mallit, kuten BST-iteraattorin ja BST:n muuntamisen suurempien arvojen summapuuksi. Seuraavaksi tarkistamme BST:n oikeellisuuden ja hyödynnämme in-order-ominaisuuksia.
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 poisto: kolme tapausta” ilmainen?
Kyllä – oppitunnin ”BST:n poisto: kolme tapausta” 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 poisto: kolme tapausta”?
Käsitelkää lehden, yhden lapsen ja kahden lapsen poistot in-order-seuraajan avulla ja toteuttakaa algoritmi alusta alkaen. 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 2/4.
Kuinka kauan ”BST:n poisto: kolme tapausta”-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