3

在红黑树中,当旋转时,您需要知道谁是特定节点的父节点。但是,该节点仅具有对右子或左子的引用。

我想给一个节点实例变量“父级”,但正是出于这个原因,我认为这样做不值得,而且每次旋转更改父级引用也太复杂了。

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; 
            }
        }
    }
4

5 回答 5

3

我想给一个节点实例变量“父”,但正是出于这个原因,我认为这样做不值得

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

那么这是一个权衡

  1. 维护额外参考并在您修改节点时使其保持最新的成本。
  2. 必须遍历树以找到给定节点的父节点的计算成本和复杂性

我认为这两个选项之间的选择有点主观,但我个人会选择简单地跟踪parent参考。

作为您的参考点,java.util.TreeMap它被实现为一个红黑树,其中Entry包含leftrightparent引用的节点。

于 2010-07-27T19:15:46.097 回答
3

父指针的使用是可选的。如果您放弃父指针,那么您将不得不使用递归编写插入/删除操作(递归方法调用将父信息保存在堆栈上)或编写一个迭代版本,该版本在向下移动时维护自己的父堆栈。

可以在此处找到对红黑树的非常好的描述

http://adtinfo.org/

这包括对许多 rbtree 实现的描述,包括有和没有父指针。

如果您确实想节省空间(这很公平),可以在此处找到对 rbtree 实现的非常出色的描述

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

如果由插入/删除实现使用,您描述的用于搜索节点父级的方法将非常低​​效。使用指针或使用递归。

于 2015-10-17T21:39:29.377 回答
2

当您遍历树以到达您的枢轴节点时,您可以缓存前一个父节点,或者如果您需要多个级别的“撤消”,您可以将每个遍历的节点缓存到堆栈中。

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

于 2010-07-27T19:27:44.977 回答
1

存储父级肯定比查找它更好。更新父引用并不复杂。

于 2010-07-27T19:15:06.253 回答
0

除了父指针和再次查询父节点之外,另一个解决方案是维护祖先堆栈。

假设有人希望将 23 插入以下树:

红黑树

通常要插入的算法是:

  1. 如果它在树中,则查找 23 所在的节点

  2. 如果 23 已经存在,则返回失败

  3. 如果 23 还没有,把它放在那里。

  4. 根据需要运行重新平衡/着色程序。

现在,要使用堆栈方法,您分配一个足够大的堆栈以支持树的每一级一个节点(我认为 2 * Ceiling(Log2(count)) + 2) 应该已经涵盖了。您甚至可以保留为插入或删除分配的堆栈,并在开始插入时将其清除。

所以——看根。将其推入堆栈。23 大于根中的值,所以向右走。现在将节点当前节点(值 21)推入堆栈。如果 23 在树中,它必须在当前节点的右侧。但是当前节点右侧的节点是一个空哨兵。因此,该 null-sentinel 应替换为具有您的值的节点。父项是堆栈顶部的项目(最近推送),祖父母是下一个......等。因为你似乎正在学习...... Java为你提供了一个堆栈接口,所以你不需要开发自己的堆栈来做到这一点。就用他们的。

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

于 2017-07-02T23:55:58.273 回答