红黑树

作者: 我是小曼巴 | 来源:发表于2020-04-03 18:14 被阅读0次

数据结构—树—红黑树
TreeMap
数据结构与算法-AVL 红黑树
[转载]红黑树
拿下红黑树
红黑树
彻底理解红黑树（二）之插入
彻底理解红黑树（三）之删除
Golang红黑树
数据结构红黑树添加、修改原理分析

定义

AVL树的另一种变种就是红黑树。对红黑树的操作在最坏情形下花费O(logN)时间。
红黑树是具有下列着色性质的二叉查找树：

每一个节点或者着成红色，或者着成黑色。
根是黑色的。
如果一个节点是红色的，那么它的子节点必须是黑色的。
从一个节点到所有null引用的路径必须包含相同数目的黑色节点。

以上的性质保证了红黑树的高度最多是2log(N+1)。因此查找操作的时间复杂度保证为对数。

红黑树的例子如下。图中的红黑树显然满足条件1,2,3,4；对于条件4：比如根节点30，到所有15个null引用的路径上，黑色节点数都是一样的，为2；

图1：红黑树

自底向上的插入

新插入的项通常会作为叶子节点放到树中。如果把该叶子节点涂成黑色，那么必定违反条件4，因为会建立一条更长的黑节点的路径。因此，这一项必须涂成红色。所以红黑树新插入的项必定为红色节点。
插入的步骤如下：
1）根据二叉查找性质，首先找到插入点;
2）若父节点为黑色，插入完成;
3）若父节点为红色，会违反条件3，所以需要调整；根据父节点的兄弟节点S的颜色，分为下面两种情形：
a. 这个父节点的兄弟节点为黑色或者为空（即没有兄弟节点）
若插入元素X为P的左儿子，则在P和G之间进行单旋转；若X为P的右儿子，则在X，P，G之间进行双旋转。这两种情形下，子树的新根均被涂成黑色，因此即使原来的曾祖是红色的，也不会出现两个相邻红色节点的情况；同样关键的是通向B，C路径上的黑色节点个数黑色节点个数保持不变（指的是原来子树的根到B和C的路径上的黑色节点个数和旋转之后的子树的根到B和C的路径上的黑色节点个数一样）。

图2：S节点为黑色时的旋转和着色
b. 这个父节点的兄弟节点为红色的
旋转操作仍然不变，只是旋转过后，为了保证从子树的根到B和C的路径上黑色节点数不变，P，G，S中只能有一个黑色节点，所以必须把新根和S节点涂成红色，G涂成黑色。这种情况下，如果曾祖也是红色的，那么会出现曾祖和新根两个连续的红色节点。此时，我们需要将这个过程朝着根的方向上滤，直到不再有两个相连的红色节点或者到达根。这种情况可以通过下面自顶向下查找过程规避掉，所以编程实现时，完全可以只考虑情况a即可。

图3：S节点为红色时的旋转和着色

自顶向下红黑树

自顶向下的插入在寻找插入点的过程中对树进行调整，保证S不会为红。即保证了上面的b情况不会出现。
查找过程中：
1）当前节点X有两个红儿子，则让X变红，两儿子变黑（若X为根，则变红之后再变黑）。此时，若X的父节点为红，则出现两红相连，但X的父节点的兄弟节点不可能为红，此时按照图2所示进行旋转和变色即可。

图4：颜色翻转

2）其他情况继续向下遍历。
3）找到插入点插入即可。
以图1红黑树为例，我们要将45插入到该树中。在沿树向下的过程中，我们看到50有两个红色儿子，因此我们进行一次颜色翻转，使得50变红，40和55变黑。那么，50和60这对父子节点均为红色，那么在60和70之间进行一次单旋转，使得60是30的右子树的黑根，而70和50都是红的。当到达树叶时，把45作为红节点插入，由于父节点是黑色的，因此插入完成，不需要旋转调整颜色。

图5：自顶向下插入例子
红黑树相比AVL树的优点是执行插入所需要的开销相对较低，另外就是实践中发生的旋转相对较少。经验指出，平均红黑树和平均AVL树一样深，查找时间一般接近最优。

RedBlackTree类架构
1）红黑树节点RedBlackNode多一个标识颜色的字段。
2）红黑树中使用两个标记节点，一个是根，一个是nullNode，它的作用就是指示一个null引用。根标记存储关键字 $-\infty$ 和一个指向真正的根的右链。因此，相比二叉查找树的实现，查找和打印过程均需要调整（online code）。

public class RedBlackTree<AnyType extends Comparable<? super AnyType>>
{
    /**
     * Construct the tree.
     */
    public RedBlackTree()
    {
        nullNode = new RedBlackNode<AnyType>( null );
        nullNode.left = nullNode.right = nullNode;
        header      = new RedBlackNode<AnyType>( null );
        header.left = header.right = nullNode;
    }

