A Red-Black tree based NavigableMap implementation.
The map is sorted according to the Comparable natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
基于红黑树的实现，有序map，默认为key值的自然排序，或者可以设置排序规则（通过构造器传入Comparable接口实现）。
底层没有数组，只有一棵树。
@Test
public void testTreeMap() {
TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(1, "a");
tm.put(3, "b");
tm.put(2, "c");
System.out.println(tm); // {1=a, 2=c, 3=b}
}
红黑树
红黑树是什么呢？
红黑树是一种特定类型的二叉树，是一种平衡二叉树。是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的，它可以在O(logn)时间复杂度内做查找，插入和删除（这里的n是树中元素的数目）。
二叉查找树
二叉排序树（BinarySortTree），又称二叉查找树、二叉搜索树。
它或者是一棵空树；或者是具有下列性质的二叉树：若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于它的根结点的值；左、右子树也分别为二叉排序树。若子树为空，查找不成功
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
- 性质1. 节点是红色或黑色。
- 性质2. 根节点是黑色。
- 性质3. 每个叶节点是黑色的。 NIL节点或空节点，不包含数据，至少标示树在此终结。
- 性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长(最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长)。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
红黑树学习参考最容易懂的红黑树
TreeMap的实现
- 构造器
// 无参构造器，
public TreeMap() {
comparator = null;
}
构建对象时没有创建map对象(红黑树数据结构)，延迟到第一次put中。之后的put会遵循排序二叉树的原则进行节点的插入，插入后检查是否满足红黑树的规则，进行fixAfterInsertion(e);
public V put(K key, V value) {
Entry<K,V> t = root;
// 第一次put会进入此分支，创建root entry
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<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> 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<? 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);
// 确定是左子节点还是右子节点
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
- 修正树结构
private void fixAfterInsertion(Entry<K,V> x)
private void fixAfterDeletion(Entry<K,V> x)
这两个方法做的事情是树结构改变后的检查和修正，检查树是否满足红黑树的性质，不满足就通过旋转等操作改到满足条件。
看一下fixAfterInsertion:
/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
// 因为要满足红黑树的这五条性质，如果我们插入的是黑色节点，那就违反了性质五，需要进行大规模调整，
// 如果我们插入的是红色节点，那就只有在要插入节点的父节点也是红色的时候违反性质四或者是当插入的节点是根节点时，违反性质二，
// 所以，我们把要插入的节点的颜色变成红色。
// 设置x为红色节点，那就要检查父节点是不是红色的（红色节点不能连续出现）。
x.color = RED;
// 父节点为红色时
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> 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)));
}
// 如果x的父节点是x祖父节点的右子节点
} else {
Entry<K,V> 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;
}
具体关于排序二叉树和二叉树旋转操作以及红黑树的调整，请移步暂时未完成
网友评论