平衡二叉树之红黑树（Red-Black Tree）简介及Java实现

[TOC]
#### 红黑树简介
红黑树（Red-Black Tree）也是一种自平衡二叉查找树，在前面的文当中，我们已经描述了[AVL树](https://www.datalearner.com/blog/1051540468259136)了。AVL树与红黑树很像，因此也经常被放到一起比较。

与其他平衡二叉树不同，红黑树的每个节点有个额外的位来存储节点的颜色（红色或者黑色）。这些颜色位保证了在树的插入和删除时能保持平衡。

尽管红黑树的平衡不是完美的，但是它也足够保证搜索的时间效率为$O(\log n)$。追踪节点的颜色仅仅需要每个节点多保存一位数据，因为它只有两种颜色。除此之外，它不保存任何其他信息，因此，它的内存使用和典型的[二叉查找树](https://www.datalearner.com/blog/1051540195789273)差不多，并不会造成额外的内存占用。

红黑树依靠节点的颜色来调整树的平衡（这和AVL树使用平衡因子来判断类似，后面会具体描述），其对颜色的要求如下：
1. 每个节点只能是红色或者黑色两种
2. 根节点是黑色的（但是这个规则有时候也不提，因为根节点总是可以从红色变成黑色，但是反过来不一定，它对分析的影响很小）
3. 所有的叶子节点（NIL）都是黑色的
4. 如果一个节点是红色的，那么它所有的子节点都是黑色的
5. 从给定的节点到它的后代叶子节点中包含的黑色节点数量是一样的

这里说一下红黑树的叶子节点是不包含任何信息的，这些叶子不需要在计算机内存中显式存在，使用空子指针就可以编码这个叶子节点。但是如果叶子确实是显式节点，它会简化了一些在红黑树上操作的算法。所以，为了节省执行时间，有时指向单个sentinel节点（而不是空指针）的指针执行所有叶节点的角色; 从内部节点到叶节点的所有引用然后指向sentinel节点。因此，通常也称红黑树的叶子节点为NIL节点（NIL Leaves,NIL是0的意思，暗指不包含任何信息）。

如下图就是一个典型的红黑树：

<center>![](https://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/500px-Red-black_tree_example.svg.png)

</center>

#### 红黑树的自平衡调整
红黑树的插入和删除操作会破坏树的颜色结构，所以需要重新调整节点的颜色来保证红黑树的性质符合上述要求，但这种操作消耗的计算也很小，因此依然可以保证时间复杂度在$O(\log n)$。

红黑树的调整包括旋转和变色两种。根据具体不同的情况来操作。以插入数据为例，典型的二叉查找树的插入操作是顺着二叉树向下，把新元素变成新的叶子节点。但是在红黑树中的操作不是这样，新元素的键会根据典型的二叉搜索树往下寻找，到大叶子节点（NIL 节点）后，会将该叶子节点去掉，然后把这个新元素变成这里的节点，并在新元素后面添加两个叶子节点。同时，该新节点的颜色是红色，新加的叶子节点的颜色是黑色。

完成上述操作之后，需要根据新加的节点周围的节点情况（这里共有4中case，后面表格中的case编号对应这里的情况）来进行调整（假设新加的节点是N）：

1. N是根节点
2. N的父节点P是黑色的
3. N的父节点P是红色的且N的叔叔节点U是红色的
4. N的父节点P是红色的且N的叔叔节点U是黑色的

在前面的规则中：
1. 规则1（每个节点要么是红色要么是黑色）和规则3（所有的叶子节点都是黑色）总是成立。
2. 规则2（根节点是黑色）在插入第一个节点的时候就能保证。
3. 规则4（红色节点只能有黑色的子节点）可能会在插入新节点时候（因为新加的节点都是红色），将节点的黑色变成红色操作的时候以及旋转的时候被破坏。
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](https://stackoverflow.com/questions/16257761/difference-between-red-black-trees-and-avl-trees)上也有人给了一个比较：

对于小数据集：
- 插入操作：红黑树和AVL树最坏旋转次数一样的，但是红黑树的平均旋转次数更少，因此速度更快。
- 查找操作：AVL树更快，因为它的深度更小
- 删除操作：AVL树最坏情况下旋转次数比红黑树多，平均旋转次数也比红黑树多，因此红黑树嘟嘟更快。

对于大规模数据集：
- 插入操作：由于二者都是以最坏的情况旋转，而插入之前还需要进行查找操作，AVL查找速度更快，因此AVL效率更好。
- 查找操作：AVL树更快，理由如上
- 删除操作：AVL树平均来说更好，但是最坏的情况下红黑树更快。

#### 红黑树的Java实现
```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

平衡二叉树之红黑树（Red-Black Tree）简介及Java实现

欢迎大家关注DataLearner官方微信，接受最新的AI技术推送

相关博客

最热博客