    private static class RedBlackNode<AnyType>
    {
        // Constructors
        RedBlackNode( AnyType theElement )
        {
            this( theElement, null, null );
        }

        RedBlackNode( AnyType theElement, RedBlackNode<AnyType> lt, RedBlackNode<AnyType> rt )
        {
            element  = theElement;
            left     = lt;
            right    = rt;
            color    = RedBlackTree.BLACK;
        }

        AnyType               element;    // The data in the node
        RedBlackNode<AnyType> left;       // Left child
        RedBlackNode<AnyType> right;      // Right child
        int                   color;      // Color
    }

    private RedBlackNode<AnyType> header;
    private RedBlackNode<AnyType> 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 RedBlackNode<AnyType> current;
    private RedBlackNode<AnyType> parent;
    private RedBlackNode<AnyType> grand;
    private RedBlackNode<AnyType> great;
    
    private int compare( AnyType item, RedBlackNode<AnyType> t ) {}
    
    public void insert( AnyType item ){}
    
    public void remove( AnyType x ) {}

    public AnyType findMin( ){}
    
    public AnyType findMax( ){}

    public boolean contains( AnyType x ){}

    public void makeEmpty( )
    {
        header.right = nullNode;
    }

    public void printTree( ){}

    private void printTree( RedBlackNode<AnyType> t ){}

    public boolean isEmpty( )
    {
        return header.right == nullNode;
    }

    private void handleReorient( AnyType item ){}

    private RedBlackNode<AnyType> rotate( AnyType item, RedBlackNode<AnyType> parent ){}

    private RedBlackNode<AnyType> rotateWithLeftChild( RedBlackNode<AnyType> k2 ){}
    
    private RedBlackNode<AnyType> rotateWithRightChild( RedBlackNode<AnyType> k1 ){}
}

单旋转例程
1）item为插入的元素
2）parent为旋转子树的父节点，即图2中的G节点的父节点（曾祖节点，比如图5中的30节点），因为旋转之后的树需要附接到一个父节点上。
3）图2中第一种情形对应代码中LL情形，第二种情形对应代码中LR情形，只不过需要再用一次LL单旋转才能完成。
4）之字形旋转的实现，连续两次运用此例程即可。

    /**
     * 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<AnyType> rotate( AnyType item, RedBlackNode<AnyType> 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
    }

    private RedBlackNode<AnyType> rotateWithLeftChild( RedBlackNode<AnyType> k2 )
    {
        RedBlackNode<AnyType> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        return k1;
    }

    private RedBlackNode<AnyType> rotateWithRightChild( RedBlackNode<AnyType> k1 )
    {
        RedBlackNode<AnyType> k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        return k2;
    }

     private int compare( AnyType item, RedBlackNode<AnyType> t )
    {
        if( t == header )
            return 1;
        else
            return item.compareTo( t.element );    
    }

插入例程和handleReorient例程
1）handlerReorient例程负责旋转和着色，当我们遇到带有两个红色儿子的节点时被调用，在我们插入一片树叶时也被调用。
2）当沿树向下进行的时候，insert必须记录父亲、祖父和曾祖。由于这些量需要由handlerReorient共享，所以让他们是类成员。
3）注意，在一次旋转之后，存储在祖父和曾祖节点中的值将不再正确，不过，在下一次需要他们的时候肯定已经被修复了。

    /**
     * Insert into the tree.
     * @param item the item to insert.
     */
    public void insert( AnyType 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 )
            return;
        current = new RedBlackNode<AnyType>( item, nullNode, nullNode );

            // Attach to parent
        if( compare( item, parent ) < 0 )
            parent.left = current;
        else
            parent.right = current;
        handleReorient( item );
    }

   /**
     * 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( AnyType 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
    }

自顶向下删除
删除任何一个元素，都可以将问题归结为删除树叶。假设要删除的元素为X，做法如下：
1）若X带有两个儿子，用右子树最小节点代替X（将右子树最小节点内容放入此节点，颜色不变），然后递归删除该最小节点（此节点必然最多有一个右儿子）。
2）若X带有一个右儿子（右子树），删除方法同1）。
3）若X带有一个左儿子（左子树），用左子树最大节点代替X（将左字数最大节点内容放入此节点，颜色不变），然后递归删除该最大节点（此节点必然最多有一个左儿子）。

总之，递归的尽头，删除的必然是一个叶子节点。如果这个叶子节点为红色节点，那么直接删除即可；如果这个叶子节点为黑色节点，那么删除它将破坏红黑树的条件4。解决的办法是在自顶向下的删除期间，保证树叶是红色的。做法如下：

在下面的描述中，令X为当前节点（X属于搜索路径上的节点），T是它的兄弟，而P是它们的父亲，而我们要做的就是在沿搜索路径自顶向下的过程中，设法保证当前节点X为红色的。

a）设X有两个黑儿子
此时，根据T的儿子分为如下三种情形。