红黑树 – 如何找到节点的父节点？
在红黑树中，旋转时，您需要知道谁是特定节点的父节点。 但是，节点仅引用右子或左子。
我正在考虑给一个节点实例变量“parent”，但仅仅因为这个原因我不认为这样做是值得的，而且每次轮换更改父引用也太复杂了。
public class Node { private left; private right; private isRed; private parent; //I don't think this is good idea } 所以，我的解决方案是编写使用搜索查找父级的findParent（）方法。 我想知道是否有其他方法可以找到节点的父节点？
我的解决方案
样本树：
50 / \ 25 75
如果要查找节点25的父节点，则传递类似于：
Node parent = findParent(Node25.value);
它返回node50。
protected Node findParent(int val) { if(root == null) { return null; } Node current = root; Node parent = current; while(true) { if(current.val == val) { //found return parent; } if(current == null) { //not found return null; } parent = current; if(current.val > val) { //go left current = current.left; } else { //go right current = current.right; } } }
我正在考虑给一个节点实例变量“parent”，但正因为这个原因我不认为这样做是值得的
让节点具有parent引用需要每个节点一个额外的指针/引用。 将此与需要在需要知道给定节点的父节点时遍历树进行比较。
这是之间的权衡
- 维护额外引用的成本，并在修改节点时使其保持最新。
- 必须遍历树以查找给定节点的父节点的计算成本和复杂性
我认为这两个选项之间的选择有点主观，但我个人会选择简单地跟踪parent引用。
作为参考， java.util.TreeMap实现为红黑树，其中Entry节点包含left ， right和parent引用。
当您遍历树以到达您的枢轴节点时，您可以缓存前一个父节点，或者如果您需要多个级别的“撤消”，则可以将每个遍历节点缓存到堆栈上。
此缓存将是您的旋转算法的本地变量，因此它不需要树中的任何更多空间或昂贵的额外遍历。
存储父母比查找它更好。 更新父引用并不复杂。
父指针的使用是可选的。 如果放弃父指针，那么你将不得不使用递归来编写插入/删除操作（递归方法调用保留堆栈上的父信息）或编写一个迭代版本，当它向下移动树时，它保持自己的父堆栈。
这里可以找到非常好的红黑树的描述
这包括许多rbtree实现的描述，包括有和没有父指针。
如果你确实想节省空间（这是公平的），可以在这里找到rbtree实现的非常好的描述
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
如果插入/删除实现使用，那么您描述的用于搜索节点父节点的方法效率非常低。 使用指针或使用递归。
除了父指针和再次查询父节点之外，另一个解决方案是维护祖先堆栈。
假设有人希望将23插入到以下树中：
红黑树
通常，要插入的算法是：
-
查找节点，如果它在树中，则为23
-
如果23已经存在，则返回失败
-
如果23还没有，请把它放在那里。
-
根据需要运行您的重新平衡/着色程序。
现在，要使用堆栈方法，您需要分配一个足够大的堆栈，以支持每个树级别的一个节点（我认为2 * Ceiling（Log2（count））+ 2）应该覆盖您。 您甚至可以保留为插入或删除分配的堆栈，并在开始插入时清除它。
所以 – 看看根。 将其推入堆栈。 23大于根中的值，所以右转。 现在将节点当前节点（值21）推入堆栈。 如果23在树中，则它必须位于当前节点的右侧。 但是当前节点右侧的节点是空哨兵。 因此，应该用具有您的值的节点替换该null-sentinel。 父级是堆栈顶部的项目（最近推送），祖父母是下一个……等等。因为你似乎在学习… Java为你提供了一个堆栈接口所以你不需要开发自己的堆栈来做到这一点。 只需使用他们的。
至于这是否比父指针方法更好，这对我来说似乎有争议 – 我将倾向于父指针方法以简化并消除维护辅助数据结构或广泛使用递归的需要。 也就是说，在应用重新平衡/着色例程时，任何一种方法都比查询当前节点的父节点要好。