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

Question

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

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

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

Answer 1

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

可以在这里找到对红黑树的非常好的描述

http://adtinfo.org/

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

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

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

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