带有父指针的二叉查找树有什么优点？

Question

直到此时，我已经实现二叉搜索树与左，右指针，如：

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

我碰到实现中的节点也有指向父节点。你为什么想这么做？什么是折衷？

Answer 1

从一个角度来看，你的问题是有效的，因为parent指针引入了冗余成是在几种情况下可以避免的结构。但是在二叉树的情况下，这会给你带来的巨大好处，即你可以在不记得父节点的地址的情况下向上“跳跃”一级（即从一个节点到它的父节点）。如果节点的父节点是已知的，则几个算法（例如，获得两个值之间的节点数量）可以非常有效和简单地实现。

权衡是冗余：如果你（通过平衡树为例）修改树的结构，你必须记住更新left/right和parent指针既要保证树的一致性。

Answer 2

二叉搜索树指的是一个相当普通类二叉树。 对于二叉搜索树没有理由有父指针。

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

为了满足这些限制，父亲指针就派上用场的时候。当然，它通过交易内存（指针）来提高速度（通过算法查找父项）。

考虑自己喜欢的书上的数据结构，看看如何以及为什么，或维基百科。