分类导航

silverlight 发布时间：2022-05-03 发布网站：大佬教程 code.js-code.com

大佬教程收集整理的这篇文章主要介绍了红黑树（Red Black Tree），大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

概述

介绍今天我们来介绍另一种平衡二叉树：红黑树（Red Black Tree），红黑树由Rudolf Bayer于1972年发明，当时被称为平衡二叉B树（symmetric binary B-trees），1978年被Leonidas J. Guibas 和 Robert Sedgewick改成一个比较摩登的名字：红黑树。红黑树和之前所讲的AVL树类似，都是在进行插入和删除操作时通过特定操作保持二

介绍

今天我们来介绍另一种平衡二叉树：红黑树（Red Black Tree），红黑树由Rudolf Bayer于1972年发明，当时被称为平衡二叉B树（symmetric binary B-trees），1978年被Leonidas J. Guibas 和 Robert Sedgewick改成一个比较摩登的名字：红黑树。

红黑树和之前所讲的AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。自从红黑树出来后，AVL树就被放到了博物馆里，据说是红黑树有更好的效率，更高的统计性能。不过在我了解了红黑树的实现原理后，并不相信这是真的，关于这一点我们会在后面进行讨论。

红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。之前我们在讲解AVL树时，已经领教过AVL树的复杂，但AVL树的复杂比起红黑树来说简直是小巫见大巫。红黑树是真正的变态级数据结构。

首先来一个Silverlight做的红黑树的动画，它有助于帮你理解什么是红黑树。这里需要注意，必须安装@H_696_71@Silverlight 2.0 RTW 才能正常运行游戏，下载地址：

@H_696_71@http://www.microsoft.com/silverlight/resources/install.aspx?v=2.0

使用注意事项：

l 结点只接收整数，如果在添加和删除操作中输入非法字串，则会随机添加或删除一个0~99之间的整数。

l 可以不在编辑框中输入数字，直接单击添加和删除按钮进行添加和删除操作。

l 可以拖动拖动条控制动画速度。

红黑树的平衡

红黑树首先是一棵二叉查找树，它每个结点都被标上了颜色（红色或黑色），红黑树满足以下5个性质：

1、 每个结点的颜色只能是红色或黑色。

2、 根结点是黑色的。

3、 每个叶子结点都带有两个空的黑色结点（被称为黑哨兵），如果一个结点n的只有一个左孩子，那么n的右孩子是一个黑哨兵；如果结点n只有一个右孩子，那么n的左孩子是一个黑哨兵。

4、 如果一个结点是红的，则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

5、 对于每个结点来说，从该结点到其子孙叶结点的所有路径上包含相同数目的黑结点。

红黑树的这5个性质中，第3点是比较难理解的，但它却非常有必要。我们看图1中的左边这张图，如果不使用黑哨兵，它完全满足红黑树性质，结点50到两个叶结点8和叶结点82路径上的黑色结点数都为2个。但如果加入黑哨兵后（如图1右图中的小黑圆点），叶结点的个数变为8个黑哨兵，根结点50到这8个叶结点路径上的黑高度就不一样了，所以它并不是一棵红黑树。

要看真正的红黑树请在以上动画中添加几个结点，看看是否满足以上性质。

红黑树的旋转操作

红黑树的旋转操作和AVL树一样，分为LL、RR、LR、RL四种旋转类型，差别在于旋转完成后改变的是结点的颜色，而不是平衡因子。旋转动画演示请参考AVL这篇文章中的Flash动画：

http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html

红黑树上结点的插入

在讨论红黑树的插入操作之前必须要明白，任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解，因为插入黑点会增加某条路径上黑结点的数目，从而导致整棵树黑高度的不平衡。但如果新结点父结点为红色时（如图2所示），将会违返红黑树性质：一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。

@H_632_262@

为了清楚地表示插入操作以下在结点中使用“新”字表示一个新插入的结点；使用“父”字表示新插入点的父结点；使用“叔”字表示“父”结点的兄弟结点；使用“祖”字表示“父”结点的父结点。插入操作分为以下几种情况：

