BST Silme: Üç Durum
Yaprak silme, tek çocuklu düğüm silme ve iki çocuklu düğüm silme durumlarını, orta sıralı ardılı kullanarak ele alın ve algoritmayı sıfırdan uygulayın.
BST Silme: Üç Durum, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
BST Silme İşlemi Neden Zordur
BST silme, üç temel işlem arasındaki en karmaşık işlemdir; çünkü bir düğümü kaldırmak, BST özelliğini ağacın tamamında korumalıdır. Düğümün çocuklarına bağlı olarak üç ayrı durum vardır: hiç çocuğu yoktur (yapraktır), bir çocuğu vardır veya iki çocuğu vardır. Her durum farklı bir strateji gerektirir. Mülakat yapanlar bu problemi sever; çünkü işaretçi işlemlerini, sınır durumlarını değerlendirme becerisini ve sıralı geçişte ardıl kavramını sınar.
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')Durum 1: Yaprak Düğümü Silme
Yaprak düğümün hiç çocuğu yoktur. Silme işlemi basittir: özyinelemeli çağrıdan None döndürün; böylece üst düğüm işaretçisini (sol veya sağ) boşa ayarlar. Bu, tüm BST silme uygulamalarının önce ele alması gereken temel durumdur. Ağacın yalnızca bir düğüm içerdiği özel durumun da (kökün yaprak olması) doğru çalıştığını doğrulayın.
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 intact2. Durum: Tek Çocuklu Düğüm
Bir düğümün tam olarak bir çocuğu olduğunda, düğümü bu çocukla değiştirin. Ebeveynin göstericisinin silinen düğümü atlayacak şekilde güncellenmesi için özyinelemeli çağrıdan boş olmayan çocuğu döndürün. Tek çocuk solda da sağda da olsa bu işlem sorunsuz çalışır; yalnızca mevcut olanı döndürün.
# 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')3. Durum: İki Çocuklu Düğüm
Bir düğümün iki çocuğu olduğunda onu basitçe kaldıramayız. Bunun yerine düğümün sıralı ardılını (sağ alt ağaçtaki en küçük değeri) bulun, değerini mevcut düğüme kopyalayın ve ardından sıralı ardılı sağ alt ağaçtan silin. Ardılın en fazla bir çocuğu vardır (sol çocuğu yoktur); dolayısıyla onu silmek, nasıl ele alınacağını zaten bildiğimiz 1. veya 2. Duruma girer.
# 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')Eksiksiz BST Silme Uygulaması
Tam özyinelemeli silme işlemi üç durumu da birleştirir. Değerleri karşılaştırarak silinecek düğümü bulun ve ardından uygun durumu ele alın. Her düzeyde (muhtemelen değiştirilmiş) kökü döndürüp bunu root.left veya root.right değişkenine atama deseni, açıkça ebeveyn takibi yapmadan tüm gösterici güncellemelerini zarifçe ele alır. Zaman karmaşıklığı O(h)'dir.
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)Sıralı Ardıl Neden Kullanılır?
Sıralı ardıl (sağ alt ağacın minimumu), sol alt ağacın maksimumu yerine kullanılır; çünkü her ikisi de geçerli seçimlerdir ve ikisinden birini kullanmak BST özelliğini korur. Sıralı öncül (sol alt ağacın maksimumu) de işe yarar. Bazı uygulamalar ağacı dengeli tutmak için bu iki seçeneği dönüşümlü kullanır. Mülakatlarda genellikle sıralı ardıl sürümünün yazılması beklenir; öncülün de aynı şekilde işe yaradığını belirtin.
# 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')Bir Değere Sahip Tüm Düğümleri Silme
Bir varyantta, bir aralıkta bulunan veya bir koşulla eşleşen değerlere sahip tüm düğümleri silmeniz istenir. Bu işlem bir BST için verimlidir: karşılaştırmalara göre uygun alt ağaçta özyinelemeli olarak ilerleyin ve koşulun eşleştiği her yerde silme işlemini uygulayın. BST silme işleminin özyinelemeli yapısı, ayrı bir dolaşma geçişi gerektirmeden bu senaryolara doğal biçimde genişletilebilir.
# 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 Yineleyici Örüntüsü
BST yineleyicisi (LeetCode #173), elemanları her seferinde bir tane olmak üzere sıralı düzende döndürür; ortalama O(1) zaman ve O(h) alan kullanır. Yineleyiciyi, yinelemeli sıralı dolaşımı taklit eden bir yığınla uygulayın: oluşturma sırasında kökten başlayarak tüm sol düğümleri yığına itin. next() çağrısında en üstteki düğümü çıkarın ve sağ alt ağacın tüm sol düğümlerini yığına itin. Bu, yinelemeli sıralı algoritmanın kontrollü biçimde açılmasıdır.
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 15Düğüm Silme: Karmaşıklık Analizi
BST silme işlemi, h ağaç yüksekliğini gösterirken O(h) zamanda çalışır. Dengeli bir BST için bu değer O(log n)'dir. Eğik bir ağaçta ise O(n)'e düşer. Sıralı ardılı bulmak, sağ alt ağaçta en fazla bir ek O(h) dolaşımı gerektirir; bu da genel karmaşıklığı değiştirmez. Özyinelemeli uygulamada alan karmaşıklığı, çağrı yığını için O(h)'dir.
# 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')BST'de İki Toplam
İki Toplam IV, bir BST'de herhangi iki düğümün toplamının hedefe eşit olup olmadığını sorar. Yaklaşımlardan biri bir küme kullanır: sıralı dolaşım sırasında değerleri toplarken, target - current değerinin o ana kadar kümede bulunup bulunmadığını kontrol eder. Daha zarif bir yaklaşım, biri ileri yönde, diğeri geriye yönde çalışan bir BST yineleyicisini eşzamanlı kullanır (iki gösterici gibi); bu yaklaşım, her yineleyicinin yığını için gereken O(h) alan dışında ek alan kullanımını önler.
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'yi Daha Büyük Toplam Ağacına Dönüştürme
Daha büyük toplam ağacı (LeetCode #538), her düğümün değerini BST'de kendisinden büyük veya kendisine eşit tüm değerlerin toplamıyla değiştirir. Temel fikir şudur: düğümleri azalan sırada ziyaret edip çalışan bir toplam biriktirmek için ters sıralı dolaşım (sağ → kök → sol) gerçekleştirin. Bu işlem O(n) zamanda ve O(h) alanda çalışır.
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 = 18Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayıp anlamadığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: üç BST silme durumu (yaprak, tek çocuk, iki çocuk), iki çocuklu silme için sıralı ardıl tekniği ve BST yineleyicisi ile BST'den daha büyük toplam ağacına dönüşüm gibi temiz özyinelemeli kalıplar. Sırada BST doğruluğunu doğrulamak ve sıralı dolaşım özelliklerinden yararlanmak var.
Sıkça Sorulan Sorular
“BST Silme: Üç Durum” dersi ücretsiz mi?
Evet — “BST Silme: Üç Durum” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“BST Silme: Üç Durum” dersinde ne öğreneceğim?
Yaprak silme, tek çocuklu düğüm silme ve iki çocuklu düğüm silme durumlarını, orta sıralı ardılı kullanarak ele alın ve algoritmayı sıfırdan uygulayın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“BST Silme: Üç Durum” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- BST Ekleme ve Arama
- BST Silme: Üç Durum
- BST’yi ve Orta Sıralı Özellikleri Doğrulama
- K’inci En Küçük, Aralık Toplamı ve BST’den Sıralı Diziye