java - 是否建议使用对父节点的引用来实现二叉搜索树？

Question

我很困惑是否使用对父母的引用。它显着降低了删除操作的算法复杂度。但我看到了一些反对使用它的令人信服的论据，比如空间要求。那么使用父指针是否很好。生产质量代码是否使用对父级的引用？

Answer 1

简短的回答：这取决于.

回答以下问题会有所帮助：

1. 你想经常做什么？
2. 你想快速做什么？
3. 你有多少内存？

父指针可以很容易地找到最低公共祖先，也可以很容易地删除节点。

你打算用 BST 做什么？

有了更多的细节，我们可以为您提供更多帮助。

反对使用它的有力论据：

吹毛求疵：如果它令人信服，为什么要问这个问题？

无论如何，如果我是你，我会包含对父节点的引用，因为它使大量功能更容易实现。

再次，这最终成为时间和记忆之间的权衡。如果您愿意在一个方面花费更多，那么您可以在另一个方面做得更好。