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包含left、right和parent引用的节点。

于 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 回答