建議使用對父節點的引用來實現二叉查找樹嗎？

Question

我很困惑是否使用對父項的引用。它顯着降低了刪除操作的算法複雜度。但是我已經看到了一些反對使用它的有力論據，比如空間要求。所以這是很好的使用父指針。生產質量代碼是否使用父母的參考？

Answer 1

簡短的回答：這取決於。

回答以下問題的幫助：

1. 要經常做什麼？
2. 你想快速做什麼？
3. 你有多少內存？

父指針可以很容易找到最低公共祖先，也可以很容易地刪除節點。

您打算如何使用BST？

有了更多的細節，我們可以幫助您更多。

令人信服的理由反對它的使用：

只是吹毛求疵：如果這是令人信服的，爲什麼問這個問題？

無論如何，如果我是你，我會包括簡單的父節點的引用，因爲它使一噸的功能更容易實現。

這又最終被時間和memory.If之間的權衡你願意花更多的錢一個，你可以做其他的因素更好。