前面几篇文章已经讲解过HashMap内部实现以及红黑树的基础知识，今天这篇文章就讲解之前HashMap中未讲解的红黑树操作部分，如果没了解红黑树，请去阅读前面的两篇文章，能更好的理解本章所讲解的红黑树源码操作，全文默认读者已经了解红黑树的相关知识，接下来，就以HashMap.TreeNode来说明红黑树的源码操作。

前言

jdk版本：1.8

以HashMap.TreeNode为例是因为之前HashMap的红黑树操作在文章省略了，这里进行一个解释，其实源码里并不是只有这个地方用红黑树结构，但是总体上都大同小异，故只说明这一部分就好，举一反三的能力相信各位都应该拥有。

类定义

staticfinalclassTreeNode<K,V>extendsLinkedHashMap.Entry<K,V>

继承LinkedHashMap.Entry，追溯源头可以到HashMap.Node，下面图展示了对应的结构关系：

进群：697699179可以获取Java各类入门学习资料！

这是我的微信公众号【编程study】各位大佬有空可以关注下，每天更新Java学习方法，感谢！

学习中遇到问题有不明白的地方，推荐加小编Java学习群：697699179内有视频教程 ，直播课程 ，等学习资料，期待你的加入

属性

/**

    * 父节点

    */TreeNode parent;// red-black tree links/**

    * 左子节点

    */TreeNodeleft;/**

    * 右子节点

    */TreeNoderight;/**

    * 指向前一个节点

    */TreeNode prev;// needed to unlink next upon deletion/**

    * 是否是红色节点

    */boolean red;

以上的属性都是为了满足红黑树特性而设置

构造方法

/**

    * 构造方法直接调用的父类方法

    * 最终还是HashMap.Node的构造方法，调用代码下面也列出来了

    */TreeNode(int hash,Kkey,Vval,Node next) {super(hash, key,val, next);    }/**

    * HashMap.Node subclass for normal LinkedHashMap entries.

    */staticclassEntry<K,V>extendsHashMap.Node<K,V>{Entry before, after;Entry(int hash,Kkey,Vvalue,Node next) {super(hash, key, value, next);        }    }Node(int hash,Kkey,Vvalue,Node next) {this.hash = hash;this.key = key;this.value = value;this.next = next;    }

Node和TreeNode相同的构造方法

重要方法

root

实现上非常简单，不断向上遍历，找到父节点为空的节点即为根节点

/**

    * 返回根节点TreeNode

    */finalTreeNode root() {for(TreeNode r =this, p;;) {if((p = r.parent) ==null)returnr;            r = p;        }    }

moveRootToFront

从注释中也能看出当前方法的含义，确保根节点是bin桶（数组tab的其中一个元素）中的第一个节点,如果不是，则进行操作，将根节点放到tab数组上，这个跟HashMap结构有关，数组（链表+红黑树），在进行树化，结构调整时，根节点可能会变化，原有数组tab对应索引指向的树节点需要进行改变，指向新的根节点,这里注意下，移动时不是修改红黑树是修改的链表结构，prev和next属性

