本文共 11885 字，大约阅读时间需要 39 分钟。
前言
红黑树（Red Black Tree） 是一种自平衡二叉查找树。JDK1.8中，当HashMap的链表达到一定长度后，会将链表转化为红黑树。同时，TreeMap中数据的存储结构就是红黑树。
红黑树
红黑树定义
红黑树是一个平衡的二叉树，但不是一个完美的平衡二叉树。红黑树是在普通二叉树上，对每个节点添加一个颜色属性形成的，同时整个红黑二叉树需要同时满足一下五条性质 ：
节点是红色或者是黑色 在树里面的节点不是红色的就是黑色的，没有其他颜色;
根节点是黑色 根节点总是黑色的;
每个叶节点（NIL或空节点）是黑色；
每个红色节点的两个子节点都是黑色的 连续的两个节点不能是连续的红色;
从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点
红黑树平衡性修正
红黑树主要通过三种方式对平衡进行修正，改变节点颜色、左旋和右旋。
变色
改变节点颜色，这是为满足上述第四个条件而设定的修正操作。事实上，在红-黑树中插入的节点都是红色的，这不是偶然的，因为插入一个红色节点比插入一个黑色节点违背红-黑规则的可能性更小。
左旋
左旋的过程是将父节点的右子树绕父节点逆时针旋转，使得父节点的右子树成为父节点的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。
右旋
右旋的过程是将父节点的左子树绕父节点顺时针旋转，使得父节点的左子树成为父节点的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。
红黑树的优势
红黑树的查询性能略微逊色于AVL树，因为它比AVL树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较，但是，红黑树在插入和删除上完爆AVL树，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多。
TreeMap中红黑树应用
TreeMap
TreeMap的实现是红黑树算法的实现。
定义
public class TreeMap extends AbstractMap implements NavigableMap , Cloneable, java.io.Serializable
重要属性
//比较器，因为TreeMap是有序的， //通过comparator接口我们可以对TreeMap的内部排序进行精密的控制 private final Comparator comparator; //TreeMap红-黑节点，为TreeMap的内部类 private transient Entry root; //容器大小 private transient int size = 0; //TreeMap修改次数 private transient int modCount = 0; //红黑树的节点颜色--红色 private static final boolean RED = false; //红黑树的节点颜色--黑色 private static final boolean BLACK = true;
节点结构
K key; V value; Entry left; Entry right; Entry parent; boolean color = BLACK;
TreeMap的关键方法
get方法
public V get(Object key) { Entry p = getEntry(key); return (p==null ? null : p.value); } final Entry getEntry(Object key) { // Offload comparator-based version for sake of performance if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable k = (Comparable ) key; Entry 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; } TreeMap的get(Object key)方法根据指定的key值返回对应的value，该方法调用了getEntry(Object key)得到相应的entry，然后返回entry.value。因此getEntry()是算法的核心。算法思想是根据key的自然顺序（或者比较器顺序）对二叉查找树进行查找，直到找到满足k.compareTo(p.key) == 0的entry。
put方法
public V put(K key, V value) { Entry t = root; if (t == null) { compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry parent; // split comparator and comparable paths Comparator cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable k = (Comparable ) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } Entry e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; } 上述代码中，首先在红黑树上找到合适的位置，然后创建新的entry并插入（当然，新插入的节点一定是树的叶子）。难点是调整函数fixAfterInsertion()，前面已经说过，调整往往需要：1.改变某些节点的颜色；2.对某些节点进行旋转。
private void fixAfterInsertion(Entry x) { //新节点的颜色是红色 x.color = RED; //当x不为根节点，并且x的父节点为红色时需要调整 while (x != null && x != root && x.parent.color == RED) { //判断x的父节点是否为x祖父节点的左子节点 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //获取x的叔父节点，即x父节点父节点的右子节点 Entry y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { //如果x的叔父节点为红色， //调整x的父节点和叔父节点为黑色， //调整x的祖父节点为红色， //调整结束后，x指向祖父节点。 setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == rightOf(parentOf(x))) { //如果x是其父节点的右子节点， //x指向其父节点， //以x为中心进行左旋操作 x = parentOf(x); rotateLeft(x); } //调整x父节点颜色为黑色， //调整x祖父节点颜色为红色， //以x的祖父节点为中心进行右旋操作 setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { //x的父节点是x祖父节点的右子节点 Entry y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { //叔父节点为红色， //处理逻辑跟上述x的父节点是x祖父节点的左子节点情形一样 setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == leftOf(parentOf(x))) { //如果x是其父节点的左子节点， //x指向其父节点， //以x为中心进行右旋操作 x = parentOf(x); rotateRight(x); } //调整x父节点颜色为黑色， //调整x祖父节点颜色为红色， //以x的祖父节点为中心进行左旋操作 setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } //根节点颜色为黑色 root.color = BLACK; }
总的来说，当前新增节点不为空，且不为根节点，并且父节点颜色为红色时需要循环调整红黑树结构。
调整时，新增节点所处的位置特征有三种：
插入节点的父节点和其叔父节点（祖父节点的另一个子节点）均为红色的；
插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的右子节点；
插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点。
第一种情况，修改父节点和叔父节点颜色为黑色，祖父节点颜色为红色，置祖父节点为新插入节点，以待后续处理；
第二种情况，置插入节点的父节点为先插入节点，并以此为中心进行左旋操作；
第三种情况，置祖父节点为红色，置父节点为黑色，并以祖父节点为中心进行右旋操作。
remove方法
红黑树的删除节点处理逻辑可以分为两步：以二叉查找树的逻辑删除节点；红黑树性质的修复。
public V remove(Object key) { Entry p = getEntry(key); if (p == null) return null; V oldValue = p.value; deleteEntry(p); return oldValue; } private void deleteEntry(Entry p) { modCount++; size--; if (p.left != null && p.right != null) { //查找节点p的“后继”节点,其条件如下： //p的右子树不空，则t的后继是其右子树中最小的那个元素。 //p的右孩子为空，则t的后继是其第一个向左走的祖先。 Entry s = successor(p); p.key = s.key; p.value = s.value; p = s; } Entry replacement = (p.left != null ? p.left : p.right); if (replacement != null) { replacement.parent = p.parent; if (p.parent == null) root = replacement; else if (p == p.parent.left) p.parent.left = replacement; else p.parent.right = replacement; p.left = p.right = p.parent = null; if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { root = null; } else { if (p.color == BLACK) fixAfterDeletion(p); if (p.parent != null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; } } } 删除过程可以简单分为两种情况：
- 删除点p的左右子树都为空，或者只有一棵子树非空。
- 删除点p的左右子树都非空。
对于第一种情况，直接将p删除（左右子树都为空时），或者用非空子树替代p（只有一棵子树非空时）；对于第二种情况，可以用p的后继s（树中大于x的最小的那个元素）代替p，然后使用第一种情况的处理办法删除s（此时s一定满足情况1，可以画画看）。
当删除节点为黑色的时候，才会触发调整函数fixAfterDeletion，通常有如下四种情况：
当前节点是黑色的，且兄弟节点是红色的（那么父节点和兄弟节点的子节点肯定是黑色的）；
当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的两个子节点均为黑色的；
当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的左子节点是红色，右子节点时黑色的；
当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的右子节点是红色，左子节点任意颜色。
private void fixAfterDeletion(Entry x) { while (x != root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { Entry sib = rightOf(parentOf(x)); if (colorOf(sib) == RED) { //x为左子节点，并且兄弟节点为红色， //调整兄弟节点为黑色，父节点为红色， //以父节点为中心左旋操作，sib指向左旋操作后x的兄弟节点 //此时节点x和其兄弟节点为黑色，父节点为红色 setColor(sib, BLACK); setColor(parentOf(x), RED); rotateLeft(parentOf(x)); sib = rightOf(parentOf(x)); } if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { //如果兄弟节点的两个子节点都为黑色 //调整兄弟节点为红色 //x指向x自身的父节点 setColor(sib, RED); x = parentOf(x); } else { if (colorOf(rightOf(sib)) == BLACK) { //如果兄弟节点的右子节点为黑色 //调整兄弟节点的左子节点为黑色 //调整兄弟节点颜色为红色 //以兄弟节点为中心进行右旋操作 //sib指向节点x的兄弟节点 setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } //调整sib的颜色为x节点父节点颜色 //调整x节点父节点颜色为黑色 //调整sib右子节点颜色为黑色 //以x的父节点为中心左旋操作，并将x指向root setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; } } else { // symmetric Entry sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } //调整节点x颜色为黑色 setColor(x, BLACK); }
x节点为右子节点的情况可以对称处理，不再赘述。
总结
本文阐述了红黑树的定义、性质以及红黑树的典型实现——TreeMap，详细描述了TreeMap在发生结构变化时的调整逻辑，希望读者能有所启发。
转载地址：http://msgmi.baihongyu.com/