1、黑父

如图3所示，如果新点的父结点为黑色结点，那么插入一个红点将不会影响红黑树的平衡，此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见，从而使红黑树需要旋转的几率相对AVL树来说会少一些。

2．红父

如果新点的父结点为红色，这时就需要进行一系列操作以保证整棵树红黑性质。如图3所示，由于父结点为红色，此时可以判定，祖父结点必定为黑色。这时需要根据叔父结点的颜色来决定做什么样的操作。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作，而每次进行不平衡判断的起始点（我们可将其视为新点）都不一样。所以我们在此使用一个蓝色箭头指向这个起始点，并称之为判定点。

@H_772_336@

2.1 红叔

当叔父结点为红色时，如图4所示，无需进行旋转操作，只要将父和叔结点变为黑色，将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色，从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上进行平衡操作。

需要注意，无论“父”在“叔”的左边还是右边，无论“新”是“父”的左孩子还是右孩子，它们的操作都完全一样。

2.2 黑叔

当叔父结点为黑色时，需要进行旋转，以下图示了所有的旋转可能

情形1：

情形2：

（2010-3-25 注意：经网友@H_97_419@BourneHan的指正，现已确定3.2.1和3.2.2中的新结点应为黑色，而不是现在的不确定颜色。基于以下2点原因，我并不打算在代码及博文中更改这个错误：

@H_97_419@ 1、这个错误对代码及动画的正确性没有影响。

@H_97_419@ 2、之前的代码及动画经过了大量测试，需要花很多时间，更改代码意味着重新测试，现在的确抽不出这么多时间来做这项工作。

@H_97_419@这里只能对各位读者说声对不起了，最快的补救方法就是在此点出错误，让读者明了。)

3.2.3 黑兄红侄

黑兄红侄有以下四种情形，下面分别进行图示：

情形1：

情形2：

情形3：

情形4：

由以上图例所示，看完以上四张图的兄弟有可能会有一个疑问，如果情形1和情形2中的两个侄子结点都为红色时，是该进行LL旋转还是进行LR旋转呢？答案是进行LL旋转。情形3和情形4则是优先进行RR旋转的判定。

红黑树的代码实现

本以为红黑树的代码非常容易，因为System.Collections.Generic.sortedDictionary类就是使用红黑树实现的，把代码的算法部分抠出来就搞定了。但看了SortedDictionary源码后有些失望，C#中真正实现红黑树的是TreeSet类，SortedDictionary只是在TreeSet的基础上进一步抽象，加上了Key/value泛型对。TreeSet使用了一种新的红黑树算法，它在搜索插入点和删除点时预先进行旋转和染色操作，从而避免插入和删除后的回溯。这种算法看上去很美，但仔细想想，如果插入的是一个已经存在的结点，删除的结点并不存在，那这些预平衡处理不是白做了吗？更可怕的是如果在一条路径上间隔进行一次插入和一次删除，而这些操作没有命中目标，那么大家就会看到结点的颜色变来变去，这些都是无用功。来看看在寻找插入和删除点的路径上TreeSet每前进一步都要做些什么：给四个变量赋值；判断每个结点的两个孩子结点的颜色。这种算法在《java数据结构和算法》这本书中有详细讲述，不过只讲解了插入算法。另外国内也专门有一篇论文描述这个算法，他的测试结果是这种算法优于其他算法，估计测试时没有不命中目标的情况发生。总之我并不相信这是一个好的算法。

为了证实我的想法，我不得不自己实现红黑树，实现思路跟AVL树很类似，也是使用一个数组保存访问路径以进行回溯，当然，考虑到红黑树不严格的平衡，数组的长度设为64，这并不会给性能带来什么影响。过程很艰辛，需要做大量测试。很不幸，写完后继续做红黑树的Silverlight动画时不小心把原来的代码给覆盖掉了，结点删除部分的代码丢失。当时几乎崩溃，不过重写并没有我想象的那么困难，很快完成，感觉思路清晰了很多，实现比原来也有了改进，感谢上帝！

