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

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

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

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

红黑树依靠节点的颜色来调整树的平衡（这和AVL树使用平衡因子来判断类似，后面会具体描述），其对颜色的要求如下：

每个节点只能是红色或者黑色两种
根节点是黑色的（但是这个规则有时候也不提，因为根节点总是可以从红色变成黑色，但是反过来不一定，它对分析的影响很小）
所有的叶子节点（NIL）都是黑色的
如果一个节点是红色的，那么它所有的子节点都是黑色的
从给定的节点到它的后代叶子节点中包含的黑色节点数量是一样的

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

Case	Property	Handle
Case1	N是根节点	直接插入即可
Case2	N的父节点P是黑色的	将“父节点”设为黑色；将“叔叔节点”设为黑色；将“祖父节点”设为“红色”；将“祖父节点”设为“当前节点”(红色节点)；递归操作。
Case3	N的父节点P是红色的且N的叔叔节点U是红色的	将“父节点”作为“新的当前节点”；以“新的当前节点”为支点进行左旋。
Case4	N的父节点P是红色的且N的叔叔节点U是黑色的	将“父节点”设为“黑色”；将“祖父节点”设为“红色”；以“祖父节点”为支点进行右旋。

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 ); } }

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

DataLearner 官方微信

红黑树的自平衡调整

红黑树与AVL树的比较

红黑树的Java实现

热门博客