先简单了解下红黑树
红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。
红黑树的特性：
- 每个节点要么是红色，要么是黑色；
- 根节点永远是黑色的；
- 所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
- 每个红色节点的两个子节点一定都是黑色；
- 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
左旋右旋：
红黑树的左右旋是比较重要的操作，左右旋的目的是调整红黑节点结构，转移黑色节点位置，使其在进行插入、删除后仍能保持红黑树的 5 条性质。
红黑树的插入主要分两步：
- 首先和二叉查找树的插入一样，查找、插入
- 然后调整结构，保证满足红黑树状态
- 对结点进行重新着色
- 以及对树进行相关的旋转操作
树化的方法
TreeNode节点：有左右孩子父节点 颜色，前一个元素的节点。
//TreeNode 节点
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);
}
}一、链表转红黑树 HashMap有两个成员变量TREEIFY_THRESHOLD、MIN_TREEIFY_CAPACITY。
当链表长度达到TREEIFY_THRESHOLD-1，就会检查是否扩容还是把链表结构转红黑树结构； 而当数组的长度小于MIN_TREEIFY_CAPACITY就会对数字进行扩容，否则就把链表结构转红黑树结构 从treeifyBin()方法看起
//将所有链表节点 替换成红黑树节点
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//当 tab的长度小于 MIN_TREEIFY_CAPACITY 的时候先进行扩容，而不是树化
//MIN_TREEIFY_CAPACITY 默认值 64，也就是说数组的长度达到64 才会树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//满足之后~ else if 就是 把Node 节点转换成 TreeNode 节点
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);//开始构建树
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}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) {//最开始 为null
x.parent = null;
x.red = false; //根节点必须时黑色
root = x;//直接赋值给根节点
}
else {//这里说明根节点已存在，就要按二叉排序树方式插入
//X 指向树种某个节点
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;
//hash值相等 做的一些处理
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;
//进行插入后的红黑树调整 DODO:
root = balanceInsertion(root, x);
break;
}
}
}
}
//把根节点移动到数组一次(n-1)&hash就找到的下标下 TOTO：
moveRootToFront(tab, root);
} //DODO： 此方法返回根节点 ，因为在调整过程中可能会改变根节点
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) {//插入节点时父节点的右孩子
//以父节点为支点 左旋 LEFT:
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;
//右旋 RIGHT：
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);
}
}
}
}
}
}
//TOTO： 把根节点移动到数组一次(n-1)&hash就找到的下标下
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) { //root节点不是第一个节点
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);
}
}
//LEFT： 左旋 root是旧的根节点，p是旋转支点
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; //p的右节点的左孩子会变成p的右孩子
if ((pp = r.parent = p.parent) == null) //说明p原来是根节点
(root = r).red = false; //p的右孩子会变成根节点
else if (pp.left == p)
pp.left = r; //p原先是个左孩子
else
pp.right = r; //p原先是个右孩子
r.left = p; //p变成原先p的右节点的左孩子
p.parent = r;
}
return root;
}
//RIGHT： 右旋
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;
}put操作
Hashmap的put方法在进行操作的时候会，先根据key找到 该元素应该存在数组上的具体位置——table[i]。其中有一步操作是(p instanceof TreeNode)，也就是判断该节点是不是树形节点。也就是判断此时，该位置的链表是否已经构建成红黑树。如果是的话将执行.putTreeVal(this, tab, hash, key, value);方法
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;
// 根据hash值 判断方向
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
// 如果key 相等 直接返回该节点的引用 外边的方法会对其value进行设置
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null && //这块说明 hash相同， equals不同
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
//在左右子树递归的寻找 是否有key的hash相同 并且equals相同的节点
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;//找到了 就直接返回
}
//说明红黑树中没有与之equals相等的 那就要进行插入操作
//打破平衡的方法的 分出大小 结果 只有 -1 1
dir = tieBreakOrder(k, pk);
}
//下列操作进行插入节点
//xp 保存当前节点
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;
//将root移到table数组的i 位置的第一个节点
//插入操作过红黑树之后 重新调整平衡。
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}删除操作
红黑树删除节分四种情况：
删除的节点没有孩子，那暂时先用自己代替，最后再删除 删除的节点只有左孩子，那用左孩子代替 删除的节点只有右孩子，那用右孩子代替 删除的节点左孩子、右孩子都不为空，那和后继节点交换，这样就转换成删除后继节点 HashMap中的红黑树实现其实是树结构和链表结构共存的，删除节点时会判断是否由于节点太少而转回链表结构，如果不转就按红黑树删除节点的方式删除节点。
//TreeNode 删除 操作
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)//说明只有一个节点，删除后tab[index]是null了
return;
//下面就是要从树结构中删除节点
if (root.parent != null)
root = root.root(); //保证root是根节点
if (root == null
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
tab[index] = first.untreeify(map); // 转回链表结构
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; // 交换颜色
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { //后继节点就是待删除节点的右孩子
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;
}
// 待删除节点是红色就不用调整，否则进行红黑树删除节点后的调整 balanceDeletion
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); //移动根节点
}
//待删除节点是红色不调整否则进行调整
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
// X 是删除节点的 替换节点
for (TreeNode<K,V> xp, xpl, xpr;;) {
if (x == null || x == root)
return root; //x是黑且又是根节点直接返回
else if ((xp = x.parent) == null) { //x是根节点
x.red = false; // 变黑
return x; //作为新根节点返回
}
else if (x.red) { //x是红色就直接涂黑返回根节点
x.red = false;
return root;
}
else if ((xpl = xp.left) == x) { //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;
}
}
}
}
}
// 转回链表
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;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
版权声明：本文为a_001aaa原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。