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

Question

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

Answer 1

简短回答:视情况而定。

回答以下问题有帮助:

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

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

您打算将 BST 用于什么目的？

提供更多详细信息，我们可以为您提供更多帮助。

Compelling arguments against it's use:

吹毛求疵:如果它很有说服力，为什么要问这个问题？

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

这最终也是时间和内存之间的权衡。如果您愿意在一个方面花费更多，那么您可以在另一个方面做得更好。