之前几篇博客写了关于HashMap源码的分析，到现在就只剩关于红黑树的部分。红黑树是一种数据结构，它是基于二叉查找树的。红黑树很好的继承了二叉查找树快速插入删除以及查找元素的特性，又因为红黑树自平衡，所以又克服了二叉查找树在输入线性数据时退化为链表的缺点，因此被广泛使用。
java version 1.8
1. 红黑树的特性
红黑树，顾名思义，有一个特征就是树的节点要么是红色，要么是黑色。而其本身又是自平衡的二叉查找树，除了满足二叉查找树的特征之外，还应满足以下特征，来保证自平衡性。
- 根节点为黑色
- 叶子节点为黑色的null节点
- 红色节点的子节点必为黑色，反之则未必
- 从叶子节点到根节点的每条路径上的黑色节点数目相同
红黑树在插入节点时，通过这些特性来保持自身的平衡性。而保持平衡性的操作主要有三个，改变节点颜色，左旋，右旋。
-
左旋
左旋示意图
-
右旋
右旋示意图
红黑树插入节点时默认插入的节点为红色，这是因为插入红色节点破坏自平衡特性的概率要比插入黑色节点破坏的概率低。
2. 链表转红黑树
惯例，先看源码
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
TreeNode是HashMap的内部类，继承自LinkedHashMap.Entry，而LinkedHashMap.Entry继承自HashMap的Node类。它的几个属性parent指向红黑树中的父节点，left和right分别指向左右孩子节点，prev指向原链表中的上一个节点。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
当hashmap数组中某位置链表的长度大于等于7时，该链表就被转化为红黑树，使用treeifyBin方法。
这个方法的作用是将链表的每个节点都转化为红黑树节点，并将单链表转化为双链表。之后使用treeify方法将双链表转化为红黑树。
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
treeify方法遍历双链表的每个节点，将每个节点插入到二叉查找树中，每插入一个节点，调用一次balanceInsertion方法，为红黑树做插入平衡处理。
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
// 当前红黑树为空，插入的节点作为根节点
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
// 当前插入节点的祖父节点为根节点，父节点为黑色。直接插入即可
return root;
if (xp == (xppl = xpp.left)) {
// 父节点是祖父节点的左子节点
if ((xppr = xpp.right) != null && xppr.red) {
// xppr是叔叔节点，父节点和叔叔节点均为红色，给节点变色，然后将其祖父节点置为当前节点
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.right) {
// 父节点为红色，叔叔节点为黑色，当前节点为右子节点时，对父节点做左旋操作
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
// 此时当前节点父节点为红色，祖父节点为黑色，当前节点为左子节点
// 将父节点涂黑，祖父节点涂红，对祖父节点做右旋
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else {
// 父节点是祖父节点的右子节点，具体情况与上边类似
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
balanceInsertion方法参数中root是红黑树的根节点，x是当前插入的节点。从源码中可以看出，插入的节点默认置为红色。
3. 红黑树删除节点
惯例，先看代码
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
// 判空
return;
int index = (n - 1) & hash;
// first是红黑树的第一个节点，succ是当前节点在hashmap链表中的后一个节点
// pred是在hashmap链表中的前一个节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null)
// 前一个结点为空，说明当前节点是根节点
tab[index] = first = succ;
else
// 将前一个节点的后继指向后一个节点，也即删除链表中的这个节点
pred.next = succ;
if (succ != null)
// 节点后继的前驱指向前一个节点，双链表删除操作完成
succ.prev = pred;
if (first == null)
return;
if (root.parent != null)
root = root.root();
if (root == null
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
tab[index] = first.untreeify(map); // too small
return;
}
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {// 左右子树均不为空
TreeNode<K,V> s = pr, sl;
while ((sl = s.left) != null) // 右子树的最左节点
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
//p是待删除节点
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
(root = replacement).red = false;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
// 删除节点为红色，红黑树平衡违背破坏
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
// 删除节点p
if (replacement == p) { // detach
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
moveRootToFront(tab, r);
}
这个方法是删除二叉查找树中的节点，平衡红黑树在balanceDeletion方法中。
就先到这里，具体逻辑下一次再分析。
学疏才浅，有不当之处，望指出。
网友评论