红黑树 - 如何找到节点的父节点？ [英] Red-black tree - How to find the node's parent?

问题描述

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

In red-black tree, when rotate, you need to know who is the parent of particular node. However, the node only has reference to either right or left child.

我想给一个节点实例变量parent但是因为这个原因我不认为这样做是值得的，而且它也太复杂了每次轮换更改父引用。

I was thinking to give a node instance variable "parent" but just for this reason I don't think it is worth doing so and also it would be too complicated to change parent reference per rotation.

public class Node {
  private left;
  private right;
  private isRed;
  private parent; //I don't think this is good idea
}

所以，我的解决方案是编写使用搜索查找父级的findParent（）方法。我想知道是否有其他方法可以找到节点的父节点？

So, my solution is to write findParent() method that use search to find parent. I am wondering if there is any other way to find a node's parent?

我的解决方案：

示例树：

    50
    / \
   25  75

如果你想找到Node 25的父节点，你可以传递类似的东西：

If you want to find parent of Node 25, you pass something like:

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但是因为这个原因我不认为这样做是值得的

I was thinking to give a node instance variable "parent" but just for this reason I don't think it is worth doing so

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

Having your nodes have a parent reference requires one extra pointer/reference per node. Compare this with needing to traverse the tree whenever you need to know the parent for a given node.

然后在

1. 维护额外引用的成本，并在修改节点时保持最新。


2. 计算成本和必须遍历树以查找给定节点的父节点的复杂性

我认为这两个选项之间的选择有点主观但我个人会选择简单地跟踪父引用。

I think that the choice between these two options is somewhat subjective but personally I would choose to simply keep track of the parent references.

作为参考点， java.util.TreeMap 实现为红黑树，条目包含的节点左，右，父引用。

As a point of reference for you, java.util.TreeMap is implemented as a Red-Black tree which Entry nodes that contain left, right, and parent references.

这篇关于红黑树 - 如何找到节点的父节点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！