/**

    * Ensures that the given root is the first node of its bin.

    */staticvoidmoveRootToFront(Node[] tab, TreeNode root) {intn;if(root !=null&& tab !=null&& (n = tab.length) >0) {// 找到当前树所在的bin桶位置（即数组tab的位置）intindex = (n -1) & root.hash;// 将tab[index]的树节点记录下来为firstTreeNode first = (TreeNode)tab[index];// root没有落在tab数组上，修改为root在tab数组上if(root != first) {                Node rn;// 这里即替换掉tab[index]指向的原有节点，可以理解成现在指向root节点tab[index] = root;// rp为root指向的前一个节点TreeNode rp = root.prev;// rn为root的后一个节点// 将root前后节点关联if((rn = root.next) !=null)                    ((TreeNode)rn).prev = rp;if(rp !=null)                    rp.next= rn;// first 和 root 节点进行关联，first的前一个节点为rootif(first !=null)                    first.prev = root;// 修改root的链表属性root.next= first;                root.prev =null;            }// 检查红黑树一致性assert checkInvariants(root);        }    }

find

从当前节点开始使用给定的hash和key查找到对应的节点，只会判断当前节点为根节点的局部树结构。这里复习下整个HashMap查找过程，通过(length - 1) & hash 判断bin桶位置（数组中的位置），这里不是hash值相等，注意再判断该位置处是什么类型，链表还是红黑树，链表类型，循环next遍历，直到key值相等。红黑树类型 递归左右子树遍历，直到key值相等。

/**

        * Finds the node starting at root p with the given hash and key.

        * The kc argument caches comparableClassFor(key) upon first use

        * comparing keys.

        * kc ： key class

        */finalTreeNodefind(inth, Object k,Class kc) {            TreeNode p =this;do{// ph:p的hash值intph, dir; K pk;                TreeNode pl = p.left, pr = p.right, q;// 查找节点hash值小于p的hash值，搜索左子树if((ph = p.hash) > h)                    p = pl;// 查找节点hash值大于p的hash值，搜索右子树elseif(ph < h)                    p = pr;// key值相同，说明就是此p节点elseif((pk = p.key) == k || (k !=null&& k.equals(pk)))returnp;// 若hash相等但key不等，向左右子树非空的一侧移动elseif(pl ==null)                    p = pr;elseif(pr ==null)                    p = pl;// 左右两边都不为空// 判断kc是否是k实现的可比较的类，是就比较k和pk的值，k<pk向左子树移动否则向右子树移动// hash相等，key不等，使用key实现的compareTo判断大小elseif((kc !=null||                          (kc = comparableClassFor(k)) !=null) &&                        (dir = compareComparables(kc, k, pk)) !=0)                    p = (dir <0) ? pl : pr;// 上面所有情况依旧不能判断左右，就先递归判断右子树，看是否匹配上，匹配上就赋右子树，否则左子树elseif((q = pr.find(h, k, kc)) !=null)returnq;elsep = pl;            }while(p !=null);returnnull;        }

tieBreakOrder

比较两个对象的大小，返回值只能大于0或小于0，不能为0，因为需要插入节点是放在左子树还是右子树，这里在两个对象都不为空时，先比较两个对象的类名按字符串规则比较，如果类名比较不出来或者为空则调用native方法去比较hashcode值，相等时返回-1

staticinttieBreakOrder(Objecta,Objectb) {intd;if(a ==null|| b ==null||            (d = a.getClass().getName().            compareTo(b.getClass().getName())) ==0)            d = (System.identityHashCode(a) <= System.identityHashCode(b) ?-1:1);returnd;    }

tieBreakOrder

比较两个对象的大小，返回值只能大于0或小于0，不能为0，因为需要插入节点是放在左子树还是右子树，这里在两个对象都不为空时，先比较两个对象的类名按字符串规则比较，如果类名比较不出来或者为空则调用native方法去比较hashcode值，相等时返回-1

staticinttieBreakOrder(Objecta,Objectb) {intd;if(a ==null|| b ==null||            (d = a.getClass().getName().            compareTo(b.getClass().getName())) ==0)            d = (System.identityHashCode(a) <= System.identityHashCode(b) ?-1:1);returnd;    }

treeify

以当前TreeNode为初始节点，循环处理链表上的每个节点，每次插入树节点都要进行平衡处理，保证红黑树的平衡。

/**

    * Forms tree of the nodes linked from this node.

    * @return root of tree

    */finalvoidtreeify(Node[] tab) {        TreeNode root =null;// this当前TreeNode,一般应该以树的根节点为初始值，根据链表进行遍历for(TreeNode x =this,next; x !=null; x =next) {next= (TreeNode)x.next;            x.left = x.right =null;// 首次root为空 当前节点先设置为root 节点颜色为黑色if(root ==null) {                x.parent =null;                x.red =false;                root = x;            }// root节点设置之后开始将链表节点依次插入处理，x=x.next插入root为根节点的红黑树，循环处理else{                K k = x.key;inth = x.hash;Class kc =null;for(TreeNode p = root;;) {intdir, ph;                    K pk = p.key;// 比较hash值判断处于左右子树哪侧if((ph = p.hash) > h)// 节点处于p左子树下dir = -1;elseif(ph < h)// 节点处于p右子树下dir =1;elseif((kc ==null&&                              (kc = comparableClassFor(k)) ==null) ||                            (dir = compareComparables(kc, k, pk)) ==0)// hash值相等根据compareTo判断，判断不出来继续执行tieBreakOrder判断dir = tieBreakOrder(k, pk);// x的父节点设置为xpTreeNode xp = p;// 左右节点为空，说明可以将新增节点插入// 非空，继续循环子树，p指向左子树或右子树，继续循环判断直到为空的节点if((p = (dir <=0) ? p.left : p.right) ==null) {                        x.parent = xp;if(dir <=0)                            xp.left = x;elsexp.right = x;// 插入后需进行平衡保证红黑树特性root = balanceInsertion(root, x);break;                    }                }            }        }// root位置可能会在调整中变更，这里需调用确保根节点落在tab数组上moveRootToFront(tab, root);    }

untreeify

将树转换为链表结构，将TreeNode转化为Node，改变next指向即可

/**

    * Returns a list of non-TreeNodes replacing those linked from

    * this node.

    */finalNode untreeify(HashMap map) {// hd是链表首节点，tl是链表尾节点Node hd =null, tl =null;for(Node q =this; q !=null; q = q.next) {            Node p = map.replacementNode(q,null);if(tl ==null)                hd = p;elsetl.next= p;            tl = p;        }returnhd;    }    Node replacementNode(Node p, Nodenext) {returnnewNode<>(p.hash, p.key, p.value,next);    }

putTreeVal

在红黑树结构中的putVal操作，先判断节点应该存在的位置，循环判断左右子树，找到应该存在的位置。若该位置为空，相当于原本无值，插入节点，然后进行平衡，桶位置调整。若该位置有值且相等，则直接返回，不需要插入操作。

/**

    * Tree version of putVal.

    */finalTreeNode putTreeVal(HashMap map, Node[] tab,inth, K k, V v) {Class kc =null;booleansearched =false;// 获取根节点TreeNode root = (parent !=null) ? root() :this;// 循环遍历，类似find方法for(TreeNode p = root;;) {intdir, ph; K pk;if((ph = p.hash) > h)                dir = -1;elseif(ph < h)                dir =1;elseif((pk = p.key) == k || (k !=null&& k.equals(pk)))returnp;elseif((kc ==null&&                      (kc = comparableClassFor(k)) ==null) ||                    (dir = compareComparables(kc, k, pk)) ==0) {if(!searched) {// 递归左右子树进行查找是否已经存在// 只需判断一次即可，第二次不再执行TreeNode 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))returnq;                }// 上面都比较不出来，通过这个方法比较出来dir = tieBreakOrder(k, pk);            }// 判断当前插入位置是否为空，为空才插入，非空则继续判断，根据dir判断是左还是右子树TreeNode xp = p;if((p = (dir <=0) ? p.left : p.right) ==null) {                Node xpn = xp.next;                TreeNode x = map.newTreeNode(h, k, v, xpn);if(dir <=0)                    xp.left = x;elsexp.right = x;                xp.next= x;                x.parent = x.prev = xp;if(xpn !=null)                    ((TreeNode)xpn).prev = x;// balanceInsertion 插入调整平衡// moveRootToFront 确保root节点落在tab数组上为首节点moveRootToFront(tab, balanceInsertion(root, x));returnnull;            }        }    }

removeTreeNode

删除树节点操作，movable：判断是否需要调整root节点（放置在tab上），在HashMap里removeNode方法中使用，对应的删除节点进行调用，具体自行查看源码部分。其实，想下，删除操作相当于将链表节点之间的关联重新梳理，修正两部分，第一部分是链表的关系修正，第二部分是树的关系修正，然后自平衡操作即可。

finalvoid removeTreeNode(HashMap map, Node[] tab,boolean movable) {        int n;// 判断非空if(tab ==null|| (n = tab.length) ==0)return;// 计算当前树节点所在的桶的位置（tab索引位置）int index = (n -1) & hash;        TreeNode first = (TreeNode)tab[index], root = first, rl;// succ指向当前删除节点的后一个节点，pred指向当前删除节点的前一个节点TreeNode succ = (TreeNode)next, pred = prev;if(pred ==null)// 前一个节点为空，说明删除的节点为根节点，first和tab[index]需指向删除节点的后一个节点tab[index] = first = succ;else// 前一个节点不为空，则前一个节点的后一个节点为succ(删除之后的关联)pred.next = succ;if(succ !=null)// 后一个节点不为空，则后一个节点的前一个节点为pred，构建关联succ.prev = pred;if(first ==null)// first为空则表明当前桶内无节点，直接returnreturn;if(root.parent!=null)// 目前的root节点有父类，需要调整root = root.root();if(root ==null|| root.right ==null||            (rl = root.left) ==null|| rl.left ==null) {// 根自身或者左右儿子其中一个为空或左子树的子树为空需转换为链表结构// 考虑到红黑树特性，这几种情况下，节点较少，进行树向链表的转化tab[index] = first.untreeify(map);// too smallreturn;        }// p指向删除的节点// 上面修正链表的关系，下面修正树中的关系TreeNode p = this, pl = left, pr = right, replacement;// 删除节点的左右子树都不为空，参考红黑树删除4种情况if(pl !=null&& pr !=null) {            TreeNode s = pr, sl;while((sl = s.left) !=null)// find successor// 寻找右子树中最左的叶结点作为后继节点，s指向后继节点s = sl;// 交换后继节点和删除节点的颜色，从这里开始在后继节点上进行删除处理boolean c = s.red; s.red = p.red; p.red = c;// swap colorsTreeNode sr = s.right;            TreeNode pp = p.parent;if(s == pr) {// p was s's direct parent// s是p的右儿子，直接父子关系，交换p和s的位置// 改变两节点的指向，相当于交换值p.parent= s;                s.right = p;            }else{                TreeNode sp = s.parent;// 删除节点的父节点指向其后继节点的父节点if((p.parent= sp) !=null) {// 判断s是左子节点还是右子节点，s父节点一侧指向删除节点pif(s == sp.left)                        sp.left = p;elsesp.right = p;                }if((s.right = pr) !=null)// s右节点指向原本p的右节点，不为空，原p右子节点的父节点指向spr.parent= s;            }// 修改p的左节点为空，因为现在p已经在后继节点上p.left =null;// 两个if是调整p和s交换后节点的指向关系if((p.right = sr) !=null)                sr.parent= p;if((s.left = pl) !=null)                pl.parent= s;if((s.parent= pp) ==null)// p的父亲成为s的父亲，为空说明是根节点，root指向sroot = s;elseif(p == pp.left)// p的父亲的左儿子原为p，现为spp.left = s;else// 否则右儿子为spp.right = s;// 若s结点有右儿子（s没有左儿子，因为s是后继节点），则replacement为这个右儿子否则为p// replacement相当于p和后继节点s交换后，删除s位置取代其位置的节点，参考红黑树删除过程理解if(sr !=null)                replacement = sr;elsereplacement = p;        }// 删除节点的左右子树一侧为空，参考红黑树删除4种情况// 若p的左右儿子为空，则replacement为非空的一方，否则为p自己elseif(pl !=null)            replacement = pl;elseif(pr !=null)            replacement = pr;elsereplacement = p;// replacement不为p，即不为叶子节点（相当于之前所讲的红黑树中有两个NIL节点的节点）// 处理连接关系if(replacement != p) {            TreeNode pp = replacement.parent= p.parent;if(pp ==null)                root = replacement;elseif(p == pp.left)                pp.left = replacement;elsepp.right = replacement;// 移除p节点p.left = p.right = p.parent=null;        }// 红黑树自平衡调节，如果为红色，则不需要进行调整，否则需要自平衡调整，后面会对这个方法进行分析TreeNode r = p.red ? root : balanceDeletion(root, replacement);// 后继节点无子节点，直接移除p节点即能保持平衡if(replacement == p) {// detachTreeNode pp = p.parent;            p.parent=null;if(pp !=null) {if(p == pp.left)                    pp.left =null;elseif(p == pp.right)                    pp.right =null;            }        }if(movable)// 调整root使其落在tab数组上moveRootToFront(tab, r);    }

split

拆分，在HashMap.resize方法中调用 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap)。在扩容之后，红黑树和链表因为扩容的原因导致原本在一个数组元素下的Node节点分为高低位两部分（参考HashMap.resize链表部分的改变，是相同的），请查看HashMap的文章自行回顾，低位树即当前位置，高位树则在新扩容的tab上

finalvoidsplit(HashMap map, Node[] tab,intindex,intbit) {        TreeNode b =this;// Relink into lo and hi lists, preserving order// 分成高位树和低位树，头尾节点先声明TreeNode loHead =null, loTail =null;        TreeNode hiHead =null, hiTail =null;intlc =0, hc =0;// 循环处理节点for(TreeNode e = b,next; e !=null; e =next) {next= (TreeNode)e.next;            e.next=null;// 这里bit代表扩容的二进制位（数值是扩容前的容量大小），不明白的也请参考之前的HashMap讲解文章if((e.hash & bit) ==0) {// 0说明在低位树，即原位置if((e.prev = loTail) ==null)// 首节点设置loHead = e;else// 链表next设置loTail.next= e;                loTail = e;                ++lc;            }else{// 同上，主要是在高位树上处理if((e.prev = hiTail) ==null)                    hiHead = e;elsehiTail.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{// 高位所处的位置为原本位置+旧数组的大小即bittab[index + bit] = hiHead;if(loHead !=null)                    hiHead.treeify(tab);            }        }    }

rotateLeft

左旋操作，参考红黑树讲解中的图来理解，自己动手画一画也能明白，右旋操作类似，不再多说

static TreeNode rotateLeft(TreeNode root,                                          TreeNode p) {        TreeNode r, pp, rl;// r代表M的右子节点N，先决条件，p(M),r(N)不能为空if(p !=null&& (r = p.right) !=null) {// r的左子节点成为p的右子节点，即B成为M的右子节点if((rl = p.right = r.left) !=null)// r的左子节点父节点指向p,即修改B父节点指向Mrl.parent= p;// p的父节点成为r的父节点，即N父节点为原M的父节点if((pp = r.parent= p.parent) ==null)// r的父节点为空，则r为root节点，设置为黑色，即N父节点为空，N设置为根节点(root = r).red =false;// 原p节点是左子树，即M是左子树elseif(pp.left == p)// 现调整后修改N父节点左子指向Npp.left = r;else// r的父节点的右子节点需重设,即调整后修改N父节点右子指向Npp.right = r;// p和r的位置关系修改，即M与N的关系重设r.left = p;            p.parent= r;        }returnroot;    }

balanceInsertion

插入节点之后进行平衡调整，x为新添加的节点，root为树的根节点，返回根节点。

static TreeNode balanceInsertion(TreeNode root,                                            TreeNode x) {// 根据红黑树属性插入的节点默认设置为红色x.red =true;// 通过循环进行调整,从叶子到根节点进行局部调整for(TreeNode xp, xpp, xppl, xppr;;) {// x的父节点为空，说明x节点为根节点，将颜色置为黑即可// 符合插入节点第一种情况if((xp = x.parent) ==null) {                x.red =false;returnx;            }// x父节点为黑色或者x的祖父节点为空// 符合插入节点第二种情况elseif(!xp.red || (xpp = xp.parent) ==null)returnroot;// 下面情况中x的颜色都为红色，因为上边已经判断过黑色// x的父节点为x祖父节点的左儿子，插入情况下三四种情况需要区分左还是右if(xp == (xppl = xpp.left)) {// x祖父右儿子，即x的叔叔不为空，且为红色// 符合插入节点第三种情况if((xppr = xpp.right) !=null&& xppr.red) {// x的叔叔修改为黑色xppr.red =false;// x的父节点修改为黑色xp.red =false;// x的祖父节点修改为红色xpp.red =true;// x指向x的祖父节点，以祖父节点循环继续向上调整，相当于xpp是插入节点x = xpp;                }else{// x的叔叔是黑色且x是右儿子，相当于在树的“内部”// 符合插入节点第四种情况的第一种状态if(x == xp.right) {// 以x父节点进行左旋root = rotateLeft(root, x = xp);                        xpp = (xp = x.parent) ==null?null: xp.parent;                    }// 这里处理第二种状态，相当于在树的“外部”if(xp !=null) {// x的父节点改为黑色，x的祖父节点改为红色后对x的祖父节点进行右旋转xp.red =false;if(xpp !=null) {                            xpp.red =true;                            root = rotateRight(root, xpp);                        }                    }                }            }// x的父节点为x祖父节点的右儿子// 下面跟上边类似，对称关系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);                        }                    }                }            }        }    }

balanceDeletion

删除节点后自平衡操作，x是删除节点的替换节点，注意下

static TreeNode balanceDeletion(TreeNode root,TreeNode x) {// 循环操作，平衡局部之后继续判断调整for(TreeNode xp, xpl, xpr;;)  {// 删除节点为空或x为根节点直接返回，平衡调整完毕x=rootif(x ==null|| x == root)returnroot;// 删除后x父节点为空，说明x为根节点，x置为黑色，红黑树平衡// 参考红黑树删除文章中的3种情况中的第一种情况，整棵树的根节点需要将根节点置黑elseif((xp = x.parent) ==null) {// xp为空 x为根节点，x置为黑色x.red =false;returnx;            }// x为红色，原节点必为黑色，变色操作即可满足红黑树特性达到平衡// 参考红黑树删除文章中的3种情况中的第二种情况elseif(x.red) {                x.red =false;returnroot;            }// 区分x为左子节点还是右子节点elseif((xpl = xp.left) == x) {// x的叔叔为红色// 符合3种情况中的第三种情况中的第二种情况if((xpr = xp.right) !=null&& xpr.red) {// 先进行变色，然后进行左旋操作，xpr指向xp新的右子xpr.red =false;                    xp.red =true;                    root = rotateLeft(root, xp);                    xpr = (xp = x.parent) ==null?null: xp.right;                }// x的兄弟为空if(xpr ==null)// x指向x的父节点，继续以x父节点调整平衡x = xp;else{                    TreeNode sl = xpr.left, sr = xpr.right;// 符合3种情况中的第三种情况中的第三种情况if((sr ==null|| !sr.red) &&                        (sl ==null|| !sl.red)) {// sr，sl两个兄弟都是黑色，x的兄弟设置为红色，x指向x的父节点继续向上循环调整平衡xpr.red =true;                        x = xp;                    }else{// 符合3种情况中的第三种情况中的第五种情况if(sr ==null|| !sr.red) {// sr为空或者为黑色if(sl !=null)// sl非空说明为红色，设置为黑色sl.red =false;// x的兄弟设置为红色xpr.red =true;// 右旋root = rotateRight(root, xpr);                            xpr = (xp = x.parent) ==null?null: xp.right;                        }// 符合3种情况中的第三种情况中的第六种情况if(xpr !=null) {// xpr颜色设置xpr.red = (xp ==null) ?false: xp.red;if((sr = xpr.right) !=null)// xpr 右孩子设置为黑色sr.red =false;                        }if(xp !=null) {                            xp.red =false;// 左旋操作root = rotateLeft(root, xp);                        }                        x = root;                    }                }            }// 和上边是对称操作else{// symmetricif(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 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;                    }                }            }        }    }

checkInvariants

对整棵树进行红黑树一致性的检查 目前仅在检查root是否落在table上时调用，满足红黑树的特性以及节点指向的正确性

static boolean checkInvariants(TreeNode t) {        TreeNode tp = t.parent, tl = t.left, tr = t.right,            tb = t.prev, tn = (TreeNode)t.next;// t的前一个节点的后一个节点应为tif(tb !=null&& tb.next != t)returnfalse;// tn的后一个节点的前一个节点应为tif(tn !=null&& tn.prev != t)returnfalse;// t的父节点的左子节点或右子节点应为tif(tp !=null&& t != tp.left && t != tp.right)returnfalse;// t的左子节点的父节点应为t并且 t的左子节点hash值小于t的hash值if(tl !=null&& (tl.parent != t || tl.hash > t.hash))returnfalse;// t的右子节点的父节点应为t并且 t的右子节点hash值大于t的hash值if(tr !=null&& (tr.parent != t || tr.hash < t.hash))returnfalse;// t和t的子节点不能同时是红色，红黑树特性if(t.red && tl !=null&& tl.red && tr !=null&& tr.red)returnfalse;// 左子节点递归检查if(tl !=null&& !checkInvariants(tl))returnfalse;// 右子节点递归检查if(tr !=null&& !checkInvariants(tr))returnfalse;returntrue;    }

总结

至此，关于TreeNode的代码讲解部分已经完成，类似的源码TreeMap等使用红黑树结构的类基本操作都是类似源码，可以自行查看，重要的部分在于插入和删除是如何做到的，在之后如何进行自平衡操作的，希望对各位读者有所帮助