HashMap小探（三）之红黑树
2019-01-12 本文已影响13人
AlanKim
HashMap中的红黑树
红黑树
平衡二叉查找树
红黑树是一种平衡二叉查找树(Binary Search Tree)的实现，先看看二叉查找树的概念如下：
- 为空树，或者具有以下特性的二叉树
- 左子树上的所有节点，若不为空，则全都小于根节点
- 右子树上的所有节点，若不为空，则全都大于根节点
- 任意节点的左右子树，也都是二叉查找树
- 不存在key、value都相等的节点
不过二叉查找树存在一个问题。正常情况下，二叉查找树的查找性能为O(logN)，不过在极端情况下，比如按照顺序从小到大 或者从大到小，选中的根节点为最小或最大值，那么二叉查找树就变成了一个链表，查找性能变成了O(N)。而加上了一个平衡，也就解决了这个问题，平衡树(即AVL树，Adelson-Velskii 和 Laandis），在每插入一个节点的时候，必须保证每个节点对应的左子树和右子树的树高度差不超过1。如果超过，就需要平衡，也就是左旋、右旋、左右旋结合（先左再右，先右再左）
总结下：二叉查找树的值，从小到大的顺序分别是：左 < 根 < 右，任意子树都满足这个大小关系，不过存在极端情况下性能变成O(N)的问题，平衡树则解决了这个问题。
注意：这里说的值，是指key的值，而不是Value。简化点，是根据key来构成的节点
红黑树定义
红黑树在平衡二叉查找树的基础上，增加了着色和一些规定。增加的规定如下：
- 根节点是黑的
- 下面的子节点可以为红，也可以为黑
- 叶子节点，即所有null节点，都是黑的
- 如果一个节点是红的，那么他的两个子节点都是黑的
- 对于任一节点来说，它到叶子null节点的所有路径，含有相同数目的黑色节点
如下图所示，就是一个典型的红黑树结构（引用自https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md）：
1.png
第五点比较有意思，可以对照图做理解。
AVL树的旋转
当往平衡树中添加、删除节点时，可能导致树的左右子树不平衡，所以就有了树的旋转。
树的旋转分为左旋和右旋，下面分别开始学习：
左旋
顾名思义，向左旋转，不过这里指的是根节点变成了左子树根节点。
具体下来，就是右子树以根节点为中心，逆时针旋转， 如下所示，右节点C变成了根节点，原来的根节点A变成了左子树的子根节点。
Snip20180627_13.png
说明：
- 左侧是一颗红黑树，现在需要做 左转 操作
- 根据左转负责，A的右子树需要逆时针旋转，所以是以C为根节点的子树，逆时针上移
- 关于key大小的关系，存在以下不等式： B < A < E < C < F，所以C变成了根节点，A为左子树根节点，则B和E分别变成了A的左、右子节点，F变成C的右子节点
- 根据红黑树的节点颜色规定，需要将各个节点的颜色进行从新着色。
先看下普通的左旋实现，关于着色的。。。后续再说。主要思路就是上面的2、3两个步骤：
treeMap中的左旋实现，p是当前根节点（或子树根节点）
void rotateLeft(Entry<K,V> p){ // p是当前需要旋转的树根节点
if(null != p){
// 1 先拿到右子树(上图中C)
Entry<K,V> r = p.right;
// 2 把C的左子树E 变成 节点p的右子树，因为EValue肯定大于pValue，注意是双向关系指向
p.right = r.left; // 2.1 父-->子
if(null != r.left){
r.left.parent = p; // 2.2 子-->父
}
// 3 把r变成根节点
r.parent = p.parent; // 3.1 子-->父
// 3.2 以下都是父到子的关系设定
if(p.parent = null){ // 3.2.1 如果p已经是根节点了，那么现在r就是根节点
root = r;
}
// 3.2.2 如果p是之前父节点的左子树，设置左子树为r
else if (p.parent.left == p){
p.parent.left = r;
}
// 3.2.3 如果p是之前父节点的右子树，设置右子树为r
else{
p.parent.right = r;
}
// 4 p和r的位置设置，p变成r的左子树
r.left = p; // 3.1.1 父 -> 子
p.parent = r; // 3.1.2 子 --> 父
}
}
右旋
说完左旋，下面说到右旋。右旋是指根节点变成右移，变成右子树根节点。
右旋是指树的左子树，以根节点为中心顺时针旋转。
Snip20180629_17.png
说明：
- 左侧是原始树，需要做右旋转。
- 右旋转是左子树B，以根节点A为轴，顺时针旋转，并取代A的根节点位置。
- 值的大小关系，是D < B < E < A < C，所以如果B变成了根节点，那么左子树只有一个D节点。其他节点都在右子树上；其中A需要为右子树的子根节点
- 右旋转完成后，需要重新着色。
简单起见，先以普通二叉树的右旋转代码实现为例：
void rotateRight(Entry<K,V> p){ // p是当前需要右旋转的树/子树根节点
if(null != p){
// 1 先拿到左子树根节点
Entry<K,V> l = p.left;
// 2 把l节点的右子节点(上图中E)，变成p(上图中A)的左节点，注意是双向节点：
p.left = l.right; // 2.1，父-->子，也就是做父节点指向子节点的指针赋值
if(null != l.right){
l.right.parent = p; // 2.2 子-->父，做子节点指向父节点的指针赋值。这里做个非Null判断，防止空指针
}
// 3 把l节点 跟 p的父节点 关联起来
l.parent = p.parent; // 3.1 子 --> 父，设定l的父节点为 p的父节点
// 3.2 父 --> 子，多种情况
if(null = p.parent){ // 3.2.1 p本身就是根节点，那么现在根节点变成l
root = l;
}
// 3.2.2 如果p是左子树
else if(p = p.parent.left){
p.parent.left = l;
}
// 3.2.3 如果p是右子树
else{
p.parent.right = l;
}
// 4 p和l的关系转换
p.parent = l;
l.right = p;
}
}
右旋的实现，基本上思路与左旋实现一致，只不过刚好倒过来。
总结下：
左旋 = 右子树 + 逆时针，本质上是右子树向右，原根节点变成新根节点的左子树根节点，所以叫左旋
右旋 = 左子树 + 顺时针，本质上是左子树向左，原根节点变成新根节点的右子树根节点，所以叫右旋
旋转之后，需要根据key的大小关系重新组织数节点，这里赋值的时候，需要注意是双向赋值：
- 子节点需要将parent字段指向父节点
- 父节点需要根据情况，确定子节点是在左子树还是右子树上。
红黑树的旋转
在二叉树节点插入的基础上，红黑树需要加入平衡、着色处理。由于只有两种颜色，即红色和黑色，那么可以用boolean类型来表示颜色。具体实现详见下一章节。
红黑树的实现
hashmap源码中包含了红黑树的构造和实现，先贴下源码
/* ------------------------------------------------------------ */
// Tree bins
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
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(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
/**
* Ensures that the given root is the first node of its bin.
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
/**
* Finds the node starting at root p with the given hash and key.
* The kc argument caches comparableClassFor(key) upon first use
* comparing keys.
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
/**
* Calls find for root node.
*/
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
/**
* Tie-breaking utility for ordering insertions when equal
* hashCodes and non-comparable. We don't require a total
* order, just a consistent insertion rule to maintain
* equivalence across rebalancings. Tie-breaking further than
* necessary simplifies testing a bit.
*/
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
/**
* Forms tree of the nodes linked from this node.
* @return root of tree
*/
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);
}
/**
* Returns a list of non-TreeNodes replacing those linked from
* this node.
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
/**
* Tree version of putVal.
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
/**
* Removes the given node, that must be present before this call.
* This is messier than typical red-black deletion code because we
* cannot swap the contents of an interior node with a leaf
* successor that is pinned by "next" pointers that are accessible
* independently during traversal. So instead we swap the tree
* linkages. If the current tree appears to have too few nodes,
* the bin is converted back to a plain bin. (The test triggers
* somewhere between 2 and 6 nodes, depending on tree structure).
*/
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;
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 || 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) // find successor
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;
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
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);
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);
}
/**
* Splits nodes in a tree bin into lower and upper tree bins,
* or untreeifies if now too small. Called only from resize;
* see above discussion about split bits and indices.
*
* @param map the map
* @param tab the table for recording bin heads
* @param index the index of the table being split
* @param bit the bit of hash to split on
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
/* ------------------------------------------------------------ */
// Red-black tree methods, all adapted from CLR
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null)
rl.parent = p;
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
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.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);
}
}
}
}
}
}
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
for (TreeNode<K,V> xp, xpl, xpr;;) {
if (x == null || x == root)
return root;
else if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (x.red) {
x.red = false;
return root;
}
else if ((xpl = xp.left) == x) {
if ((xpr = xp.right) != null && xpr.red) {
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr == null)
x = xp;
else {
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
xpr.red = true;
x = xp;
}
else {
if (sr == null || !sr.red) {
if (sl != null)
sl.red = false;
xpr.red = true;
root = rotateRight(root, xpr);
xpr = (xp = x.parent) == null ?
null : xp.right;
}
if (xpr != null) {
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
sr.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateLeft(root, xp);
}
x = root;
}
}
}
else { // symmetric
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K,V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}
/**
* Recursive invariant check
*/
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)t.next;
if (tb != null && tb.next != t)
return false;
if (tn != null && tn.prev != t)
return false;
if (tp != null && t != tp.left && t != tp.right)
return false;
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
if (t.red && tl != null && tl.red && tr != null && tr.red)
return false;
if (tl != null && !checkInvariants(tl))
return false;
if (tr != null && !checkInvariants(tr))
return false;
return true;
}
}
父类
先从父类开始看，TreeNode继承LinkedHashMap.Entry，看下实现代码
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
可以看到，而LinkedHashMap.Entry还是继承的HashMap.Node。Entry扩展了before、after两个指针。
TreeNode的变量
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;
可以看到，在LinkedHashMap.Entry的基础上，TreeNode又扩展了以下信息：
- parent：父根节点
- left：左子节点
- right：右子节点
- prev：？这个没理解，为什么还需要记录一个prev
- red：当前节点颜色，默认为false的话，那就是black
