不明白此二進制搜索樹（BST）示例算法

Question

在從here刪除代碼。

我不明白第一個刪除代碼片段（其中節點沒有兩個孩子）。

如果被刪除的節點本身有一個父節點和一個子節點（即節點有一個孩子），它是如何工作的？

該代碼只是刪除節點，並沒有設置父指針現在孤兒的孩子。

我錯過了什麼嗎？

Answer 1

我可能是錯的，但引用網站上的代碼似乎沒問題。雖然我沒有測試過它。

這是真的，因爲delete函數接受一個類型爲BSTNode **節點的參數。這不是指向節點的指針。這是父節點指向節點本身的指針。這可能有點草率，但我必須承認在實現代碼後，它是一種優雅的解決方案。所以當你重寫（* node）時，你並沒有重寫節點本身，而是你正在改寫節點的父節點指向節點。有效的代碼是以你稍微變態的方式做你的建議：D。希望你明白我的意思，我希望我的理解正確。

我還建議您閱讀關於紅黑樹的更多信息，因爲本文僅提供洞察創建樹，但所描述的結構對其高度沒有漸近邊界。如果，例如您在此結構中推送排序值，它將成爲連接列表而不是平衡樹。

---