下面把代码贴出来，如果理解了上面所讲内容是很容易读懂这些代码的。

using System;
namespace PaintBST
{
     public class rBTree : IBinaryTree // 实现画树接口
    {     // 成员变量
         private Node _head; // 头指针
         private Node[] path = new Node[ 32 ]; // 记录访问路径上的结点
         private int p; // 表示当前访问到的结点在_path上的索引
        INode IBinaryTree.Head // 显式接口实现
         {
             get { return (INodE)_head; }
       }
         public bool Add( int value) // 添加一个元素
          {   // 如果是空树，则新结点成为二叉排序树的根
             if (_head == null )
            {
                _head = new Node(value);
                _head.IsRed = false ;
                 return true ;
            }
            p = 0 ;
             // parent为上一次访问的结点，current为当前访问结点
            Node parent = null , current = _head;
             while (current != null )
            {
                path[p ++ ] = current; // 将路径上的结点插入数组
                  // 如果插入值已存在，则插入失败
                  if (current.Data == value)
                {
                     return false ;
                }
                parent = current;
                 // 当插入值小于当前结点，则继续访问左子树，否则访问右子树
                 current = (value < parent.Data) ? parent.Left : parent.Right;
            }
            current = new Node(value); // 创建新结点
               current.IsRed = true ;
             if (value < parent.Data) // 如果插入值小于双亲结点的值
               {
                parent.Left = current; // 成为左孩子
               }
             else // 如果插入值大于双亲结点的值
               {
                parent.Right = current; // 成为右孩子
               }
             if ( ! parent.IsRed)
            {
                 return true ;
            }
            path[p] = current;
             // 回溯并旋转
             while ((p -= 2 ) >= 0 ) // 现在p指向插入点的祖父结点
             {
                Node grandParent = path[p];
                parent = path[p + 1 ];
                 if ( ! parent.IsRed)
                {
                     break ;
                }
                Node uncle = grandParent.Left == parent ? grandParent.Right : grandParent.Left;
                current = path[p + 2 ];
                 if (IsRed(unclE)) // 叔父存在并且为红色的情况
                   {
                    parent.IsRed = false ;
                    uncle.IsRed = false ;
                     if (p > 0 ) // 如果祖父不是根结点，则将其染成红色
                        {
                        grandParent.IsRed = true ;
                    }
                }
                 else // 叔父不存在或为黑的情况需要旋转
                   {
                    Node newRoot;
                     if (grandParent.Left == parent) // 如果当前结点及父结点同为左孩子或右孩子
                        {
                        newRoot = (parent.Left == current) ? LL(grandParent) : LR(grandParent);
                    }
                     else
                    {
                        newRoot = (parent.Right == current) ? rR(grandParent) : rL(grandParent);
                    }
                    grandParent.IsRed = true ; // 祖父染成红色
                     newRoot.IsRed = false ; // 新根染成黑色
                      // 将新根同曾祖父连接
                     replaceChildOfNodeOrRoot((p > 0 ) ? path[p - 1 ] : null , grandParent, newRoot);
                     return true ; // 旋转后不需要继续回溯，添加成功，直接退出
                   }
            }
             return true ;
        }
         // 旋转根旋转后换新根
         private void replaceChildOfNodeOrRoot(Node parent, Node child, Node newChild)
        {
             if (parent != null )
            {
                 if (parent.Left == child)
                {
                    parent.Left = newChild;
                }
                 else
                {
                    parent.Right = newChild;
                }
            }
             else
            {
                _head = newChild;
            }
        }
         private static bool IsBlack(Node nodE)
        {
             return ((node != null ) && ! node.IsRed);
        }

         private static bool IsNullOrBlack(Node nodE)
        {
             if (node != null )
            {
                 return ! node.IsRed;
            }
             return true ;
        }

