红黑二叉查找树

偏执的太偏执、 2022-09-25 06:17 357阅读 0赞

//红黑二叉查找树  
      
    //红黑二叉查找树是一种平衡二叉树,是基于2-3查找树的基础上演变的  
    //这里不对2-3查找树的算法进行描述,感兴趣的朋友可以自行了解一下  
    //2-3查找树的实现原理.  
    //  
    //在2-3查找树算法中,难点就是3-Node类型(含有2个key,3个子节点的节点类型)  
    //的节点数据结构处理,那么在红黑二叉查找树中这种3-Node类型节点演变为如  
    //下表示方式.非常巧妙的在原普通二叉数结点数据结构中增加了一个颜色的成  
    //员变量,就使得红黑二叉查找树可以替换为2-3查找树.当一个节点的左子节点  
    //的颜色为红色时，该节点即为2-3查找树中的3-Node类型节点，此时可以将红  
    //色的子节点理解为和父节点是平行的，一体的，比如当前示例中将Node1与  
    //Node2合并成一个节点，该节点相当于2-3查找树中的3-Node类型节点，即含有  
    //2个key，3个子节点。  
    //  
    //  ** 相当于2-3查找树中的3-Node类型节点:  
    //                Node1(Black)  
    //              --------------  
    //             /              \  
    //        Node2(Red)      NULL(Black)  
    //       -----------  
    //      /           \  
    //  NULL(Black)  NULL(Black)  
    //    
    //  ** 相当于2-3查找树中的2-Node类型节点:  
    //                Node1(Black)  
    //              --------------  
    //             /              \  
    //        Node2(Black)      NULL(Black)  
    //       -----------  
    //      /           \  
    //  NULL(Black)  NULL(Black)  
    //  
    //红黑二叉查找树的定义如下：  
    //1 根节点必须为黑色  
    //2 红链接均为左链接  
    //3 没有任何一个结点同时和两条红链接相连  
    //4 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量  
    //  相同。  
    //备注： 空节点的颜色为黑色。  
      
    private const bool RED = true;
    private const bool BLACK = false;
    
    private Node root;
    
    class Node
    {
        public Node Left { get; set; }
        public Node Right { get; set; }
        public TKey Key { get; set; }
        public TValue Value { get; set; }
        public int Number { get; set; }
        public bool Color { get; set; }
    
        public Node(TKey key, TValue value,int number, bool color)
        {
            this.Key = key;
            this.Value = value;
            this.Number = number;
            this.Color = color;
        }
    }
    
    private bool IsRed(Node node)
    {
        if (node == null) return false;
        return node.Color == RED;
    }
      
    //树的左旋：  
    //1 首先把该节点的右子节点进行提升  
    //2 之后把该节点进行下降(由于右子节点提升，该节点下降，所以此刻该节点的等级  
    //  仅仅和新位置的右子点的子节点平行，即当前右子节点已经可以做为被旋转节点  
    //  的父节点了)  
    //3 将该节点的右链接指向原右子节点的左树  
    //4 将原右子节点的左链接指向该节点  
    // （3、4步之所以这样操作，主要是为了满足二叉树的特性，每个节点最多有两个子  
    // 节点，同时左子节点一定小于该节点，右子节点一定大于该节点。）  
    //5 可以看到当前仅被旋转节点和该节点的右子节点做了变化，所以仅对这两个节点  
    //  的相关信息进行更新。  
    //  
    //示例：对5节点进行左旋  
    //  
    //     旋转前  
    //       5  
    //     /   \  
    //    3     7  
    //   / \   / \  
    //  2   4 6   8  
    //  
    //     旋转后  
    //        7  
    //       / \  
    //      5   8  
    //     / \  
    //    3   6  
    //   / \  
    //  2   4   
    //  
    //左旋转
    private Node RotateLeft(Node h)
    {
        Node x = h.Right;
        //将x的左节点复制给h右节点
        h.Right = x.Left;
        //将h复制给x右节点
        x.Left = h;
        x.Color = h.Color;
        h.Color = RED;
        return x;
    }
      
    //树的右旋：  
    //同左旋原理相同，这里仅给出示例  
    //  
    //示例：对5节点进行右旋  
    //  
    //     旋转前  
    //       5  
    //     /   \  
    //    3     7  
    //   / \   / \  
    //  2   4 6   8  
    //  
    //     旋转后  
    //        3  
    //       / \  
    //      2   5  
    //         / \  
    //        4   7  
    //           / \  
    //          6   8   
    //  
    //右旋转
    private Node RotateRight(Node h)
    {
        Node x = h.Left;
        h.Left = x.Right;
        x.Right = h;
    
        x.Color = h.Color;
        h.Color = RED;
        return x;
    } 
      
    void flipColors(Node h){
    	h.color = RED;
    	h.left.color = BLACK;
    	h.right.color = BLACK;
    }  
      
    //红黑二叉查找树的插入  
    //这里同2-3查找树算法类似，主要考虑5种情况：  
    //1 插入到2-Node类型节点的左侧  
    //2 插入到2-Node类型节点的右侧  
    //3 插入到3-Node类型节点的左侧  
    //4 插入到3-Node类型节点的中侧  
    //5 插入到3-Node类型节点的右侧  
    //  
    // * 插入到2-Node类型节点的左侧  
    //   如下示例所示，将2插入到4节点的左侧，新建立的节点都是红色,此时  
    //   满足红黑树的特性，所以后继不需要在做其它处理。  
    //  
    // 插入前：  
    //    4(B)  
    //    /  \  
    //  NULL  6(B)  
    //  
    // 插入后：  
    //    4(B)  
    //    /  \  
    //  2(R) 6(B)  
    //  
    // * 插入到2-Node类型节点的右侧  
    // 如下示例所示，将6插入到4节点的右侧，新建立的节点是红色，此时  
    // 违背了红黑树的特性，不能出现红色的右链接，为了恢复红黑树的特性，  
    // 这里需要再将4节点进行左旋转，可以参见树左旋的介绍，这样红黑  
    // 树的特性又满足了。  
    //  
    // 插入前：  
    //    4(B)  
    //    /  \  
    //  5(B)  NULL  
    //  
    // 插入后：  
    //    4(B)  
    //    /  \  
    //  5(B) 6(R)  
    //  
    // * 插入到3-Node类型节点的右侧  
    // 先介绍这种情况，因为这种情况在3-Node类型节点的几种插入算法中最简单。  
    // 如下示例所示，将8插入到7节点的右侧，新建立的节点为红色，由于这里是  
    // 将新节点插入到3-Node类型节点中，所以不能依照2-Node类型算法中的插入  
    // 右侧进行分析，3-Node类型节点的插入有自己单独的算法，在插入3-Node类  
    // 型节点右侧的情况下，将7的左、右两个子节点5和8的颜色全部变成黑色，之  
    // 后7节点自身的颜色变成红色，这时候关键就看7这个节点，如果7节点也是一棵  
    // 子树，则由于7节点颜色发生了变化，所以需要检测7节点上面的父节点情况，  
    // 一般情况下父节点会有3种情况  
    // a 如果父节点不存在，则7就是最根节点，则根节点7为了满足红黑树的特性，  
    //   必须变成黑色  
    // b 如果父节点为2-Node类型节点，则按照上面2-Node的两种方法进行调用父  
    //   节点也当前子树根节点的关系即可  
    // c 如果父节点为3-Node类型节点，则同当前3-Node类型节点的方法相同，调  
    //   整父节点与当前子树根节点的关系，采用这种循环处理父节点的方式，  
    //   直到上升调整到父节点为空或为2-Node类型则停止。  
    // (此时的算法已经十分类似向2-3查找树算法中，向3-Node类型节点插入相似)  
    //  
    // 插入前：  
    //      7(B)  
    //      /  \  
    //    5(R)  NULL  
    //    /  \  
    //  3(B) 6(B)  
    //  
    // 插入后：  
    //       7(B)  
    //      /   \  
    //    5(R)  8(R)  
    //    /  \  
    //  3(B) 6(B)  
    //  
    // * 插入到3-Node类型节点的左侧  
    // 如示例所示，将节点3插入到3-Node类型节点左侧，新建的节点是红色，  
    // 插入后，出现7的左节点为红色，同时左节点的左节点也是红色，此时不  
    // 能满足红黑树的特性，之后将节点7进行右旋，仔细查看右旋后的情况，  
    // 和之前"插入到3-Node类型节点的右侧"后的情况竟然相同了，此时参数  
    // 上述方法，将两个子节点变成黑色，当前子树的根节点变成红色即可。  
    //  
    // 插入前：  
    //       7(B)  
    //      /   \  
    //    5(R)  8(B)  
    //    /  \  
    //       6(B)  
    //  
    // 插入后：  
    //       7(B)  
    //      /   \  
    //    5(R)  8(B)  
    //    /  \  
    //  3(R) 6(B)  
    //  
    // 右旋后：  
    //     5(B)  
    //    /    \  
    //  3(R)   7(R)  
    //         /  \  
    //       6(B) 8(B)  
    //  
    // * 插入到3-Node类型节点的中侧  
    // 最后一种插入情况了，放最后是因为这种情况最麻烦  
    // 如示例所示,将6插入到3-Node类型节点的中侧，插入后，新节点为红色，  
    // 不满足红黑树中右链接不能出现红色的特性，此时将5节点进行左旋转，旋转  
    // 后仔细观察，其中这时候出现左节点、以及左节点的左节点为红色，这个现象  
    // 同之前的"插入到3-Node类型节点的左侧"的相同了，所以采用那种情况的解决  
    // 方法，将当前节点7再进行一次右旋转，这时候又出现了左、右子节点都为红  
    // 色的现象，采用之前的方法，将两个子节点变成黑色，子树的根节点变成红  
    // 色。  
    //  
    // 插入前：  
    //       7(B)  
    //      /   \  
    //    5(R)  8(B)  
    //    /  \  
    //  3(B)  
    //  
    // 插入后：  
    //       7(B)  
    //      /   \  
    //    5(R)  8(B)  
    //    /  \  
    //  3(B) 6(R)  
    //  
    // 对5节点进行左旋后：  
    //        7(B)  
    //       /   \  
    //     6(R)  8(B)  
    //     /  
    //   5(R)  
    //    /  
    //  3(B)  
    //  
    // 对7节点进行右旋后：  
    //        6(B)  
    //       /   \  
    //     5(R)  7(R)  
    //     /       \  
    //   3(B)     8(B)  
    //  
    public override void Put(TKey key, TValue value)
    {
        root = Put(root, key, value);
        root.Color = BLACK;
    }
    
    private Node Put(Node h, TKey key, TValue value)
    {
        if (h == null) return new Node(key, value, 1, RED);
        int cmp = key.CompareTo(h.Key);
        if (cmp < 0) h.Left = Put(h.Left, key, value);
        else if (cmp > 0) h.Right = Put(h.Right, key, value);
        else h.Value = value;
    
        //平衡化操作
        if (IsRed(h.Right) && !IsRed(h.Left)) h = RotateLeft(h);
        if (IsRed(h.Right) && IsRed(h.Left.Left)) h = RotateRight(h);
        if (IsRed(h.Left) && IsRed(h.Right)) h = FlipColor(h);
    
        h.Number = Size(h.Left) + Size(h.Right) + 1;
        return h;
    }
    
    private int Size(Node node)
    {
        if (node == null) return 0;
        return node.Number;
    }  
      
      
    //查找  
    //这里同普通二叉树查找算法相同，不再进行描述  
    //查找获取指定的值
    public override TValue Get(TKey key)
    {
        return GetValue(root, key);
    }
    
    private TValue GetValue(Node node, TKey key)
    {
        if (node == null) return default(TValue);
        int cmp = key.CompareTo(node.Key);
        if (cmp == 0) return node.Value;
        else if (cmp > 0) return GetValue(node.Right, key);
        else return GetValue(node.Left, key);
    }

如果上面概念不是很清楚，再上几张图片：

左旋：

[![rotate left in red black tree][]][rotate left in red black tree 1]

右旋：

[![rotate right the red black tree][]][rotate right the red black tree 1]

flipColors：

![20160815020625340][]

参考：

http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html

http://blog.csdn.net/liujianfeng1984/article/details/47378715

[rotate left in red black tree]: /images/20220718/140d88e165714dbd90b3caf92fff48f0.png
[rotate left in red black tree 1]: http://images.cnitblog.com/blog/94031/201403/270024492492764.gif
[rotate right the red black tree]: /images/20220718/193f8ebc043c46e4be2af879e0dc592f.png
[rotate right the red black tree 1]: http://images.cnitblog.com/blog/94031/201403/270025006402285.gif
[20160815020625340]: /images/20220718/4f134dbab39046d0b84247241cd0171e.png