红黑树系列之一：红黑树的概述_提出红黑树的目的

一、红黑树（RBT）的定义

1.红黑树的引入目的

2.红黑树的定义

   红黑树和我们以前学过的AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。不过自从红黑树出来后，AVL树就被放到了博物馆里，据说是红黑树有更好的效率，更高的统计性能。这一点在我们了解了红黑树的实现原理后，就会有更加深切的体会。
     红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。学过数据结构的人应该都已经领教过AVL树的复杂，但AVL树的复杂比起红黑树来说简直是小巫见大巫，红黑树才是真正的变态级数据结构。
     由于STL中的关联式容器默认的底层实现都是红黑树，因此红黑树对于后续学习STL源码还是很重要的，有必要掌握红黑树的实现原理和源码实现。
     红黑树是AVL树的变种，红黑树通过一些着色法则确保没有一条路径会比其它路径长出两倍，因而达到接近平衡的目的。所谓红黑树，不仅是一个二叉搜索树，而且必须满足一下规则：
     1、每个节点不是红色就是黑色。
     2、根节点为黑色。
     3、如果节点为红色，其子节点必须为黑色。
     4、任意一个节点到到NULL（树尾端）的任何路径，所含之黑色节点数必须相同。
上面的这些约束保证了这个树大致上是平衡的，这也决定了红黑树的插入、删除、查询等操作是比较快速的。 根据规则4，新增节点必须为红色；根据规则3，新增节点之父节点必须为黑色。当新增节点根据二叉搜索树的规则到达其插入点时，却未能符合上述条件时，就必须调整颜色并旋转树形，如下图：

假设我们为上图分别插入节点3、8、35、75，根据二叉搜索树的规则，插入这四个节点后，我们会发现它们都破坏了红黑树的规则，因此我们必须调整树形，也就是旋转树形并改变节点的颜色。

3.红黑树相关定理

（1）. 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

      根据上面的性质5我们知道上图的红黑树每条路径上都是3个黑结点。因此最短路径长度为2(没有红结点的路径)。再根据性质4(两个红结点不能相连)和性质1，2(叶子和根必须是黑结点)。那么我们可以得出：一条具有3个黑结点的路径上最多只能有2个红结点(红黑间隔存在)。也就是说黑深度为2（根结点也是黑色）的红黑树最长路径为4，最短路径为2。从这一点我们可以看出红黑树是 大致平衡的。 (当然比平衡二叉树要差一些，AVL的平衡因子最多为1)

 

（2）. 红黑树的树高(h)不大于两倍的红黑树的黑深度(bd)，即h<=2bd

      根据定理1，我们不难说明这一点。bd是红黑树的最短路径长度。而可能的最长路径长度(树高的最大值)就是红黑相间的路径，等于2bd。因此h<=2bd。

 

（3）. 一棵拥有n个内部结点(不包括叶子结点)的红黑树的树高h<=2log(n+1)

      下面我们首先证明一颗有n个内部结点的红黑树满足n>=2^bd-1。这可以用数学归纳法证明，施归纳于树高h。当h=0时，这相当于是一个叶结点，黑高度bd为0，而内部结点数量n为0，此时0>=2^0-1成立。假设树高h<=t时，n>=2^bd-1成立，我们记一颗树高 为t+1的红黑树的根结点的左子树的内部结点数量为nl，右子树的内部结点数量为nr，记这两颗子树的黑高度为bd'（注意这两颗子树的黑高度必然一 样），显然这两颗子树的树高<=t，于是有nl>=2^bd'-1以及nr>=2^bd'-1，将这两个不等式相加有nl+nr>=2^(bd'+1)-2，将该不等式左右加1，得到n>=2^(bd'+1)-1，很显然bd'+1>=bd，于是前面的不等式可以 变为n>=2^bd-1，这样就证明了一颗有n个内部结点的红黑树满足n>=2^bd-1。

        在根据定理2，h<=2bd。即n>=2^(h/2)-1，那么h<=2log(n+1)

        从这里我们能够看出，红黑树的查找长度最多不超过2log(n+1)，因此其查找时间复杂度也是O(log N)级别的。

二、红黑树的节点设计

   RB-TREE有红黑二色，并且拥有左右子节点，因此，很容易勾勒出其结构风貌。由于在RB-TREE各种操作往往需要用到父节点，所以在数据结构中增加一个parent指针。下面是定义RBT的数据结构：

//定义红黑树的数据结构
typedef enum colorType{Red,Black} colorType;
typedef int elementType;
typedef struct RedBlackNode
{
	struct RedBlackNode *parent;  //父节点
	struct RedBlackNode *Left;   //指向左节点
	struct RedBlackNode *Right;  //指向右节点
	colorType color;            //j节点颜色，非黑即红
	elementType element;       //节点存放的数据
	
}RBTree,*PRBTree;
 

下面是RB-TREE的节点图标，其中element=10；

构建一颗空树：

// 红黑树，包含一个指向根节点的指针    
typedef struct RBTree  
{    
    struct RedBlackNode* root;  
}*RB_Tree;  
  
// 红黑树的NIL节点    
static struct RedBlackNode NIL = {0, 0, 0, 0, BLACK};   
  
#define PNIL (&NIL)   // NIL节点地址   
  
void Init_RBTree(RB_Tree pTree) // 初始化一棵红黑树    
{    
    pTree->root = PNIL;    
} 

三、红黑树的性能比较：

  1、插入时，AVL和RBT都最多需要2次旋转；删除时，AVL最多需要lgN次旋转，而RBT最多需要3次旋转；

  2、RBT旋转平衡时，需要变色操作，在O(lgN)数量级上，但操作简单、速度快；

  3、二者插入删除的代价主要消耗在查找操作上，都与O(lgN)成正比；

  研究表明：RBT的总体统计性能要好于平衡二叉树。

 四、红黑树的应用

    红黑树现在应用很广泛，任何键值对应，需要随机存储和键有序的情况都可以用；   

C++STL中的set, multiset, map, multimap等

内存中比如缓存的(区块-数据)，编号对应内容，引索号对应数据项

在Linux内核中，对虚拟内存的管理

==