         private static bool IsRed(Node nodE)
        {
             return ((node != null ) && node.IsRed);
        }
         // 删除指定值
         public bool remove( int value)
        {
            p = - 1 ;
             // parent表示双亲结点，node表示当前结点
            Node node = _head;
             // 寻找指定值所在的结点
             while (node != null )
            {
                path[ ++ p] = node;
                 // 如果找到，则调用RemoveNode方法删除结点
                  if (value == node.Data)
                {
                    removeNode(nodE); // 现在p指向被删除结点
                      return true ; // 返回true表示删除成功
                 }
                 if (value < node.Data)
                {    // 如果删除值小于当前结点，则向左子树继续寻找
                     node = node.Left;
                }
                 else
                {    // 如果删除值大于当前结点，则向右子树继续寻找
                     node = node.Right;
                }
            }
             return false ; // 返回false表示删除失败
        }
         // 删除指定结点
         private void removeNode(Node nodE)
        {
            Node tmp = null ; // tmp最终指向实际被删除的结点
             // 当被删除结点存在左右子树时
             if (node.Left != null && node.Right != null )
            {
                tmp = node.Left; // 获取左子树
                 path[ ++ p] = tmp;
                 while (tmp.Right != null ) // 获取node的中序遍历前驱结点，并存放于tmp中
                 {    // 找到左子树中的最右下结点
                     tmp = tmp.Right;
                    path[ ++ p] = tmp;
              }
                 // 用中序遍历前驱结点的值代替被删除结点的值
                 node.Data = tmp.Data;
            }
             else
            {
                tmp = node;
            }
             // 当只有左子树或右子树或为叶子结点时
             // 首先找到惟一的孩子结点
            Node newTmp = tmp.Left;
             if (newTmp == null ) // 如果只有右孩子或没孩子
               {
                newTmp = tmp.Right;
            }
             if (p > 0 )
            {
                Node parent = path[p - 1 ];
                 if (parent.Left == tmp)
                {    // 如果被删结点是左孩子
                     parent.Left = newTmp;
                }
                 else
                {    // 如果被删结点是右孩子
                     parent.Right = newTmp;
                }
                 if ( ! tmp.IsRed && IsRed(newTmp))
                {
                    newTmp.IsRed = false ;
                     return ;
                }
            }
             else    // 当删除的是根结点时
               {
                _head = newTmp;
                 if (_head != null )
                {
                    _head.IsRed = false ;
                }
                 return ;
            }
            path[p] = newTmp;

             // 如果被删除的是红色结点，则它必定是叶子结点，删除成功，返回
             if (IsRed(tmp))
            {
                 return ;
            }
             // 删除完后进行旋转，现在p指向实际被删除的位置,这个位置可能为空,tmp指向被删除的旧点，
             while (p > 0 )
            {    // 剩下的是双黑的情况
                  // 首先找到兄弟结点
                 Node current = path[p];
                Node parent = path[p - 1 ];
                 bool currentIsLeft = (parent.Left == current);
                Node sibling = currentIsLeft ? parent.Right : parent.Left;
                 // 红兄的情况，需要LL旋转或RR旋转
                  if (IsRed(sibling))
                {
                    Node newRoot;
                     if (currentIsLeft)
                    {
                        newRoot = rR(parent);
                    }
                     else
                    {
                        newRoot = LL(parent);
                    }
                    replaceChildOfNodeOrRoot(p > 1 ? path[p - 2 ] : null , parent, newRoot);
                    sibling.IsRed = false ;
                    parent.IsRed = true ;
                     // 回溯点降低
                     path[p - 1 ] = newRoot;
                    path[p] = parent;
                    path[ ++ p] = current;
                }
                 else // 黑兄的情况
                   {
                     // 黑兄二黑侄
                      if (IsNullOrBlack(sibling.Left) && IsNullOrBlack(sibling.Right))
                  {   // 红父的情况
                          if (parent.IsRed)
                     {
                            parent.IsRed = false ;
                            sibling.IsRed = true ;
                             if (current != null )
                            {
                                current.IsRed = false ;
                            }
                             break ; // 删除成功
                         }
                         else // 黑父的情况
                         {
                            parent.IsRed = IsRed(current);
                             if (current != null )
                            {
                                current.IsRed = false ;
                            }
                            sibling.IsRed = true ;
                            p -- ; // 需要继续回溯
                         }
                  }
                   else // 黑兄红侄
                     {
                        Node newRoot;
                         if (currentIsLeft) // 兄弟在右边
                             {
                             if (IsRed(sibling.Right)) // 红侄在右边
                                 {   // RR型旋转
                                 newRoot = rR(parent);
                                sibling.Right.IsRed = false ;
                            }
                             else
                            {   // RL型旋转
                                 newRoot = rL(parent);
                            }
                        }
                         else // 兄弟在左边
                            {
                             if (IsRed(sibling.Left))
                            {   // LL型旋转
                                 newRoot = LL(parent);
                                sibling.Left.IsRed = false ;
                            }
                             else
                            {   // LR型旋转
                                 newRoot = LR(parent);
                            }
                        }
                         if (current != null )
                        {
                            current.IsRed = false ;
                        }
                        newRoot.IsRed = parent.IsRed;
                        parent.IsRed = false ;
                        replaceChildOfNodeOrRoot(p > 1 ? path[p - 2 ] : null , newRoot);
                         break ; // 不需要回溯，删除成功
                     }
                }
            }
        }
         // root为旋转根，rootPrev为旋转根双亲结点
         private Node LL(Node root) // LL型旋转，返回旋转后的新子树根
         {
            Node left = root.Left;
            root.Left = left.Right;
            left.Right = root;
             return left;
        }
         private Node LR(Node root) // LR型旋转，返回旋转后的新子树根
          {
            Node left = root.Left;
            Node right = left.Right;
            root.Left = right.Right;
            right.Right = root;
            left.Right = right.Left;
            right.Left = left;
             return right;
        }
         private Node rR(Node root) // RR型旋转，返回旋转后的新子树根
          {
            Node right = root.Right;
            root.Right = right.Left;
            right.Left = root;
             return right;
        }
         private Node rL(Node root) // RL型旋转，返回旋转后的新子树根
          {
            Node right = root.Right;
            Node left = right.Left;
            root.Right = left.Left;
            left.Left = root;
            right.Left = left.Right;
            left.Right = right;
             return left;
        }
    }
}

