文前说明
作为码农中的一员，需要不断的学习，我工作之余将一些分析总结和学习笔记写成博客与大家一起交流，也希望采用这种方式记录自己的学习之旅。
本文仅供学习交流使用，侵权必删。
不用于商业目的，转载请注明出处。
1. 概述
1.1 二叉树
- 树中结点的 最大层次数 称为树的 深度 或高度。
- 结点拥有的 子树数目 称为结点的 度。
- n（n≥0）个结点的有限集合，由 一个根结点 以及两颗 互不相交 的、分别称为 左子树 和 右子树 的二叉树组成。
- 每个结点最多只有两颗子树（不存在 度＞2 的结点）。
- 左子树和右子树次序不能颠倒（有序树）。
- 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
二叉树
二叉树的性质
- 在二叉树的第 i 层上最多有 2i-1 个结点 。（i >= 1）
- 二叉树中如果深度为 k，那么最多有 2k-1 个结点。(k >= 1）
- n0=n2+1，n0 表示度数为 0 的结点数，n2 表示度数为 2 的结点数。
二叉树的遍历
- 假设 L、D、R 分别表示左子树、根结点和右子树， 则对一棵二叉树的遍历有三种情况。
- DLR（称为先根次序遍历，也可以称为前序遍历）
- LDR（称为中根次序遍历，也可以称为中序遍历）
- LRD （称为后根次序遍历，也可以称为后序遍历）
- 前序遍历是 父结点 -> 左子树 -> 右子树。上图输出是 ABDGHICEJF。
- 中序遍历是 左子树 -> 父结点 -> 右子树。上图输出是 GDIHBAEJCF。
- 后序遍历是 左子树 -> 右子树 -> 父结点。上图输出是 GIHDBJEFCA。
平衡二叉树
- 是一棵空树或它的左右两个子树的高度（深度）差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。
二叉查找树
- 左子树上所有结点的值均小于或等于它的根结点的值。
- 右子树上所有结点的值均大于或等于它的根结点的值。
- 左、右子树也分别为二叉排序树。
二叉查找树
- 这种数据结构是通过二分查找的思想，查找所需最大次数等于二分查找树深度（高度）。
- 例如上图查找（10），则分为以下步骤。
- 因为 10 > 9，因此查找右子树。
- 因为 10 < 13，因此查找左子树。
- 因为 10 < 11，因此查找左子树，找到元素 10。
统一定义概念
统一定义概念
- 假设 c 结点为当前结点，b 则为 c 结点的 父结点，d 则为 c 结点的 兄弟结点，e 则为 c 结点的 叔叔结点，a 则为 c 结点的 祖父结点，f 则为 c 结点的 左子结点，g 则为 c 结点的 右子结点。
1.2 红黑树
- 二叉查找树在插入新结点时存在缺陷。
- 假设初始的二叉查找树只有三个结点（9、8、12），然后依次插入结点（7、6、5、4），依照二叉查找树的特性，结果如下图。
- 虽形态符合二叉查找树特性，但是查找性能大打折扣，为了处理这种不平衡现象，则出现了红黑树。
二叉查找树
- 红黑树是一种自平衡二叉查找树，是在插入和删除操作时通过特定的操作保持二叉查找树的平衡，从而获得较高的查找性能，可以在 O(log n) 时间内做查找、插入和删除。
- 红黑树是每个结点都带有颜色属性的二叉查找树，颜色为红色或者黑色。
红黑树的特性
- 特性 1，每个结点都只能是红色或者黑色。
- 特性 2，根结点是黑色。
- 特性 3，每个叶子结点都是黑色的空结点（NIL 结点）。
- 特性 4，每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）。
- 特性 5，从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。（确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对接近平衡的二叉树）
红黑树
- 当红黑树插入新的结点时，很可能规则被破坏，这个时候它会通过一些调整来维持规则。例如下图插入结点（10）没有问题，插入结点（8）就造成规则被破坏。
规则被破坏
- 调整有两种方法，变色 和 旋转。
1.2.1 红黑树的变色操作
- 为了重新符合红黑树的规则，尝试把红色结点变为黑色，或者把黑色结点变为红色。
变色
- 首先，上图中因为结点（8）的插入，造成违反特性（4），因此修改结点（10）为黑色。
- 然后，结点（10）修改为黑色后又违反特性（5），因此修改结点（11）为红色。
- 最后，结点（11）修改为红色后又违反特性（4），因此修改结点（12）为黑色。
1.2.2 红黑树的旋转操作
- 红黑树中对树的平衡可以通过旋转操作来完成，其中旋转分为左旋转和右旋转。
- 左旋转是逆时针旋转红黑树的两个结点，使得父结点被自己的右子结点取代，而自己成为自己的左子结点。
左旋转
- 顺时针旋转红黑树的两个结点，使得父结点被自己的左子结点取代，而自己成为自己的右子结点。
右旋转
1.2.3 红黑树的添加操作
- 第一步，将红黑树当作一颗 二叉查找树，将结点插入。
- 红黑树本身就是一颗二叉查找树，将结点插入后，该树仍然是一颗二叉查找树。
- 第二步，将插入的结点着色为 红色。
- 第二步操作因为有颜色所以满足特性（1），因为不会更改根结点所以满足特性（2），因为插入的是非空结点，所以不会影响满足特性（3）。
- 将插入的结点着色为红色，就不会违背特性（5），意味着需要处理的情况越少。
- 第三步，通过一系列的 旋转 或 着色 等操作，使之重新成为一颗红黑树。
- 第二步操作有可能违背特性（4），因此为了满足特性（4），需要通过第三步将树重新构造为红黑树。
添加结点操作的情况分析
- 根据被插入结点的父结点的情况，可以将 当结点被着色为红色结点，并插入二叉查找树 划分为以下三种情况来处理。
- 情况 1，如果 被插入的结点（N） 是 根结点，直接把此结点 着色 为 黑色（空二叉树）。
情况 1
- 情况 2，如果 N 的 父结点 是 黑色，什么也不需要做。
情况 2
- 如果 N 的 父结点 是 红色，与特性（4）冲突。
- N 一定存在非空的 祖父结点
- N 一定存在 叔叔结点（即使叔叔结点为空，也视之为存在，空结点本身就是黑色结点）。
依据叔叔结点的情况，又可以分为三种情况处理
-
情况 3，当前结点的父结点和叔叔结点都是红色。将 父结点 和 叔叔结点 都着色为黑色，将 祖父结点 着色为红色并设为当前结点（红色结点），即之后继续对当前结点进行操作。
- 经过上面的处理，可能 A 结点的父结点也是红色，这时需要将 A 结点当做新增结点递归处理。
情况 3
-
情况 4，当前结点的父结点是红色，叔叔结点是黑色或者为 NIL，且 N 是其父结点的 右子结点。对 N 和父结点进行一次左旋转。
- 经过上面的处理，还不是平衡的，违反特性（4），需要再进行情况（5）的操作。
情况 4
-
情况 5，当前结点的父结点是红色，叔叔结点是黑色，且当前结点是其父结点的 左子结点。将 父结点 着色为黑色，祖父结点 着色为红色，并以 祖父结点 为支点进行右旋。
- 这种情况有可能是由于情况（4）而产生的，也有可能不是。
情况 5
1.2.4 红黑树的删除操作
- 第一步，将红黑树当作一颗二叉查找树，将该结点从二叉查找树中删除。
- 第二步，通过一系列的 旋转 或 着色 等操作，使之重新成为一颗红黑树。
删除结点操作的情况分析
- 根据待删除结点（N）有几个子结点的情况可以进行分类。
-
情况 1，如果无子结点（红色结点），直接删除 N 即可，不会影响树的结构。
- 该结点只能为叶子结点，它不可能存在子结点，如其子结点为黑，则违反特性（5），为红，则违反特性（4）。
情况 1
- 情况 2，有一个子结点，用该子结点替代 N，然后删除 N 即可。
情况 2
- 有两个子结点，需要找到一个子结点替代 N，然后删除 N 即可，这又分为了 4 种情况。
-
情况 3，N 的兄弟结点 W 为红色的。
- W 为红色，那么其子结点必定全部为黑色，父结点也为黑色。处理策略是修改 W、父结点的颜色，然后以 X 为支点进行一次左旋。
- 这样处理后将情况（3）转变为情况（4）、情况（5）、情况（6）中的一种。
- 若删除图中的 N 结点，将缺少一个黑结点，与红黑树的特性冲突，所以修改 W 颜色为黑色，设置 P 结点为红色，并进行左旋操作，再进行后续的处理。
情况 3
-
情况 4，W 是黑色的，且 W 的两子结点都是黑色的。
- 这种情况其父结点（P）可红可黑，由于 W 为黑色，导致 N 子树相对于其兄弟 W 子树少一个黑色结点，可以将 W 置为红色，使 N 子树与 W 子树黑色结点一致，保持平衡。
- 将 W 由黑转变为红，会导致违反特性，如果 P 为红色，直接将 P 转变为黑色，保持整棵树的平衡。
- 如果 P 为黑色，转变为情况（3）、情况（5）、情况（6）中的一种。
情况 4
-
情况 5，W 是黑色的，W 的左子结点是红色的，右子结点是黑色的。
- 针对这种情况是将 W 和其左子结点进行颜色交换，然后对 W 进行右旋处理。
- 此时 X 是一个有红色右子结点的黑结点，于是将情况（5）转化为情况（6）。
情况 5
-
情况 6，W 是黑色的，W 的右子结点是红色的。
- 交换 W 和父结点（P）的颜色，同时对 P 进行左旋操作。
- 同时将 W 的右子结点 Y 置黑来达到平衡。
情况 6
- 情况（3）～情况（6）是可以互相转换的。
- 情况（4）仅通过一个颜色的转变，减少右子树的一个黑色结点使之保持平衡，同时将不平衡点上移至 N 与 W 的父结点，然后进行下一轮迭代。
- 情况（3）将 W 旋转，将其转成情况（4）、情况（5）、情况（6）进行处理。
- 情况（5）通过转变成情况（6）来进行处理。
- 情况（6）右子结点为红色结点，将缺失的黑色结点交由给右子结点，通过旋转达到平衡。
2. TreeMap 原理
- TreeMap 中的数据是有序的，根据 Entry 中的 key 进行排序，key 比较大小通过比较器 comparator 判断，也可以自定义 comparator，未定义时使用默认比较器，按照 自然顺序 进行排序。
//比较器：可以通过这个对TreeMap的内部排序进行控制
private final Comparator<? super K> comparator;
//TreeMap的红黑结点，内部类
private transient Entry<K,V> root = null;
//map中元素的个数
private transient int size = 0;
//map中结构变动 的次数
private transient int modCount = 0;
//TreeMap的红黑树结点对应的集合
private transient EntrySet entrySet = null;
//keyset的导航类
private transient KeySet<K> navigableKeySet = null;
//键值对的倒序映射
private transient NavigableMap<K,V> descendingMap = null;
2.1 TreeMap 的构造函数
//使用默认构造函数，按照自然顺序进行排序
public TreeMap() {
comparator = null;
}
//创建指定排序的比较器
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
//创建包含指定map的treeMap，按照自然顺序进行排序
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
//将一个指定map中的所有元素复制到新的map中
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator c = ((SortedMap)map).comparator();
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
super.putAll(map);
}
//创建一个map包含指定的比较器
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
private void buildFromSorted(int size, Iterator it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
this.size = size;
root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
it, str, defaultVal);
}
//根据一个已经排好序的map创建一个TreeMap，将map中的元素逐个添加到TreeMap中，并返回map的中间元素作为根结点
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
int redLevel,
Iterator it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
if (hi < lo) return null;
//获取中间元素
int mid = (lo + hi) >>> 1;
Entry<K,V> left = null;
//如果lo小于mid，则递归调用获取mid的左子结点
if (lo < mid)
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
it, str, defaultVal);
//获取mid结点对应的key和value
K key;
V value;
if (it != null) {
if (defaultVal==null) {
Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();
key = entry.getKey();
value = entry.getValue();
} else {
key = (K)it.next();
value = defaultVal;
}
} else { // use stream
key = (K) str.readObject();
value = (defaultVal != null ? defaultVal : (V) str.readObject());
}
//创建middle结点
Entry<K,V> middle = new Entry<>(key, value, null);
//如果当前结点的深度是红色结点的深度，则将结点设置为红色
if (level == redLevel)
middle.color = RED;
//设置middle为left的父结点，left为middle的左子结点
if (left != null) {
middle.left = left;
left.parent = middle;
}
//递归调用获取mid的右子结点
if (mid < hi) {
Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
it, str, defaultVal);
middle.right = right;
right.parent = middle;
}
return middle;
}
-
buildFromSorted()通过递归的方法将每个元素进行关联，为了保证是一颗红黑树，它将中间结点作为 TreeMap 的根结点。
2.2 put 操作
-
put()操作时主要包含以下步骤。- 判断树是否为空，如果为空，直接将当前插入的 k-v 做为根结点完成插入操作。
- 如果树不为空，获取比较器（不管是自定义的比较器还是默认的比较器），对树从根结点开始遍历。
- 如果 k 小于结点的 key，那么开始遍历左子结点，如果大于结点的 key，开始遍历右子结点，如果相等，说明 k 已经存在 TreeMap 当中，则使用新的 value 值覆盖，完成插入操作。
- 如果 k 在 TreeMap 中不存在，将 k 插入到其相应的位置，此时由于树的结构进行了变化，需要检验其是否满足红黑性的元素，调用
fixAfterInsertion()方法。
public V put(K key, V value) {
//用t表示二叉树的当前结点
Entry<K,V> t = root;
//t为null表示一个空树，即TreeMap中没有任何元素，直接插入
if (t == null) {
compare(key, key); // type (and possibly null) check
//将新的key-value键值对创建为一个Entry结点，并将该结点赋予给root
root = new Entry<>(key, value, null);
//容器的size = 1，表示TreeMap集合中存在一个元素
size = 1;
modCount++; //修改次数 + 1
return null;
}
int cmp; //cmp表示key排序的返回结果
Entry<K,V> parent; //父结点
// split comparator and comparable paths
Comparator<? super K> cpr = comparator; //指定的排序算法
//如果cpr不为空，则采用既定的排序算法进行创建TreeMap集合
if (cpr != null) {
do {
parent = t; //parent指向上次循环后的t
cmp = cpr.compare(key, t.key); //比较新增结点的key和当前结点key的大小
//cmp返回值小于0，表示新增结点的key小于当前结点的key，则以当前结点的左子结点作为新的当前结点
if (cmp < 0)
t = t.left;
//cmp返回值大于0，表示新增结点的key大于当前结点的key，则以当前结点的右子结点作为新的当前结点
else if (cmp > 0)
t = t.right;
//cmp返回值等于0，表示两个key值相等，则新值覆盖旧值，并返回新值
else
return t.setValue(value);
} while (t != null);
}
//如果cpr为空，则采用默认的排序算法进行创建TreeMap集合（默认构造方法时cpr为null）
else {
if (key == null) //key值为空抛出异常
throw new NullPointerException();
/* 下面处理过程用compareTo比较和上面一样 */
Comparable<? super K> k = (Comparable<? super K>) 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);
}
//将新增结点当做parent的子结点
Entry<K,V> e = new Entry<>(key, value, parent);
//如果新增结点的key小于parent的key，则当做左子结点
if (cmp < 0)
parent.left = e;
else
//如果新增结点的key小于parent的key，则当做左子结点
parent.right = e;
/*
* 上面已经完成了排序二叉树的的构建，将新增结点插入该树中的合适位置
* 下面fixAfterInsertion()方法就是对这棵树进行调整、平衡
*/
fixAfterInsertion(e);
size++; //TreeMap元素数量 + 1
modCount++; //TreeMap容器修改次数 + 1
return null;
}
-
fixAfterInsertion()方法主要是对二叉树进行左旋转、右旋转和着色的操作，使其保持是一颗红黑树。
private void fixAfterInsertion(Entry<K,V> x) { // Entry<K,V> x表示新增结点
x.color = RED; //新增结点的颜色为红色
//循环 直到 x不是根结点，且x的父结点不为红色
while (x != null && x != root && x.parent.color == RED) {
//如果X的父结点（P）是其父结点的父结点（G）的左结点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//获取X的叔结点(U)
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//如果X的叔结点（U） 为红色（情况三）
if (colorOf(y) == RED) {
//将X的父结点（P）设置为黑色
setColor(parentOf(x), BLACK);
//将X的叔结点（U）设置为黑色
setColor(y, BLACK);
//将X的父结点的父结点（G）设置红色
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
//如果X的叔结点（U为黑色）；这里会存在两种情况（情况四、情况五）
} else {
//如果X结点为其父结点（P）的右子树，则进行左旋转（情况四）
if (x == rightOf(parentOf(x))) {
//将X的父结点作为X
x = parentOf(x);
//右旋转
rotateLeft(x);
}
//（情况五）
//将X的父结点（P）设置为黑色
setColor(parentOf(x), BLACK);
//将X的父结点的父结点（G）设置红色
setColor(parentOf(parentOf(x)), RED);
//以X的父结点的父结点（G）为中心右旋转
rotateRight(parentOf(parentOf(x)));
}
//如果X的父结点（P）是其父结点的父结点（G）的右结点
} else {
//获取X的叔结点（U）
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
//将X的父结点（P）设置为黑色
setColor(parentOf(x), BLACK);
//将X的叔结点（U）设置为黑色
setColor(y, BLACK);
//将X的父结点的父结点（G）设置红色
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
//如果X的叔结点（U为黑色）；这里会存在两种情况（情况四、情况五）
else {
//如果X结点为其父结点（P）的右子树，则进行左旋转（情况四）
if (x == leftOf(parentOf(x))) {
//将X的父结点作为X
x = parentOf(x);
//右旋转
rotateRight(x);
}
//（情况五）
//将X的父结点（P）设置为黑色
setColor(parentOf(x), BLACK);
//将X的父结点的父结点（G）设置红色
setColor(parentOf(parentOf(x)), RED);
//以X的父结点的父结点（G）为中心右旋转
rotateLeft(parentOf(parentOf(x)));
}
}
}
//将根结点G强制设置为黑色
root.color = BLACK;
}
左旋（rotateLeft() 方法）
- 将新增结点（N）当做其父结点（P），将其父结点 P 当做新增结点（N）的左子结点。
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
//获取P的右子结点，其实这里就相当于新增结点N（情况四而言）
Entry<K,V> r = p.right;
//将R的左子树设置为P的右子树
p.right = r.left;
//若R的左子树不为空，则将P设置为R左子树的父亲
if (r.left != null)
r.left.parent = p;
//将P的父亲设置R的父亲
r.parent = p.parent;
//如果P的父亲为空，则将R设置为跟结点
if (p.parent == null)
root = r;
//如果P为其父结点（G）的左子树，则将R设置为P父结点(G)左子树
else if (p.parent.left == p)
p.parent.left = r;
//否则R设置为P的父结点（G）的右子树
else
p.parent.right = r;
//将P设置为R的左子树
r.left = p;
//将R设置为P的父结点
p.parent = r;
}
}
右旋（rotateRight() 方法）
- 将新增结点（N）当做其父结点（P），将其父结点 P 当做新增加点（N）的右子结点。
private void rotateRight(Entry<K,V> p) {
if (p != null) {
//将L设置为P的左子树
Entry<K,V> l = p.left;
//将L的右子树设置为P的左子树
p.left = l.right;
//若L的右子树不为空，则将P设置L的右子树的父结点
if (l.right != null)
l.right.parent = p;
//将P的父结点设置为L的父结点
l.parent = p.parent;
//如果P的父结点为空，则将L设置根结点
if (p.parent == null)
root = l;
//若P为其父结点的右子树，则将L设置为P的父结点的右子树
else if (p.parent.right == p)
p.parent.right = l;
//否则将L设置为P的父结点的左子树
else
p.parent.left = l;
//将P设置为L的右子树
l.right = p;
//将L设置为P的父结点
p.parent = l;
}
}
着色（setColor() 方法）
- 改变该结点的颜色，在红黑树中，它是依靠结点的颜色来维持平衡的。
private static <K,V> void setColor(Entry<K,V> p, boolean c) {
if (p != null)
p.color = c;
}
2.3 remove 操作
- 在对 TreeMap 进行删除操作的时候，由于结点结构的变化也可能使得树不满足红黑树的结构，这时候也需要对树进行调整，同样是删除结点之后，调整红黑树，而在这里删除一个结点并不是真正的删除，而是在树中根据一定的规则找到一个结点来替代删除结果，然后再删除替代结点，例如删除结点 A，找到 A 的替代结点 B，这时候将 B 的k、v值覆盖 A 的 k、v 值，然后删除 B 结点。而替代结点的规则是：右分支的最左边，或者左分支的最右边（也就是大于当前 k 的最小值的结点）。
//根据key值删除一个结点，并返回删除的结点
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
//删除一个结点
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
//如果该结点的左子结点和右子结点均不为空，找到p的后继结点，将后继结点的key和value替代p的key和value,然后将p赋值为s
//这一步就是将删除p结点的操作改为删除替代结点的操作
if (p.left != null && p.right != null) {
//返回p的对应的后继结点，将
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
//如果p有左子结点，找到左子结点，否则用右子结点
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//replacement不为空的话
if (replacement != null) {
//将p的父结点设置为replacement的父结点
replacement.parent = p.parent;
//如果p就是根结点，那么replacement设置为根结点
if (p.parent == null)
root = replacement;
else if (p == p.parent.left) //如果p是其父结点的左子结点，将replacement设置为其父结点的左子结点
p.parent.left = replacement;
else
p.parent.right = replacement; //否则将replacemnet设置为p的父结点右子结点
//将p结点置为null，结点删除了
p.left = p.right = p.parent = null;
//如果p结点是黑色的，那么需要对树进行调整
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) {
root = null; //如果p是空结点，则树是空的
} else {
//如果p结点是黑色的，需要对树进行调整
if (p.color == BLACK)
fixAfterDeletion(p);
//如果p的父结点不为空，
if (p.parent != null) {
//p为其父结点的左子结点，将其父结点的左子结点置为空
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
//返回结点t的后继结点，返回大于t的最小的结点
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
//t为null，返回null
if (t == null)
return null;
else if (t.right != null) { //t的右子结点不为空
//设置p为t的右子结点
Entry<K,V> p = t.right;
//开始遍历p的左子树，返回左子树中最后一个结点
while (p.left != null)
p = p.left;
return p;
} else { //如果t的右子结点为空
//设置p的t的父结点
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
//循环，如果ch是p的右子结点，一直向上查找
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
- 删除结点过程后调用
fixAfterDeletion()方法，因为在删除结点后也可能导致树不平衡，该方法主要是在删除操作之后调整树的平衡。
//删除结点树调整
private void fixAfterDeletion(Entry<K,V> x) {
//循环遍历树，x不是根结点，x的颜色是黑色的
while (x != root && colorOf(x) == BLACK) {
//x是其父结点的左子结点
if (x == leftOf(parentOf(x))) {
//sib为x的的兄弟结点
Entry<K,V> sib = rightOf(parentOf(x));
//sib为红色时，将sib设置为黑色、x的父结点设置为红色，左旋转x的父结点，sib设置为x的父结点的右子结点
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
//如果sib的两子结点都是黑色的，将sib设置为红色，x设置为s的父结点
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {//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));
}
//sib结点的颜色设置为x的父结点的颜色
setColor(sib, colorOf(parentOf(x)));
//x的父结点的颜色设置为黑色
setColor(parentOf(x), BLACK);
//sib的右子结点的颜色设置为黑色
setColor(rightOf(sib), BLACK);
//左旋转x的父结点
rotateLeft(parentOf(x));
//根结点赋值为x
x = root;
}
} else { //x是其父结点的右子结点
//sib为x的兄弟结点
Entry<K,V> sib = leftOf(parentOf(x));
//sib为红色时，设置sib颜色为黑色，x的父结点为红色，右旋转x的父结点，sib设置为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);
}
2.4 总结
- TreeMap 中的键值对是有序的，按照自然顺序或者自定义的顺序。
- TreeMap 中的如果是默认比较器，其 key 值不能为空。
- TreeMap 是基于红黑树实现的，每次对结构进行改变时，都需要进行检验是否仍然保持平衡。
- TreeMap 是非线程安全的。
参考资料
https://blog.csdn.net/zhangyuan19880606/article/details/51234420/
https://blog.csdn.net/qq_41786692/article/details/79940660
网友评论