LinuxSir.cn,穿越时空的Linuxsir!

 找回密码
 注册
搜索
热搜: shell linux mysql
查看: 657|回复: 0

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

[复制链接]
发表于 2023-12-26 16:49:15 | 显示全部楼层 |阅读模式

# 寻找节点后继

对于一棵二叉查找树,给定节点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;
    }
}

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
您需要登录后才可以回帖 登录 | 注册

本版积分规则

快速回复 返回顶部 返回列表