参考资料：
《Map - TreeSet & TreeMap 源码解析》
《TreeMap和红黑树》
《关于红黑树(R-B tree)原理》
写在开头：本文为个人学习笔记，内容比较随意，夹杂个人理解，如有错误，欢迎指正。
目录
一、基础概念
1、概述
2、基础属性
二、红黑树
1、红黑树的起源
1.1、二叉搜索树
1.2、平衡二叉树
2、红黑树的基本性质
3、红黑树的平衡 *** 作
三、核心方法
1、查找
2、 新增
3、删除
四、树的维护
1、寻找直接后继
2、插入后调整
3、删除后调整
一、基础概念 1、概述
我们可以通过下图的类继承关系看出TreeMap和HashMap都是Map接口的实现类。 在之前的文章中，我们介绍了HashMap，在其中我们有提到，其内部结构是table数组+链表（在一定条件下会转换为红黑树）结构，而在TreeMap中，没有了table数组也没有链表，直接就是基于红黑树实现的结构（直白一点就是TreeMap=红黑树），并且可以根据初始化时传入的比较器来实现自定义的排序。
2、基础属性TreeMap是基于红黑树实现的，因此它的每一个节点都带有颜色（红黑树的基础属性，后面会介绍）。
注意这里新节点初始化时默认黑色（实际上只有根节点默认黑色，其它节点在新增时都会触发调整方法fixAfterInsertion，此时会调整节点的）。
// 自定义的比较器
private final Comparator comparator;
// 红黑树的根节点
private transient Entry root;
// 红黑树的节点包含左右孩子节点、父节点及该节点颜色
static final class Entry implements Map.Entry {
K key;
V value;
Entry left;
Entry right;
Entry parent;
boolean color = BLACK;
Entry(K key, V value, Entry parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
// 其余方法省略
...
} 再来看下TreeMap的构造方法，TreeMap由于实现了SortedMap接口，因此具备了自由实现排序顺序的功能，我们可以看到第二个构造方法中可以手动传入一个比较器，我们自定义的排序顺序即使基于此完成的。
// 默认构造方法，如果不自定义比较器，则使用传入类型的自然顺序比较
// 比如String就是逐个比较字符的Ascll码
public TreeMap() {
comparator = null;
}
// 可传入自定义的构造器以获得想要的排序结果
public TreeMap(Comparator comparator) {
this.comparator = comparator;
}
// 下面2种都是基于其他的集合转换过来的TreeMap
public TreeMap(Map m) {
comparator = null;
putAll(m);
}
public TreeMap(SortedMap m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
下面演示下TreeMap自定义排序顺序的使用。
public static void sortByValue() {
Map map = new TreeMap(new Comparator(){
@Override
public int compare(String a,String b){
return a.compareTo(b);
}
});
map.put("a", "dddd");
map.put("d", "aaaa");
map.put("b", "cccc");
map.put("c", "bbbb");
List> list = new ArrayList>(map.entrySet());
for (Entry e: list) {
System.out.println(e.getKey()+":"+e.getValue());
}
} 在数据结构种，我们知道二叉搜索树（BST）可以实现有序数组的快速查找，但是它存在一个漏洞，即当创建时数组已基本有序，这个时候创建出来的二叉搜索树将呈现链式结构。此时二叉搜索树的查找性能将大打折扣。
1.2、平衡二叉树为了避免这种情况，我们需要让整棵树尽量保持平衡，即每个节点的左右子树高度差不超过1，这就是平衡二叉树（AVL树）。平衡二叉树的实现是依靠在每次插入和删除节点时，都对左右子树的高度做检查，如果出现高度差大于1的情况，则需要做相应的调整，以此来保证整棵树的平衡。
二叉平衡树有效的确保了查找的效率保持在O(logN)的复杂度内，但由于非常严格的平衡限制（每个节点的左右子树高度差不超过1），每次插入和删除都需要检查节点，并可能对整棵树做出调整， 这对性能造成了比较大的影响。于是我们又对平衡二叉树做出了调整，即放弃了高度差不超过1的限制，转而通过一套特殊的机制保证整棵树的相对平衡即可，这样既能保证整棵树不偏向链式结构，影响查找效率，也减小了树在调整时付出的时间代价，这就是我们下面要讲的红黑树。
2、红黑树的基本性质（1）每个节点要么是红色，要么是黑色
（2）根节点必须是黑色
（3）红色节点不能连续(也即是，红色节点的孩子和父亲都不能是红色)。
（4）对于每个节点，从该点至null(树尾端)的任何路径，都含有相同个数的黑色节点。
3、红黑树的平衡 *** 作红黑树为了实现树的平衡（即满足上面讲的4个性质），提供了3种基本 *** 作，分别为变色、左旋、右旋，所有的复杂 *** 作都是基本这三个 *** 作实现的。变色，即是将节点的颜色由红转黑或者由黑转红，很容易理解。重点在于左旋与右旋。
左旋：逆时针旋转两个节点，让一个节点被其右子节点取代，而该节点成为右子节点的左子节点。下图中演示了左旋的 *** 作顺序，首先断开节点PL与右子节点G的关系，同时将其右子节点的引用指向节点C2；然后断开节点G与左子节点C2的关系，同时将G的左子节点的应用指向节点PL。
左旋在TreeMap种的实现如下（TreeMap中红黑树比较的是每个Entry节点的key）：
//Rotate Left
private void rotateLeft(Entry p) {
if (p != null) {
// 记录下p节点的右孩子r，用r的左孩子代替原来的右孩子
Entry r = p.right;
p.right = r.left;
// 新的左孩子与p建立父子关系
if (r.left != null)
r.left.parent = p;
// 初始右孩子r的父节点调整为p的父节点，即取P的位置
r.parent = p.parent;
// 特殊情况，p即为根节点
if (p.parent == null)
root = r;
// 下面两步负责确认p与其父节点的位置关系（p是左孩子还是右孩子），以便赋值给r
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
// 完成剩余 *** 作
r.left = p;
p.parent = r;
}
}
右旋：顺时针旋转两个节点，让一个节点被其左子节点取代，而该节点成为左子节点的右子节点。下图中演示了右旋的 *** 作顺序，首先断开节点G与左子节点PL的关系，同时将其左子节点的引用指向节点C2；然后断开节点PL与右子节点C2的关系，同时将PL的右子节点的应用指向节点G。
右旋在TreeMap种的实现如下：
//Rotate Right
private void rotateRight(Entry p) {
if (p != null) {
// 记录下p节点的左孩子l，用l的右孩子代替原来的左孩子
Entry l = p.left;
p.left = l.right;
// 新的右孩子与p建立父子关系
if (l.right != null) l.right.parent = p;
// 初始左孩子l的父节点调整为p的父节点，即取P的位置
l.parent = p.parent;
// 特殊情况，p即为根节点
if (p.parent == null)
root = l;
// 下面两步负责确认p与其父节点的位置关系（p是左孩子还是右孩子），以便赋值给l
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
// 完成剩余 *** 作
l.right = p;
p.parent = l;
}
}
查找相对简单，红黑树是基于二叉搜索树的变形，因此我们可以利用二分查找的性质来找到相应节点。因为查找不涉及节点的变更，因此不需要维护。唯一需要注意的是，TreeMap会根据初始化时是否传入了比较器来判断选用哪种比较器来比较，如果初始化时未提供，则使用key的自然顺序。
public V get(Object key) {
Entry p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry getEntry(Object key) {
// 如果比较器不为空，则使用自定义的比较器来查找
if (comparator != null)
return getEntryUsingComparator(key);
// 对Key做非空判断
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
// 使用key默认的比较器排序查找
Comparable k = (Comparable) key;
Entry p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
// 与默认的查找顺序大致相似，区别在于使用自定义的比较器
final Entry getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator cpr = comparator;
if (cpr != null) {
Entry p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
} put方法不难理解，还是基于二叉搜索树的 *** 作，难点在最后对红黑树性质的维护 *** 作。
public V put(K key, V value) {
Entry t = root;
// 空树则直接新增节点
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry parent;
// 按照正常情况进行二分查找，若找到，则直接更新value即可
Comparator cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable k = (Comparable) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 没有找到，则需要新增节点
Entry e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 新增后对红黑树进行调整
fixAfterInsertion(e);
size++;
modCount++;
return null;
} 一棵普通二叉查找树的删除过程，可以简单分为两种情况:
（1）删除点p的左右子树都为空，或者只有一棵子树非空。
（2）删除点p的左右子树都非空。
对于上述情况1，处理起来比较简单，直接将p删除(左右子树都为空时)，或者用非空子树替代p(只有一棵子树非空时)；对于情况2，可以用p的后继s(树中大于x的最小的那个元素)代替p，然后使用情况1删除s。
public V remove(Object key) {
Entry p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
private void deleteEntry(Entry p) {
modCount++;
size--;
// 删除点p的左右子树都非空，直接根据二叉搜索树的性质将后续节点填补上来
if (p.left != null && p.right != null) {
Entry s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
// 找到用来替换的节点（如果上文已经使用后继节点替换，则需要删除的就是后继节点）
Entry replacement = (p.left != null ? p.left : p.right);
// 至少有一个子节点不为null，直接用这个有值的节点替换掉当前节点，给replacement的parent属性赋值,给
// parent节点的left属性和right属性赋值，同时要记住叶子节点必须为null,然后用fixAfterDeletion方法
// 进行自平衡处理
if (replacement != null) {
//将待删除节点的子节点挂到待删除节点的父节点上。
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
// p如果是红色节点的话，那么其子节点replacement必然为红色的，并不影响红黑树的结构
// 但如果p为黑色节点的话，那么其父节点以及子节点都可能是红色的，那么很明显可能会存在红色相连的情
// 况，因此需要进行自平衡的调整
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) {
root = null;
} else {
// 如果p节点为黑色，那么p节点删除后，就可能违背每个节点到其叶子节点路径上黑色节点数量一致的规则，
// 因此需要进行自平衡的调整
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
对于一棵二叉查找树，给定节点t，其后继(树中比大于t的最小的那个元素)可以通过如下方式找到:
- t的右子树不空，则t的后继是其右子树中最小的那个元素。
- t的右孩子为空，则t的后继是其第一个向左走的祖先。
// 寻找节点后继函数successor()
static TreeMap.Entry successor(Entry t) {
if (t == null)
return null;
else if (t.right != null) {
// t的右子树不空，则t的后继是其右子树中最最左侧节点
Entry p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
// t的右孩子为空，则t的后继是其祖先中第一个左子树遍历完的节点
Entry p = t.parent;
Entry ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
private void fixAfterInsertion(Entry x) {
//新插入的节点为红色节点
x.color = RED;
//我们知道父节点为黑色时，并不需要进行树结构调整，只有当父节点为红色时，才需要调整
while (x != null && x != root && x.parent.color == RED) {
//如果父节点是左节点，对应上表中情况1和情况2
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry y = rightOf(parentOf(parentOf(x)));
//如果叔父节点为红色，对应于“父节点和叔父节点都为红色”，此时通过变色即可实现平衡
//此时父节点和叔父节点都设置为黑色，祖父节点设置为红色
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
//如果插入节点是黑色，插入的是右子节点，通过【左右节点旋转】（这里先进行父节点左旋）
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
//设置父节点和祖父节点颜色
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
//进行祖父节点右旋（这里【变色】和【旋转】并没有严格的先后顺序，达成目的就行）
rotateRight(parentOf(parentOf(x)));
}
} else {
//父节点是右节点的情况
Entry y = leftOf(parentOf(parentOf(x)));
//对应于“父节点和叔父节点都为红色”，此时通过变色即可实现平衡
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
//如果插入节点是黑色，插入的是左子节点，通过【右左节点旋转】（这里先进行父节点右旋）
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
//进行祖父节点左旋（这里【变色】和【旋转】并没有严格的先后顺序，达成目的就行）
rotateLeft(parentOf(parentOf(x)));
}
}
}
//根节点必须为黑色
root.color = BLACK;
} private void fixAfterDeletion(Entry x) {
/**
* 当x不是root节点且颜色为黑色时
*/
while (x != root && colorOf(x) == BLACK) {
/**
* 首先分为两种情况，当前节点x是左节点或者当前节点x是右节点，这两种情况下面都是四种场景,这里通过
* 代码分析一下x为左节点的情况，右节点可参考左节点理解，因为它们非常类似
*/
if (x == leftOf(parentOf(x))) {
Entry sib = rightOf(parentOf(x));
/**
* 场景1：当x是左黑色节点，兄弟节点sib是红色节点
* 兄弟节点由红转黑，父节点由黑转红，按父节点左旋，
* 左旋后树的结构变化了，这时重新赋值sib，这个时候sib指向了x的兄弟节点
*/
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
/**
* 场景2：节点x、x的兄弟节点sib、sib的左子节点和右子节点都为黑色时，需要将该节点sib由黑变
* 红，同时将x指向当前x的父节点
*/
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
/**
* 场景3：节点x、x的兄弟节点sib、sib的右子节点都为黑色，sib的左子节点为红色时，
* 需要将sib左子节点设置为黑色，sib节点设置为红色，同时按sib右旋，再将sib指向x的
* 兄弟节点
*/
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
/**
* 场景4：节点x、x的兄弟节点sib都为黑色，而sib的左右子节点都为红色或者右子节点为红色、
* 左子节点为黑色，此时需要将sib节点的颜色设置成和x的父节点p相同的颜色，
* 设置x的父节点为黑色，设置sib右子节点为黑色，左旋x的父节点p，然后将x赋值为root
*/
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else {//x是右节点的情况
Entry sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
} 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）