平衡二叉树之红黑树（Red-Black Tree）简介及Java实现
[TOC]
红黑树简介
红黑树（Red-Black Tree）也是一种自平衡二叉查找树，在前面的文当中，我们已经描述了AVL树了。AVL树与红黑树很像，因此也经常被放到一起比较。
与其他平衡二叉树不同，红黑树的每个节点有个额外的位来存储节点的颜色（红色或者黑色）。这些颜色位保证了在树的插入和删除时能保持平衡。
尽管红黑树的平衡不是完美的，但是它也足够保证搜索的时间效率为O(\log n)。追踪节点的颜色仅仅需要每个节点多保存一位数据，因为它只有两种颜色。除此之外，它不保存任何其他信息，因此，它的内存使用和典型的二叉查找树差不多，并不会造成额外的内存占用。
红黑树依靠节点的颜色来调整树的平衡（这和AVL树使用平衡因子来判断类似，后面会具体描述），其对颜色的要求如下：
- 每个节点只能是红色或者黑色两种
- 根节点是黑色的（但是这个规则有时候也不提，因为根节点总是可以从红色变成黑色，但是反过来不一定，它对分析的影响很小）
- 所有的叶子节点（NIL）都是黑色的
- 如果一个节点是红色的，那么它所有的子节点都是黑色的
- 从给定的节点到它的后代叶子节点中包含的黑色节点数量是一样的
这里说一下红黑树的叶子节点是不包含任何信息的，这些叶子不需要在计算机内存中显式存在，使用空子指针就可以编码这个叶子节点。但是如果叶子确实是显式节点，它会简化了一些在红黑树上操作的算法。所以，为了节省执行时间，有时指向单个sentinel节点（而不是空指针）的指针执行所有叶节点的角色; 从内部节点到叶节点的所有引用然后指向sentinel节点。因此，通常也称红黑树的叶子节点为NIL节点（NIL Leaves,NIL是0的意思，暗指不包含任何信息）。
如下图就是一个典型的红黑树：
红黑树的自平衡调整
红黑树的插入和删除操作会破坏树的颜色结构，所以需要重新调整节点的颜色来保证红黑树的性质符合上述要求，但这种操作消耗的计算也很小，因此依然可以保证时间复杂度在O(\log n)。
红黑树的调整包括旋转和变色两种。根据具体不同的情况来操作。以插入数据为例，典型的二叉查找树的插入操作是顺着二叉树向下，把新元素变成新的叶子节点。但是在红黑树中的操作不是这样，新元素的键会根据典型的二叉搜索树往下寻找，到大叶子节点（NIL 节点）后，会将该叶子节点去掉，然后把这个新元素变成这里的节点，并在新元素后面添加两个叶子节点。同时，该新节点的颜色是红色，新加的叶子节点的颜色是黑色。
完成上述操作之后，需要根据新加的节点周围的节点情况（这里共有4中case，后面表格中的case编号对应这里的情况）来进行调整（假设新加的节点是N）：
- N是根节点
- N的父节点P是黑色的
- N的父节点P是红色的且N的叔叔节点U是红色的
- N的父节点P是红色的且N的叔叔节点U是黑色的
在前面的规则中：
- 规则1（每个节点要么是红色要么是黑色）和规则3（所有的叶子节点都是黑色）总是成立。
- 规则2（根节点是黑色）在插入第一个节点的时候就能保证。
- 规则4（红色节点只能有黑色的子节点）可能会在插入新节点时候（因为新加的节点都是红色），将节点的黑色变成红色操作的时候以及旋转的时候被破坏。
- 规则5（给定节点到所有叶子节点的路径上黑色节点数量是一样的）会在加入一个黑色节点、变色以及旋转的时候被破坏。
上述四种情况对应的操作如下：
| Case | Property | Handle |
|---|---|---|
| Case1 | N是根节点 | 直接插入即可 |
| Case2 | N的父节点P是黑色的 | 将“父节点”设为黑色； 将“叔叔节点”设为黑色； 将“祖父节点”设为“红色”； 将“祖父节点”设为“当前节点”(红色节点)； 递归操作。 |
| Case3 | N的父节点P是红色的且N的叔叔节点U是红色的 | 将“父节点”作为“新的当前节点”； 以“新的当前节点”为支点进行左旋。 |
| Case4 | N的父节点P是红色的且N的叔叔节点U是黑色的 | 将“父节点”设为“黑色”； 将“祖父节点”设为“红色”； 以“祖父节点”为支点进行右旋。 |
红黑树与AVL树的比较
红黑树与AVL树相比没有那么严格的平衡，但是查找、插入和删除的效率是一样的。因此在实际中红黑树更广泛被使用。因为红黑树的实现相对简单，在常规操作上也更容易。JDK里面的TreeMap、TreeSet和HashMap（JDK 8）都使用红黑树来实现。
值得注意的是，在插入操作的时候，AVL树需要执行的旋转次数更多，有O(\log n)，而后者只需要O(1)。更多的旋转意味着更多的内存写入，这也是耗时的操作。所以更新操作的时候红黑树比AVL树更快。
具体的，StackOverflow上也有人给了一个比较：
对于小数据集：
- 插入操作：红黑树和AVL树最坏旋转次数一样的，但是红黑树的平均旋转次数更少，因此速度更快。
- 查找操作：AVL树更快，因为它的深度更小
- 删除操作：AVL树最坏情况下旋转次数比红黑树多，平均旋转次数也比红黑树多，因此红黑树嘟嘟更快。
对于大规模数据集：
- 插入操作：由于二者都是以最坏的情况旋转，而插入之前还需要进行查找操作，AVL查找速度更快，因此AVL效率更好。
- 查找操作：AVL树更快，理由如上
- 删除操作：AVL树平均来说更好，但是最坏的情况下红黑树更快。
红黑树的Java实现
package com.huawei.machinelearning.data.structure;// RedBlackTree class
//
// CONSTRUCTION: with a negative infinity sentinel
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x (unimplemented)
// Comparable find( x ) --> Return item that matches x
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print all items
// ******************ERRORS********************************
// Exceptions are thrown by insert if warranted and remove.
/**
* Implements a red-black tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class RedBlackTree {
/**
* Construct the tree.
*/
public RedBlackTree( ) {
header = new RedBlackNode( null );
header.left = header.right = nullNode;
}
/**
* Compare item and t.element, using compareTo, with
* caveat that if t is header, then item is always larger.
* This routine is called if is possible that t is header.
* If it is not possible for t to be header, use compareTo directly.
*/
private final int compare( Comparable item, RedBlackNode t ) {
if( t == header )
return 1;
else
return item.compareTo( t.element );
}
/**
* Insert into the tree.
* @param item the item to insert.
* @throws DuplicateItemException if item is already present.
*/
public void insert( Comparable item ) {
current = parent = grand = header;
nullNode.element = item;
while( compare( item, current ) != 0 ) {
great = grand; grand = parent; parent = current;
current = compare( item, current ) < 0 ?
current.left : current.right;
// Check if two red children; fix if so
if( current.left.color == RED && current.right.color == RED )
handleReorient( item );
}
// Insertion fails if already present
if( current != nullNode )
throw new DuplicateItemException( item.toString( ) );
current = new RedBlackNode( item, nullNode, nullNode );
// Attach to parent
if( compare( item, parent ) < 0 )
parent.left = current;
else
parent.right = current;
handleReorient( item );
}
/**
* Remove from the tree.
* @param x the item to remove.
* @throws UnsupportedOperationException if called.
*/
public void remove( Comparable x ) {
throw new UnsupportedOperationException( );
}
/**
* Find the smallest item the tree.
* @return the smallest item or null if empty.
*/
public Comparable findMin( ) {
if( isEmpty( ) )
return null;
RedBlackNode itr = header.right;
while( itr.left != nullNode )
itr = itr.left;
return itr.element;
}
/**
* Find the largest item in the tree.
* @return the largest item or null if empty.
*/
public Comparable findMax( ) {
if( isEmpty( ) )
return null;
RedBlackNode itr = header.right;
while( itr.right != nullNode )
itr = itr.right;
return itr.element;
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public Comparable find( Comparable x ) {
nullNode.element = x;
current = header.right;
for( ; ; ) {
if( x.compareTo( current.element ) < 0 )
current = current.left;
else if( x.compareTo( current.element ) > 0 )
current = current.right;
else if( current != nullNode )
return current.element;
else
return null;
}
}
/**
* Make the tree logically empty.
*/
public void makeEmpty( ) {
header.right = nullNode;
}
/**
* Print all items.
*/
public void printTree( ) {
printTree( header.right );
}
/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the tree.
*/
private void printTree( RedBlackNode t ) {
if( t != nullNode ) {
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( ) {
return header.right == nullNode;
}
/**
* Internal routine that is called during an insertion
* if a node has two red children. Performs flip and rotations.
* @param item the item being inserted.
*/
private void handleReorient( Comparable item ) {
// Do the color flip
current.color = RED;
current.left.color = BLACK;
current.right.color = BLACK;
if( parent.color == RED ) // Have to rotate
{
grand.color = RED;
if( ( compare( item, grand ) < 0 ) !=
( compare( item, parent ) < 0 ) )
parent = rotate( item, grand ); // Start dbl rotate
current = rotate( item, great );
current.color = BLACK;
}
header.right.color = BLACK; // Make root black
}
/**
* Internal routine that performs a single or double rotation.
* Because the result is attached to the parent, there are four cases.
* Called by handleReorient.
* @param item the item in handleReorient.
* @param parent the parent of the root of the rotated subtree.
* @return the root of the rotated subtree.
*/
private RedBlackNode rotate( Comparable item, RedBlackNode parent ) {
if( compare( item, parent ) < 0 )
return parent.left = compare( item, parent.left ) < 0 ?
rotateWithLeftChild( parent.left ) : // LL
rotateWithRightChild( parent.left ) ; // LR
else
return parent.right = compare( item, parent.right ) < 0 ?
rotateWithLeftChild( parent.right ) : // RL
rotateWithRightChild( parent.right ); // RR
}
/**
* Rotate binary tree node with left child.
*/
private static RedBlackNode rotateWithLeftChild( RedBlackNode k2 ) {
RedBlackNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
/**
* Rotate binary tree node with right child.
*/
private static RedBlackNode rotateWithRightChild( RedBlackNode k1 ) {
RedBlackNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
private static class RedBlackNode {
// Constructors
RedBlackNode( Comparable theElement ) {
this( theElement, null, null );
}
RedBlackNode( Comparable theElement, RedBlackNode lt, RedBlackNode rt ) {
element = theElement;
left = lt;
right = rt;
color = RedBlackTree.BLACK;
}
Comparable element; // The data in the node
RedBlackNode left; // Left child
RedBlackNode right; // Right child
int color; // Color
}
private RedBlackNode header;
private static RedBlackNode nullNode;
static // Static initializer for nullNode
{
nullNode = new RedBlackNode( null );
nullNode.left = nullNode.right = nullNode;
}
private static final int BLACK = 1; // Black must be 1
private static final int RED = 0;
// Used in insert routine and its helpers
private static RedBlackNode current;
private static RedBlackNode parent;
private static RedBlackNode grand;
private static RedBlackNode great;
// Test program
public static void main( String [ ] args ) {
RedBlackTree t = new RedBlackTree( );
final int NUMS = 400000;
final int GAP = 35461;
System.out.println( "Checking... (no more output means success)" );
for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( new Integer( i ) );
if( ((Integer)(t.findMin( ))).intValue( ) != 1 ||
((Integer)(t.findMax( ))).intValue( ) != NUMS - 1 )
System.out.println( "FindMin or FindMax error!" );
for( int i = 1; i < NUMS; i++ )
if( ((Integer)(t.find( new Integer( i ) ))).intValue( ) != i )
System.out.println( "Find error1!" );
}
}
/**
* Exception class for duplicate item errors
* in search tree insertions.
* @author Mark Allen Weiss
*/
class DuplicateItemException extends RuntimeException
{
/**
* Construct this exception object.
*/
public DuplicateItemException( )
{
super( );
}
/**
* Construct this exception object.
* @param message the error message.
*/
public DuplicateItemException( String message )
{
super( message );
}
}
参考文献：
https://stackoverflow.com/questions/16257761/difference-between-red-black-trees-and-avl-trees
https://www.java-tips.org/java-se-tips-100019/24-java-lang/1904-red-black-tree-implementation-in-java.html
https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
欢迎大家关注DataLearner官方微信，接受最新的AI技术推送
