LinuxSir.cn,穿越时空的Linuxsir!

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

Map - TreeSet & TreeMap - 左旋与右旋

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

预备知识


前文说到当查找树的结构发生改变时,红黑树的约束条件可能被破坏,需要通过调整使得查找树重新满足红黑树的约束条件。调整可以分为两类: 一类是颜色调整,即改变某个节点的颜色;另一类是结构调整,即改变检索树的结构关系。结构调整过程包含两个基本操作** : 左旋(Rotate Left),右旋(RotateRight)**。
# 左旋

左旋的过程是将x的右子树绕x逆时针旋转,使得x的右子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。



TreeMap中左旋代码如下:

//Rotate Left
private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

# 右旋

右旋的过程是将x的左子树绕x顺时针旋转,使得x的左子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。



TreeMap中右旋代码如下:

//Rotate Right
private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}


------
原文链接:https://pdai.tech/md/java/collection/java-map-TreeMap&TreeSet.html

本帖子中包含更多资源

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

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

本版积分规则

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