完成红黑树后，做了一个比较粗糙的测试程序，对我自己实现的红黑树RBTree，C#类库中的红黑树TreeSet和我自己实现的AVL树AVLTree进行了简单的测试，为了公平起见，我把TreeSet改成了整型版，这样大家都站在了同一起跑线上。考虑到垃圾回收，这样的测试并不是很精确、科学，但也能说明一些问题。以后我会专门写程序对各种常见的查找数据结构进行测试

@H_315_2944@

测试项目

RBTree

TreeSet

AVLTree

200000个整数顺序插入(全部命中)

0.4375

0.4844

0.3437

200000个整数顺序插入后顺序删除(全部命中，只对删除部分计时)

0.25

0.5

0.20

200000个整数随机插入(全部命中)

0.4375

0.5469

0.5

200000个整数随机插入后顺序删除(全部命中，只对删除部分计时)

0.5

0.7343

0.4219

200000个整数顺序插入(一半命中)

0.297

0.344

0.234

100000个整数随机插入后顺序删除(一半命中，只对删除部分计时)

0.094

0.203

0.109

后记

测试结果基本证实了我的想法，惟一意外的是AVL树有两个项目输给了RBTree。在理论上，RBTree在某些方面的确是比AVL树更为优秀，但从程序员的角度来说，红黑树的实现需要调用大量方法，比如结点颜色的判断，这会抵消红黑树的性能优势。国外网站也有针对红黑树和AVL树的测试，结果基本上是AVL树胜出。

红黑树的动画还有一些bug，整体效果也不尽如人意，我也懒得再改了，写它比写红黑树困难些。写它主要是为了学习Silverlight，这也算是第一个Silverlight动画作品，东西弄懂了就不想再动了。打算将来更深入地了解Silverlight后再全面修改这个动画。

情形3：