红黑树 - 如何找到节点的父节点？

在红黑树中，旋转时，您需要知道谁是特定节点的父节点。但是，节点只能引用右侧或左侧的子节点。红黑树 - 如何找到节点的父节点？

我想给一个节点实例变量“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; 
      } 
     } 
    }

来源

2010-07-27 masato-san

我可能是错的，但我认为通常的办法是通过母公司的调用堆栈的旋转功能上的一个参数。 – mikera 2010-07-27 19:13:10

你应该看看libavl。正确的方法是在搜索时将祖先保存在堆栈中。 – user172818 2012-05-22 13:58:26

我想给一个节点实例变量“父”，但只是为了这个原因，我不认为这是值得这样做

有您的节点有parent参考需要一个额外的指针/每个节点的参考。当需要知道给定节点的父节点时，将此与需要遍历树进行比较。

这是再

保持一个额外的参考，并保持高达只要您修改节点日期的成本之间的权衡。
不必遍历树以查找一个给定节点的父

我认为，这两个选项之间的选择是有点主观的，但我个人会选择简单地保持跟踪的计算成本和复杂性parent参考。

至于你一个参考点，java.util.TreeMap实现为一个红黑树包含left，right和parent引用其Entry节点。

来源

2010-07-27 19:15:46

我不认为这些都是主观的。如果你打算远离拥有R-B树，那可能是因为你为了追求更快的操作而愿意牺牲一些东西。如果你为了记忆而苦苦挣扎，为什么不使用数组呢？ – 2010-07-27 19:25:09

那么，我认为有一些算法，你可以说，不必维护数据结构的权衡是值得的，因为计算复杂度的小幅增加。我个人认为这不是其中之一。我只是想避免给出一个广泛的答案。 – 2010-07-27 19:28:22

这对存储父母来说比查找它更好。更新父引用并不那么复杂。

来源

2010-07-27 19:15:06 unbeli

当你遍历树来到你的pivot节点时，你可以缓存前一个父节点，或者如果你需要多个级别的“undo”，你可以缓存每个遍历节点到堆栈上。

此缓存将是您的旋转算法的本地变量，因此它不需要树中的更多空间或昂贵的额外遍历。

来源

2010-07-27 19:27:44 joshperry

使用父指针是可选的。如果你放弃了父指针，那么你将不得不使用递归来编写插入/删除操作（递归方法调用保存堆栈上的父信息），或者编写一个迭代版本，在父树向下移动时维护它自己的父级栈。

一个很好的红黑树的描述可以在这里

http://adtinfo.org/

，其中包含很多rbtree实现，包括有和无父指针的描述中找到。

如果你想节省空间（这是不够公平）的rbtree实现一个真正优秀的描述可以在这里

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx

已用于搜索节点的描述的方法发现如果插入/删除实现使用父级，则效率非常低。使用指针或使用递归。

来源

2015-10-17 21:39:29

另一种解决方案，除了父指针和再次查询父项，是维护一个祖先堆栈。

假如有人想插入23划分为以下三种：

Red Black Tree

一般插入算法是：

其中23是如果它是在树

查找节点
如果23已经存在，返回失败
如果23不在那里，就把它放在那里。
根据需要运行您的重新平衡/着色程序。

现在，使用协议栈的方法，你分配一个堆栈大到足以支持每个你的树的一级节点（我认为2 *天花板（LOG 2（数））+ 2）应该有你覆盖。你甚至可以保留一个分配给插入或删除的堆栈，只要你开始插入就清除它。

所以 - 看看根。将它推入堆栈。 23大于根中的值，所以向右走。现在将节点当前节点（值21）推入堆栈。如果23在树中，它必须在当前节点的右侧。但是当前节点右侧的节点是空标记。因此，应该用具有您的价值的节点替换空标记。父项是堆栈顶部的项目（最近被推送），祖父项是下一行...等等。因为你好像在学习...... Java为你提供了一个堆栈接口，所以你不需要开发自己的堆栈来做到这一点。只要使用他们的。

至于这是否比父指针方法更好，这似乎对我来说是有争议的 - 为了简单起见，我会倾向于父指针方法，并且不需要维护辅助数据结构或广泛使用递归。也就是说，任何一种方法都比在应用重新平衡/着色例程时查询当前节点的父节点要好。

来源

2017-07-02 23:55:58

红黑树 - 如何找到节点的父节点？

回答

相关问题