接下来我们看一看这个方法
private void fixAfterInsertion(Entry<K,V> x) { //新插入的节点为红色节点 x.color = RED; //我们知道父节点为黑色时，并不需要进行树结构调整，只有当父节点为红色时，才需要调整 while (x != null && x != root && x.parent.color == RED) { //如果父节点是左节点，对应上表中情况1和情况2 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { Entry<K,V> y = rightOf(parentOf(parentOf(x))); //如果叔父节点为红色，对应于“父节点和叔父节点都为红色”，此时通过变色即可实现平衡 //此时父节点和叔父节点都设置为黑色，祖父节点设置为红色 if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { //如果插入节点是黑色，插入的是右子节点，通过【左右节点旋转】（这里先进行父节点左旋） if (x == rightOf(parentOf(x))) { x = parentOf(x); rotateLeft(x); } //设置父节点和祖父节点颜色 setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); //进行祖父节点右旋（这里【变色】和【旋转】并没有严格的先后顺序，达成目的就行） rotateRight(parentOf(parentOf(x))); } } else { //父节点是右节点的情况 Entry<K,V> y = leftOf(parentOf(parentOf(x))); //对应于“父节点和叔父节点都为红色”，此时通过变色即可实现平衡 if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { //如果插入节点是黑色，插入的是左子节点，通过【右左节点旋转】（这里先进行父节点右旋） if (x == leftOf(parentOf(x))) { x = parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); //进行祖父节点左旋（这里【变色】和【旋转】并没有严格的先后顺序，达成目的就行） rotateLeft(parentOf(parentOf(x))); } } } //根节点必须为黑色 root.color = BLACK; }源码中通过 rotateLeft 进行【左旋】，通过 rotateRight 进行【右旋】。都非常类似，我们就看一下【左旋】的代码，【左旋】规则如下：“逆时针旋转两个节点，让一个节点被其右子节点取代，而该节点成为右子节点的左子节点”。
private void rotateLeft(Entry<K,V> p) { if (p != null) { /** * 断开当前节点p与其右子节点的关联，重新将节点p的右子节点的地址指向节点p的右子节点的左子节点 * 这个时候节点r没有父节点 */ Entry<K,V> r = p.right; p.right = r.left; //将节点p作为节点r的父节点 if (r.left != null) r.left.parent = p; //将节点p的父节点和r的父节点指向同一处 r.parent = p.parent; //p的父节点为null，则将节点r设置为root if (p.parent == null) root = r; //如果节点p是左子节点，则将该左子节点替换为节点r else if (p.parent.left == p) p.parent.left = r; //如果节点p为右子节点，则将该右子节点替换为节点r else p.parent.right = r; //重新建立p与r的关系 r.left = p; p.parent = r; } }就算是看了上面的注释还是并不清晰，看下图你就懂了
get方法是通过二分查找的思想，我们看一下源码
public V get(Object key) { Entry<K,V> p = getEntry(key); return (p==null ? null : p.value); } /** * 从root节点开始遍历，通过二分查找逐步向下找 * 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过k.compareTo(p.key)比较传入的key和 * 根节点的key值； * 如果传入的key<root.key, 那么继续在root的左子树中找，从root的左孩子节点（root.left）开始； * 如果传入的key>root.key, 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始; * 如果恰好key==root.key，那么直接根据root节点的value值即可。 * 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找 */ //默认排序情况下的查找 final Entry<K,V> getEntry(Object key) { if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root; while (p != null) { int cmp = k.compareTo(p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } return null; } /** * 从root节点开始遍历，通过二分查找逐步向下找 * 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过自定义的排序算法 * cpr.compare(key, t.key)比较传入的key和根节点的key值，如果传入的key<root.key，那么 * 继续在root的左子树中找，从root的左孩子节点（root.left）开始：如果传入的key>root.key, * 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始;如果恰好key==root.key， * 那么直接根据root节点的value值即可。 * 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找 */ //自定义排序规则下的查找 final Entry<K,V> getEntryUsingComparator(Object key) { @SuppressWarnings("unchecked") K k = (K) key; Comparator<? super K> cpr = comparator; if (cpr != null) { Entry<K,V> p = root; while (p != null) { int cmp = cpr.compare(k, p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } } return null; } 六. remove方法