我很好奇 BST 中節點洗掉的這種實作（有關其他代碼/背景關系，請參閱完整實作。）這是我的理解方式：
if val < self.data并且elif val > self.data都是當前節點不是要洗掉的節點的情況，因此它們遞回地在適當的子節點上呼叫洗掉函式。else是我們找到了正確的節點并需要執行洗掉的情況。一種。
if self.left is None and self.right is None: return None我不清楚這里的目標是什么。我們回傳了 None，但沒有將節點值本身重新分配給 None。灣。至此，我們已經排除了left和 right 都不存在的可能性，因此
elif self.left is None是一種冗長的 write 方式elif self.right，它回傳 right。但為什么？它不會重新分配節點本身的值。C。我不確定為什么最后一個控制流陳述句是
elif self.right is None. 為什么沒有 else 陳述句？這種 min_val、self.data、self.right 舞蹈僅在 #2 中的上述控制流陳述句之一沒有條件執行時才會發生，所以我認為這是一個隱含的 else 陳述句。
一種。這一步實際上歸結為為 self.data 分配其右子節點的最小值，然后分配 self.right 遞回函式呼叫的輸出，這可能是來自 #2 的 left、right 或 None。
def delete(self, val):
if val < self.data:
if self.left:
self.left = self.left.delete(val)
elif val > self.data:
if self.right:
self.right = self.right.delete(val)
else:
if self.left is None and self.right is None:
return None
elif self.left is None:
return self.right
elif self.right is None:
return self.left
min_val = self.right.find_min()
self.data = min_val
self.right = self.right.delete(min_val)
return self
要回答這個問題，請確認或糾正我上面的一些疑問。
uj5u.com熱心網友回復：
該演算法的第一個案例是關于從樹中洗掉節點：洗掉對它們的所有參考，同時保持 BST 的密鑰順序。
想想你會如何用鉛筆和紙來做這件事。
如果洗掉的節點沒有子節點，則重繪父節點的指標以指向空（
None）。洗掉的節點現在從樹中“切出”。BST 訂單保持不變。如果洗掉的節點只有一個子節點，則替換父節點的指標，使其現在指向該子節點。再次從樹中洗掉洗掉的節點，保持 BST 密鑰順序。
請注意，父指標的替換發生在對delete. 例如，通過回傳None，“沒有孩子”的情況導致父母不指向任何東西。“切出”的節點最終將由 Python 進行垃圾收集。
- 否則你會遇到更復雜的情況：被洗掉節點只有一個父節點和兩個子節點。該怎么辦？此特定代碼查找已洗掉節點的下一個最大鍵，并使用它來替換要洗掉的鍵。該節點根本沒有被切斷。然后它從右子樹中洗掉移動的值，這確實會導致其節點被洗掉。再次維護 BST 密鑰順序。
這種實作第三種情況的方式可以生成干凈的代碼，并且在所有資料訪問都通過參考（指標）進行的 Python 中可能是有意義的。但這不是唯一的選擇。另一種方法是繼續與其他情況相同的模式，并實際切出包含已洗掉值的節點并將下一個最大節點移動到該位置（不僅僅是關鍵資料）。如果節點實際上包含資料（不僅僅是對它的參考），這是一個更好的選擇，而且它非常大。它保存所有資料的副本。如果作者做出了這樣的選擇，就會有另一個return該節點用于重新分配父指標。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/473276.html