带有父指针的二叉搜索树有什么优点？

Question

到目前为止，我一直在使用左指针和右指针实现二叉搜索树，例如：

template<typename T>
struct BSTNode{
    BSTNode* left;
    BSTNode* right;
    T data;
}

我遇到过一些实现，其中节点也有指向父节点的指针。你为什么想这么做？有哪些权衡？

Answer 1

从一个角度来看，你的问题是有效的，因为

parent

指针在结构中引入了冗余，这在几种情况下是可以避免的。但对于二叉树来说，这给您带来了巨大的好处，您可以“向上”跳一级（即从节点到其父节点），而无需记住父节点的地址。如果节点的父节点已知，则可以非常有效且简单地实现多种算法（例如，获取两个值之间的节点数）。

权衡是冗余：如果您修改树的结构（例如通过平衡树），您必须记住更新

left/right

和

parent

指针以保持树的一致性.

Answer 2

二叉搜索树指的是一类非常通用的二叉树。 对于the二叉搜索树，没有理由有父指针。

然而，二叉树还有更专门的变体，其中父指针是有益的。例如，寻找AVL树或红黑树。这些专业化对树的布局施加了进一步的限制，以实现各种目标，例如通过确保树

始终平衡

来保证O(log n)在红黑树中查找/插入/删除的复杂性。

为了满足这些限制，父指针有时会派上用场。当然，它是通过用内存（指针）换取速度（通过算法查找父级）来实现的。

考虑一下你最喜欢的关于数据结构的书，看看如何以及为什么，或者维基百科。

Answer 3

它为您提供了更简单、更小的迭代器，不会因树突变而失效。如果没有父节点，遍历例程需要一个大小等于树深度的堆栈来记住它所在的位置。如果添加或删除节点，则该堆栈将变得陈旧，并且迭代器将不再正常工作，例如它可能会记得重新访问已删除的祖先节点。

当然，保留父指针的代价是内存中的树更大。我无法对性能做出任何声明，因为更新父指针需要时间，而且还消除了某些算法中记住父指针的步骤。因此，权衡归结为一方面拥有一棵较小的树和大的脆弱迭代器，或者另一方面拥有一棵较大的树和小的鲁棒迭代器。

Answer 4

这是一种以速度换空间的交易，从概念上讲这是不必要的，即它是一个实施细节。您始终可以编写一个函数，返回 BST 中任何给定节点的父节点，但调用这样的函数需要时间，仅查找值通常会更快。

如果你不愿意进行交易，可以考虑使用XOR BST，这是一种妥协。