具有父指针的二叉搜索树有什么优势？

Question

到目前为止,我一直用左右指针实现二叉搜索树,如:

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

我遇到了节点也有父节点指针的实现.你为什么想这么做？有什么权衡取舍？

Answer 1

从一个角度来看,你的问题是有效的,因为parent指针在结构中引入了冗余,这在几种情况下是可以避免的.但是在二叉树的情况下,这会给你带来巨大的好处,你可以跳到一个级别(即从一个节点到它的父节点)而不记住父节点的地址.如果已知节点的父节点,则可以非常有效且简单地实现若干算法(例如,获得两个值之间的节点数).

权衡是冗余:如果您修改树的结构(例如通过平衡树),您必须记住更新指针left/right和parent指针以保持树的一致性.

Answer 2

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

然而，二叉树还有更专门的变体，其中父指针是有益的。例如，寻找AVL 树或红黑树。这些专门化对树的布局施加了进一步的限制，以实现各种目标，例如通过确保树始终平衡来保证红黑树O(log n)中查找/插入/删除的复杂性。

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

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