-
ConcurrentHashMap(JDK1.8)中红黑树的实现
ConcurrentHashMap(JDK1.8)中红黑树的实现
本文只介绍红黑树的实现 不对并发容器ConcurrentHashMap进行介绍。红黑树的理论和基础试下可以阅读红黑树与JAVA实现
红黑树特性
- 每个结点的或是黑色或是红色
- 根结点是黑色
- 每个叶子结点都是黑色（NIL）
- 如果一个结点是红色，那么它的子结点必须是黑色
- 对任意一结点，该结点到其叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点
ConcurrentHashMap数据结构示意图
代码实现分析
结点组成
Node<K,V>// key的hash值 final int hash; // 关键字 final K key; // 存储值 volatile V val; // 下一个结点 volatile Node<K,V> next;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
TreeNode<K,V>
作为红黑树结构的存储结构，比一般红黑树存储结构出来的next和prev，可以将这些结点变成双向的链表结构，是为了方便从链表变为红黑树，在从红黑树变成链表。在ConcurrentHashMap中，链表与红黑树的转变是依据链表中的结点数量，默认变成红黑树的链表结点个数需要大于8。hash key val next prev parent left right red static final class TreeNode<K,V> extends Node<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, TreeNode<K,V> parent) { super(hash, key, val, next); this.parent = parent; } Node<K,V> find(int h, Object k) { return findTreeNode(h, k, null); } /** * Returns the TreeNode (or null if not found) for the given key * starting at given root. */ final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) { if (k != null) { TreeNode<K,V> p = this; do { int ph, dir; K pk; TreeNode<K,V> q; TreeNode<K,V> pl = p.left, pr = p.right; if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; else if ((pk = p.key) == k || (pk != 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.findTreeNode(h, k, kc)) != null) return q; else p = pl; } while (p != null); } return null; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
TreeBin<K,V>继承Node，树标记结构，表明该结点背后有一棵红黑树。在新增结点和删除结点的时候，为了并发的安全都需要会进行锁的竞争。root和first不应该是同一个结点。
TreeNode<K,V> root; // 树根结点 volatile TreeNode<K,V> first; // 首结点 volatile Thread waiter; // 等待的线程 volatile int lockState; // 结点锁的情况- 1
- 2
- 3
- 4
主要方法
构造函数
从给定的b结点开始，遍历整个链表，构建红黑树。
TreeBin(TreeNode<K,V> b) { super(TREEBIN, null, null, null); // 参数b的值为首结点 this.first = b; // 根结点 TreeNode<K,V> r = null; // 从首结点开始遍历链表 for (TreeNode<K,V> x = b, next; x != null; x = next) { // 获取下一个结点 next = (TreeNode<K,V>)x.next; // 初始化x的左右子结点 置null x.left = x.right = null; // 设置根结点，颜色为黑色 if (r == null) { x.parent = null; x.red = false; r = x; } else { // 结点的关键字 K k = x.key; // 结点的hash int h = x.hash; Class<?> kc = null; // 遍历以r为根的树 for (TreeNode<K,V> p = r;;) { int dir, ph; K pk = p.key; // dir-1 左子 dir1 右子 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) // 当 hashCodes 相等且不可比较时，用于排序插入的打破平局实用程序。 我们不需要总排序，只需要一致的插入规则来保持重新平衡之间的等价性。 简化了比较平局的处理逻辑。 dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; // p作为x的双亲结点，确认x是双亲结点p的左子还是右子 if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; // 保证红黑树的性质 r = balanceInsertion(r, x); break; } } } } this.root = r; assert checkInvariants(root); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
新增节点修复红黑树方法
balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x)root为根，x为新增的那个结点，新增的结点都为红色。
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { // 先将x变为红结点 x.red = true; // x的双亲结点xp // x的祖父结点xpp // x的祖父结点xpp的左子结点xppl // x的祖父结点xpp的右子结点xppr for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { // 若x的父结点为空，则将节点置为黑，直接返回x即为根结点退出for。 if ((xp = x.parent) == null) { x.red = false; return x; } // 此时父节点不为null，若父节点是黑色的，那么不要调整，直接返回 // 若当前结点的祖父节点为空（说明父节点是根结点），直接返回根结点。 else if (!xp.red || (xpp = xp.parent) == null) return root; // 目前父节点是红色的 若父节点是祖父的左子结点 if (xp == (xppl = xpp.left)) { // 叔叔结点是红色 // 将双亲节点和叔叔结点变黑，祖父变红 // x指向祖父结点 if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } // 以下叔叔结点是黑色 else { // 当前结点是双亲结点的右子 if (x == xp.right) { //当前x指向双亲结点 ，以双亲节点为根进行左旋 root = rotateLeft(root, x = xp); // 取x的祖父结点 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 { // 叔叔结点是红色 // 将双亲节点和叔叔结点变黑，祖父变红 // x指向祖父结点 if (xppl != null && xppl.red) { xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } // 以下叔叔结点是黑色 else { // 当前结点是双亲结点的左子 if (x == xp.left) { //当前x指向双亲结点 ，以双亲节点为根进行右旋 root = rotateRight(root, x = xp); // 取x的祖父结点 xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { // 当前结点是双亲结点的右子 // 双亲结点变黑 xp.red = false; // 若还有祖父结点，将祖父结点变红，以祖父结点为支点进行左旋 if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
左旋方法
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { // r右子结点 pp是p的双亲结点 rl是r的左子结点 TreeNode<K,V> r, pp, rl; // 若p是空 或者p没有右子 不进行左旋 if (p != null && (r = p.right) != null) { // 若r存在左子，则变为p的右子 if ((rl = p.right = r.left) != null) rl.parent = p; // 若p的双亲结点为空（p是当前的根结点），则r变为根结点，r颜色变黑 if ((pp = r.parent = p.parent) == null) (root = r).red = false; // 目前p的双亲结点不为空，若p是双亲结点的左子，将r变为双亲结点的左子 else if (pp.left == p) pp.left = r; // 若p是双亲结点的右子，将r变为双亲结点的右子 else pp.right = r; // r的左子变为p，p的双亲结点变为r r.left = p; p.parent = r; } // 旋转结束，返回实际根结点 return root; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
右旋方法
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) { // l是左子结点 pp是p的双亲结点 lr是l的右子结点 TreeNode<K,V> l, pp, lr; // 若p是空 或者p没有左子 不进行右旋 if (p != null && (l = p.left) != null) { // 若l存在右子，则p变为l的左子 if ((lr = p.left = l.right) != null) lr.parent = p; // 若p的双亲结点为空（p是当前的根结点），则l变为根结点，l颜色变黑 if ((pp = l.parent = p.parent) == null) (root = l).red = false; // 目前p的双亲结点不为空，若p是双亲结点的右子，将l变为双亲结点的右子 else if (pp.right == p) pp.right = l; // 若p是双亲结点的左子，将r变为双亲结点的左子 else pp.left = l; // l的右子变为p，p的双亲结点变为r l.right = p; p.parent = l; } // 旋转结束，返回实际根结点 return root; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
红黑树特性检查方法
static <K,V> boolean checkInvariants(TreeNode<K,V> t) { // t 从根开始遍历的结点 // tp 为t的双亲结点 // tl 为t的左子 // tr 为t的右子 // tb 为t的前驱 // tn 为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; // t 不是双亲结点的左右子--树结点关系出现混乱 if (tp != null && t != tp.left && t != tp.right) return false; // t的左子的双亲结点不是t，或者左子的hash值大于t的hash--树结点关系出现混乱 if (tl != null && (tl.parent != t || tl.hash > t.hash)) return false; // t的右子的双亲结点不是t，或者右子的hash值小于t的hash--树结点关系出现混乱 if (tr != null && (tr.parent != t || tr.hash < t.hash)) return false; // t是红色 且左右子也是红色 if ((t.red && tl != null && tl.red)||(t.red && tr != null && tr.red))？？？ // 这个是说明结点是红色，其左右子不可以同时为红色，不应该是不论哪个子结点为红色也不可以吗？ 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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
删除结点方法
final boolean removeTreeNode(TreeNode<K,V> p) { // p的后继结点 TreeNode<K,V> next = (TreeNode<K,V>)p.next; // p的前驱结点 TreeNode<K,V> pred = p.prev; // unlink traversal pointers // r 右子 rl右子的左子 TreeNode<K,V> r, rl; // 如果前驱结点为null，那么就是首结点 if (pred == null) first = next; // 将前驱节点的后继结点变为p的后继（在双向链表中删除p） else pred.next = next; // 若后继结点不为null，p的原来的前驱变成p的后继结点的前驱（在双向链表中删除p） if (next != null) next.prev = pred; // 没有首结点，那就是空链表 空树，直接返回。 if (first == null) { root = null; return true; } // 树太小，就不保证红黑树了 if ((r = root) == null || r.right == null || // too small (rl = r.left) == null || rl.left == null) return true; // 锁根 lockRoot(); try { // 替换结点，从它开始修正红黑树 TreeNode<K,V> replacement; TreeNode<K,V> pl = p.left; TreeNode<K,V> pr = p.right; // p的左右子都不为null if (pl != null && pr != null) { // s 应该是p的直接后继结点（与链表的后继概念不同） TreeNode<K,V> s = pr, sl; // 寻找p的直接后继结点s while ((sl = s.left) != null) // find successor s = sl; // 将p与其直接后继结点进行交换,借助replacement将p调整至最底层结点，删除p，以replacement作为平衡修正的起始结点 >>> // 交换后继结点与p的颜色 boolean c = s.red; s.red = p.red; p.red = c; // swap colors // 后继结点的右子 TreeNode<K,V> sr = s.right; // p的双亲结点 TreeNode<K,V> pp = p.parent; // p 是s的双亲结点 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) r = 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) r = replacement; else if (p == pp.left) pp.left = replacement; else pp.right = replacement; p.left = p.right = p.parent = null; } // 将p与其后继结点进行交换,借助replacement将p调整至最底层结点，删除p，以replacement作为平衡的起始结点 <<< // p的颜色是红色 则不进行删除修正 root = (p.red) ? r : balanceDeletion(r, replacement); if (p == replacement) { // detach pointers TreeNode<K,V> pp; if ((pp = p.parent) != null) { if (p == pp.left) pp.left = null; else if (p == pp.right) pp.right = null; p.parent = null; } } } finally { unlockRoot(); } assert checkInvariants(root); return false; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
删除节点修复函数
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) { // x的双亲结点xp // x的双亲结点xp的左子结点xpl // x的双亲结点xp的右子结点xpr for (TreeNode<K,V> xp, xpl, xpr;;) { // 当前x变为null或为根 if (x == null || x == root) return root; // x的双亲结点为空，即x应该就是根 变黑 else if ((xp = x.parent) == null) { x.red = false; return x; } // 直接置成黑色退出 else if (x.red) { x.red = false; return root; } // x是双亲节点xp的左子 else if ((xpl = xp.left) == x) { // 兄弟结点为红： // 1.将兄弟结点变黑，双亲结点变红 // 2.以双亲结点为根左旋 // 3.刷过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; } // 如果兄弟结点为空，x指针指向双亲结点xp if (xpr == null) x = xp; else { TreeNode<K,V> sl = xpr.left, sr = xpr.right; // 兄弟结点的左右子都是黑色： // 1.兄弟变红 // 2.x指向双亲结点xp if ((sr == null || !sr.red) && (sl == null || !sl.red)) { xpr.red = true; x = xp; } else { // 兄弟的右子结点是黑色 // 1.左侄子变黑，兄弟变红 // 2.以兄弟为根进行右旋 // 3.更新兄弟结点 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; } } } // x是双亲节点xp的右子 else { // symmetric // 兄弟结点为红： // 1.将兄弟结点变黑，双亲结点变红 // 2.以双亲结点为根右旋 // 3.刷过x的兄弟结点 if (xpl != null && xpl.red) { xpl.red = false; xp.red = true; root = rotateRight(root, xp); xpl = (xp = x.parent) == null ? null : xp.left; } // 如果兄弟结点为空，x指针指向双亲结点xp if (xpl == null) x = xp; else { TreeNode<K,V> sl = xpl.left, sr = xpl.right; // 兄弟结点的左右子都是黑色： // 1.兄弟变红 // 2.x指向双亲结点xp if ((sl == null || !sl.red) && (sr == null || !sr.red)) { xpl.red = true; x = xp; } else { // 兄弟的左子结点是黑色 // 1.右侄子变黑，兄弟变红 // 2.以兄弟为根进行左旋 // 3.更新兄弟结点 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; } } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
新增结点方法
putTreeVal
// h:key的hash值 // k关键字 // v值 final TreeNode<K,V> putTreeVal(int h, K k, V v) {. // key的Class Class<?> kc = null; boolean searched = false; // 从根结点开始遍历，寻找位置新增结点 for (TreeNode<K,V> p = root;;) { // dir 判断左右路径 ph p的hash pk p的K int dir, ph; K pk; // 红黑树是空的，直接新增结点，作为root和first，退出for。 if (p == null) { first = root = new TreeNode<K,V>(h, k, v, null, null); break; } else if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; // 若树中已经存在此key直接返回对应结点p else if ((pk = p.key) == k || (pk != null && k.equals(pk))) return p; // 1.如果Key的对应class类为null且x 的 Class 不是“class C implements Comparable”时， // 2.如果 pk 不匹配 kc（k 的筛选可比类），返回 0。 else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) { // 查询标记为false if (!searched) { TreeNode<K,V> q, ch; searched = true; // 从p结点左右子结点寻找K对应的结点，如果找到了就返回 if (((ch = p.left) != null && (q = ch.findTreeNode(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.findTreeNode(h, k, kc)) != null)) return q; } // 当 hashCodes 相等且不可比较时，用于排序插入的打破平局实用程序。 我们不需要总顺序，只需要一致的插入规则来保持重新平衡之间的等价性。 超出必要的平局进一步简化了测试。 dir = tieBreakOrder(k, pk); } TreeNode<K,V> xp = p; // dir路径？当dir<=0则左子结点先行，相反则从右子结点先行 // 当dir<=0成立，且左子树为空 // 或 当dir>0成立，且右子树为空 if ((p = (dir <= 0) ? p.left : p.right) == null) { // xp就变成p的双亲结点 TreeNode<K,V> x, f = first; // 头插法？更新first结点 // 新结点的 前驱是xp 后继是f first = x = new TreeNode<K,V>(h, k, v, f, xp); // 若原来头结点不为空，则建立双向联系 if (f != null) f.prev = x; // 确认是将新节点作为左子结点还是右子结点 if (dir <= 0) xp.left = x; else xp.right = x; // 若xp是黑结点，x直接置为red if (!xp.red) x.red = true; else { // 获取用于树重组的写锁。 lockRoot(); try { // 平衡重组红黑树 root = balanceInsertion(root, x); } finally { unlockRoot(); } } break; } } assert checkInvariants(root); return null; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
-
相关阅读:
基于python找到并显示100以内的素数
【C语言】预处理详解
Java并发 - (并发基础)
【无标题】Linux服务器上监控网络带宽的18个常用命令
python 多线程
浅谈Java中的代理模式
ssm在线教学质量评价系统毕业设计源码141550
ZMQ请求应答模式之无中间件的可靠性--自由者模式
【PyQt5 实战项目1】武汉大学建筑知识系统--思路分享1（总体概述）
1.6 IntelliJ IDEA开发工具
- 原文地址：https://blog.csdn.net/weixin_43820556/article/details/125020774