c++ - 使用父指针的二叉搜索树有什么优点？

Question

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

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

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

Answer 1

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

权衡是冗余:如果您修改树的结构(例如通过平衡树)，您必须记住同时更新左/右 和 parent 指针来保持树的一致性。