与数组相比，链表提升了插入元素的效率。因为数组在插入元素时，需要移动后续元素的位置；而链表只需要改变后继元素的 prev 属性。然而在查询元素时，链表需要遍历所有元素，并不高效。借助于红黑树，既能提升查询的效率，又能保证插入的效率。
为什么说红黑树有助于提升查询和插入的效率呢？因为红黑树本质上是一棵完美平衡的二叉查找树，可以通过节点的有序性保证查找和插入操作的便捷，其作时间复杂度就是树的高度 O(lgN)，自然比链表的 O(N) 高效很多。红黑树有如下两个特征：有序性、平衡性。我们讲一棵红黑树是有序的，通常指的是树中的节点会遵照 key 键自小到大或自大到小的顺序。有序性是实现二叉树完美平衡的先决条件。完美平衡指的是树从根节点到每个底部节点的高度大致相当，这样才能保证查询操作的时间复杂度为 O(lgN)。设想当二叉树出现了单边有值的极端情况时，其查询效率就和链表一样同为 O(N)。因此，实际上是完美平衡的二叉树便于查询节点，而红黑树是完美平衡二叉树的一种实现方式。
犹如红黑树是完美平衡树的一种实现方式，红黑树自身也有多种实现方式。本文所介绍的红黑树（即算法红宝书中的红黑树）是基于 2-3 树实现的。在插入元素方面，2-3 树所具有的优点为：当向 2- 节点插入新节点时，通过将 2- 节点转变成 3- 节点，可以迅速接纳新的节点；当向 3- 节点插入新节点时，通过将 3- 节点转变成 4- 节点，再将 4- 节点转变成 3 个 2- 节点构成的子树，也可以迅速接纳新的节点。在实现上，若使用不同的数据类型表示 2- 节点或 3- 节点及其附属信息，接着实现不同类型节点的转换，这样势必会使程序相当复杂，且容易遇上性能问题。红黑树就应运而生了。
红宝书中的红黑树有如下性质：
红链接均为左链接
没有任何一个节点同时和两条红链接相连
该树是完美黑色平衡的，即任意空链接到根节点的路径上的黑链接数量相同
第一条性质指的是红黑树中构成 3- 节点的方式总是唯一的。当红链接为右链接时，需要通过左旋操作将其转变为标准的左链接 3- 节点。第二条性质包含以下两种情况：父子节点不能同时为红链接（无论子节点是左链接还是右链接）；父节点下的两个子节点不能同时为红链接。当父子节点同时为红链接时，可通过旋转操作将其转变为 3 个 2- 节点的子树，这样就能同时消除父子节点的红链接。当父节点下的两个子节点同时为红链接时，可通过颜色转换操作将两个子节点变为黑链接。从 2-3 树的角度直观地看第二条性质，也是指红黑树中的每一个节点不能同时从属于两个 3- 节点。因此，第二条性质和第三条性质一样，表明红黑树是和 2-3 树一一对应的。
需要说明的是：2- 节点是包含 2 个子节点的节点，在红黑树中就是普通节点；3- 节点由两个节点构成，其下包含 3 个子节点，在红黑树中就是左子节点为红链接；4- 节点由三个节点构成，其下包含 4 个子节点，在红黑树中就是左右两侧子节点均为红链接。当分析红黑树的直观视图时，我们只需要考虑 2- 节点和 3- 节点。在插入和删除元素时，我们才需要考虑 4- 节点。红黑树的直观视图就是二叉树。特别的，当将 3- 节点拉平后，红黑树的直观视图就会变成 2-3 树。
private static final boolean RED = true ; private static final boolean BLACK = false ; private class Node { Key key ; Value value ; Node left , right ; // 左右子树 int N ; // 节点总数 boolean color ; // 标识红链接或黑链接 Node ( Key key , Value value , int N , boolean color ){ this . key = key ; this . value = value ; this . N = N ; this . color = color ; }
}
private boolean isRed ( Node x ){ if ( x == null ) return false ; return x . color == RED ; }
在分析红黑树时，我们需要致力于解决如下这样一个命题：怎样在插入和删除节点时保证树的平衡性？
1 左旋、右旋、颜色转换
红黑树抽象了三种抽象操作：左旋转、右旋转和颜色转换。这三种抽象操作都是局部变换。简单地说，左旋转用于将红链接从右链接转变成左链接，即红链接均为左链接的标准红黑树；右旋转用于将父节点和左子节点均为红链接的子树转变成 3 个 2- 节点的子树；颜色转换将两个子节点同时为红链接的子树转变成 3 个 2- 节点的子树，同时子树的根节点转变为红链接，颜色转换操作可以向上递归，以实现整颗红黑树中不能有两个子节点同时为红链接。
1.1 左旋
Node rotateLeft ( Node h ){ Node x = h . right ; // 取出原红链接节点 x h . right = x . left ; // 将中间部分 x.left 置于左节点 h 下 x . left = h ; // 因 x 将作为子树的根节点，将左节点 h 置为红链接节点 x 的左子节点 x . color = h . color ; // 不改变子树根节点的颜色 h . color = RED ; // 将子树中的红链接节点置为 h，即左移 x . N = h . N ; // 调整节点数目 h . N = 1 + size ( h . left ) + size ( h . right ); return x ; // 返回子树的根节点 }
上文已指出，左旋的目的就是将作为右链接的红链接转变为标准的左链接。
1.2 右旋
Node rotateRight ( Node h ){ Node x = h . left ; // 取出原红链接节点 x h . left = x . right ; // 将中间部分 x.left 置于右节点 h 下 x . right = h ; // 因 x 将作为子树的根节点，右节点 h 置为红链接节点 x 的右子节点 x . color = h . color ; // 不改变子树根节点的颜色 h . color = RED ; // 将子树中的红链接节点置为 h，即右移 x . N = h . N ; // 调整节点数目 h . N = 1 + size ( h . left ) + size ( h . right ); return x ; // 返回子树的根节点 }
右旋的目的需要结合使用场景，即当在父节点和左子节点同时为红链接时，通过右旋和颜色转换可以将子树转变为包含 3 个 2- 节点的子树。试想一下，当父节点和左侧子节点都为红链接时，即上图中 less than E 子树的根节点也是红链接，右旋操作就可以使旋转后的根节点 E 与其两侧子节点构成 4- 节点（即两侧子节点同时为红链接）。这时再通过颜色转换就可以把这两个子节点均置为黑链接，以避免单个节点同时和两条红链接相连。图示参见节点插入部分。
1.3 颜色转换
void flipColors ( Node h ){ h . color = RED ; // 根节点置为红链接 h . left . color = BLACK ; // 左右子节点置为黑链接 h . right . color = BLACK ; }
上文已经指出，在父节点和左侧子节点同时为红链接的情形下，通过右旋操作可以使祖父节点拥有两个红链接子节点，再通过颜色转换可以将这两个节点都转换成黑链接。因为左旋、右旋和颜色转换都基于红链接，将子树的根节点置为红链接有助于向上递归调整树的平衡性（即使得左旋、右旋、颜色转换操作能作用于自根节点始的整棵树）。
2 节点插入
节点插入需要针对以下情况：
当插入对象为 2- 节点时，向左插入就是在根节点左侧直接添加一个红链接，使父子节点构成一个 3- 节点；向右插入就是在根节点右侧先添加一个红链接，然后通过左旋反转父子节点的位置。
当插入对象为 3- 节点时，向左插入就使得父子节点同时为红链接，因此就需要通过右旋和颜色转换将其转变为包含 3 个 2- 节点的子树；中间插入就使得父子节点既同时是红链接，子节点又是非法的右链接，因此先需通过左旋将子树变更为向左插入一样的形态，然后再沿用向左插入的调整策略；向右插入可以通过颜色转换将两个子节点变为黑链接。完成以上操作后，向上递归调整自根节点始的整棵树。
插入算法的实现如下：
private Node root ; public void put ( Key key , Value val ){ root = put ( root , key , val ); root . color = BLACK ; // 根节点始终为黑链接 }
private Node put ( Node h , Key key , Value val ){ if ( h == null ) return new Node ( key , val , 1 , RED ); // 创建根节点或底部节点 // 向下递归插入节点 int cmp = key . CompareTo ( h . key ); if ( cmp < 0 ) h . left = put ( h . left , key , val ); else if ( cmp > 0 ) h . right = put ( h . right , key , val ); else h . val = val ; // 向上递归调整树的平衡性 // [左旋]，[右旋，颜色转换]是连贯一体的操作，可能有，也可能没有 // 红链接为右链接，左旋，针对 2- 节点或 3-节点中插入情况 // 可能会引起向上递归执行左旋操作 if ( isRed ( h . right ) ! isRed ( h . left )) h = rotateLeft ( h ); // 父子节点均为红链接，右旋 if ( isRed ( h . left ) isRed ( h . left . left )) h = rotateRight ( h ); // 两侧子节点均为红链接，颜色转换 if ( isRed ( h . left ) isRed ( h . right )) h = flipColors ( h ); // 调整节点数目 h . Number = Size ( h . left ) + Size ( h . right ) + 1 ; return h ; // 返回根节点，便于向上递归 }
3 节点删除
可想而知，当待删除的节点在 3- 节点中，如果 3- 节点在底部，那么这个节点就可以直接删除；如果 3- 节点不在底部，就可以用该节点的前驱或后继节点替换这个节点，然后再删除这个节点。当删除的节点在 2- 节点中，删除操作将破坏树的平衡性，这时就需要从父节点或兄弟节点中借一个节点构成 3- 节点或 4- 节点，然后再执行删除操作。在删除节点的过程中，程序会自顶向下构建 3- 节点或 4- 节点；删除结点后，再自底向上拆解 4- 节点。
需要指出的是，上文中左旋、右旋操作所具有的一般性为：即便子节点不是红链接，左旋、右旋在反转父子节点时，还能创建红链接。因此，构建 3- 节点需要借助于左旋、右旋操作；构建 4- 节点借助于反向颜色转换操作。
3.1 反向颜色转换
反向颜色转换是上文 flipColors 方法的反向操作，即将左右子节点均置为红链接，这会使得单侧父子节点构成一个 3- 节点（可视为将父节点借给子节点），同时父节点和两侧子节点又会构成一个 4- 节点。
void moveFlipColors ( Node h ){ h . color = Black ; h . left . color = Red ; h . right . color = Red ; }
3.2 左移
左移操作适用于子树中的最小键，即左侧节点。对比上文，左移操作包含如下两个步骤：
通过反向颜色转换 moveFlipColors 操作构建 4- 节点。
若右侧为 3- 节点，将 3- 节点中的最小键左移到左节点下，使左节点变为 3- 节点。这时需要通过颜色转换 flipColors 拿掉 4- 节点。
private Node moveRedLeft ( Node h ){ moveFlipColors ( h ); // 从父节点中借一个 if ( isRed ( h . right . left )){ // 兄弟节点不是 2- 节点，从兄弟节点中借一个 h . right = rotateRight ( h . right ); h = rotateLeft ( h ); flipColors ( h ); // 从兄弟节点借了一个后，把从父节点中借来的还回去 }
return h ; }
3.3 右移
右移操作适用于子树中的最大键，即右侧节点。同样包含两个步骤：
通过反向颜色转换 moveFlipColors 操作构建 4- 节点。
若左侧为 2- 节点，将该 2- 节点的父节点右移，使右节点变为 3- 节点。这时需要通过颜色转换 flipColors 拿掉 4- 节点。
private Node moveRedRight ( Node h ){ moveFlipColors ( h ); // 从父节点中借一个 if (! isRed ( h . left . left )){ // 兄弟节点是 2- 节点，从兄弟节点中借一个 h = rotateRight ( h ); flipColors ( h ); // 从兄弟节点借了一个后，把从父节点中借来的还回去 }
return h ; }
3.4 再平衡
无论在删除左侧节点还是在删除右侧节点时，都可能会在右侧创建新的红链接，所以我们需要通过左旋操作移除该红链接。且删除操作会破坏红黑树的性质，使红黑树下拥有不合法的作为右链接的红链接，或者父节点和左子节点同时为红链接，或者两侧子节点同时为红链接，这时就需要借助节点插入时的左旋、右旋、颜色转换操作逐级向上调整了。
private Node balance ( Node h ){ // 删除左节点可能会创建 4- 节点，右链接为红链接 // 删除右节点可能会使用左旋创建居于右侧的红链接 // 两种情况均通过 rotateLeft 还原 if ( isRed ( h . right )) h = rotateLeft ( h ); // 和节点插入时相同，通过[左旋]、[右旋，颜色转换]调整树的平衡性 if ( isRed ( h . right ) ! isRed ( h . left )) h = rotateLeft ( h ); if ( isRed ( h . left ) isRed ( h . left . left )) h = rotateRight ( h ); if ( isRed ( h . left ) isRed ( h . right )) flipColors ( h ); h . N = size ( h . left ) + size ( h . right ) + 1 ; return h ; }
3.5 删除最小键
public void deleteMin (){ // 当 flipColors, moveFlipColors 由同一个函数实现时，需要将根节点置红，以便进行反向颜色转换 if (! isRed ( root . left ) ! isRed ( root . right )){ root . color = Red ; }
root = deleteMin ( root ); if ( ! isEmpty () ) root . color = Black ; // 根节点颜色复原 }
private Node deleteMin ( Node h ){ // h 就是为最小键，置为 null 移除 if ( h . left == null ) return null ; // 向下递归构建 3- 节点和 4- 节点，并删除节点 // 左子节点为 2- 节点，通过左移操作向右子节点或父节点中借一个 if (! isRed ( h . left ) ! isRed ( h . left . left )) h = moveRedLeft ( h ); h . left = deleteMin ( h . left ); // 向上递归移除临时的 4- 节点，调整树的平衡性 return balance ( h ); }
3.6 删除最大键
public void deleteMax (){ if (! isRed ( root . left ) isRed ( root . right )){ root . color = Red ; }
root = deleteMax ( root ); if ( ! isEmpty () ) root . color = Black ; }
private Node deleteMax ( Node h ){ // 左子节点为红链接时，通过右旋将其给到右侧，以构建 3- 节点 if ( isRed ( h . left )){ h = rotateRight ( h ); }
// h 就是为最大键，置为 null 移除 if ( h . right == null ){ return null ; }
// 向下递归构建 3- 节点和 4- 节点，并删除节点 // 右子节点为 2- 节点，通过右移操作向左子节点或父节点中借一个 if (! isRed ( h . right ) ! isRed ( h . right . left )){ h = moveRedRight ( h ); }
h . right = deleteMax ( h . right ); // 向上递归移除临时的 4- 节点，调整树的平衡性 return balance ( h ); }
3.7 删除节点
public void delete ( Key key ){ if (! isRed ( root . left ) ! isRed ( root . right )){ root . color = Red ; }
root = delete ( root , key ); if ( ! isEmpty () ) root . color = Black ; }
private Node delete ( Node h , Key key ){ if ( key . compareTo ( h . key ) < 0 ){ // 向下递归构建 3- 节点和 4- 节点，并删除节点 // 左子节点为 2- 节点，通过左移操作向右子节点或父节点中借一个 if (! isRed ( h . left ) ! isRed ( h . left . left )) h = moveRedLeft ( h ); // 递归删除 h . left = delete ( h . left , key ); }
else { // 左子节点为红链接时，通过右旋将其给到右侧，以构建 3- 节点 if ( isRed ( h . left )) h = rotateRight ( h ); // 无后继节点，意味待删除节点为底部节点，置为 null 删除 if ( key . compareTo ( h . key ) == 0 ( h . right == null )) return null ; // 向下递归构建 3- 节点和 4- 节点，并删除节点 // 右子节点为 2- 节点，通过右移操作向左子节点或父节点中借一个 if (! isRed ( h . right ) ! isRed ( h . right . left )) h = moveRedRight ( h ); // 使用后继节点替换 if ( key . compareTo ( h . key ) == 0 ){ h . val = get ( h . right , min ( h . right ). key ); h . key = min ( h . right ). key ; h . right = deleteMin ( h . right ); }
// 递归删除 else h . right = delete ( h . right , key ); }
return balance ( h ); }
4 小记
这篇文章是我在理解 HashMap 过程中的一阵整理。回头想想，仍觉得自己对红黑树的理解不是很透彻。留在网上暂作为一种记录，以便于渐进式修改。
5 参考
标签：红黑树
