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