Map - TreeSet & TreeMap - 寻找节点后继

xhz

# 寻找节点后继

对于一棵二叉查找树，给定节点t，其后继(树中比大于t的最小的那个元素)可以通过如下方式找到:

t的右子树不空，则t的后继是其右子树中最小的那个元素。

t的右孩子为空，则t的后继是其第一个向左走的祖先。


后继节点在红黑树的删除操作中将会用到。




TreeMap中寻找节点后继的代码如下:

// 寻找节点后继函数successor()
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {// 1. t的右子树不空，则t的后继是其右子树中最小的那个元素
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {// 2. t的右孩子为空，则t的后继是其第一个向左走的祖先
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}