红黑树之 原理算法详解_红黑树的数学原理

        二叉查找树由于在频繁的动态更新过程中，可能会出现树的高度远大于 log2n的情况，所以就会导致各个操作效率下降，最坏的情况下就会退化为链表，变为O(n)．很明显，想要解决这个问题，有效的一种办法就是使得树的高度不要差很多，也就是平衡它．

  最先发明的平衡二叉查找树是AVL树，（它严格符合平衡二叉查找树的定义，即任何结点的左右子树高度相差不超过 1，是一种高度平衡的二叉查找树。）但是在工程中，我们经常听到的通常是红黑树，而不是AVL树．那么为什么工程中都喜欢用红黑树，而不是其他平衡二叉查找树呢？

   其实在这里，我们应该能有一些想法了．既然他严格按照规定执行，每次的插入，删除，都就会引发树的由树叶到树根的递归调整，调整的多了，自然会影响树的效率．那么红黑树又是怎样解决这个问题的呐？

        其实，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些，同时相对于平衡二叉查找树（AVL树）来说，减少从叶子结点递归往上层调整的次数，进而提高插入、删除的效率。
        所以红黑树就是这种设计思路(近似平衡)了．

1.红黑树的定义

红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树．
顾名思义，红黑树中的结点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样四个要求：

• 1.　每个结点或者是黑色，或者是红色。
• 2.　根结点是黑色。
• 3.　每个叶子结点（NIL）是黑色。 [注意：这里叶子结点，是指为(NIL)的叶子结点！]
• 4.　如果一个结点是红色的，则它的子结点必须是黑色的。（两个红色结点不能相邻）
• 5.   从一个结点到该结点的所有路径上包含相同数目的黑结点。(黑高相同）

这里的第二点要求“叶子结点都是黑色的nil结点”，主要是为了简化红黑树的代码实现而设置的．现在，我们暂时不管这一点。

红黑树的C/C++数据结构表示如下：

#define RED				1
#define BLACK 			2
 
typedef int KEY_TYPE;
 
typedef struct _rbtree_node {
	unsigned char color;
	struct _rbtree_node *right;
	struct _rbtree_node *left;
	struct _rbtree_node *parent;
	KEY_TYPE key;
	void *value;
} rbtree_node;
 
typedef struct _rbtree {
	rbtree_node *root;
	rbtree_node *nil;
} rbtree;

下面是判断红黑树的图例，你可以看下。

        其中1的黑高不一致，不是红黑树，2满足红黑树定义的要求，是红黑树，3同1，黑高不一致，不是红黑树，4根结点为红色，不是红黑树

2.为什么红黑树是近似平衡的呐？

        首先，我们知道二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是 log2n，所以如果要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近 log2n 就好了。

首先，我们来看，如果我们将红色结点从红黑树中去掉，那单纯包含黑色结点的红黑树的高度是多少呢？

红色结点删除之后，有些结点就没有父结点了，它们会直接拿这些结点的祖父结点（父结点的父结点）作为父结点。所以，之前的二叉树就变成了四叉树。

这时我们可以将有些结点拿出来组成一个完全二叉树，而完全二叉树的高度是 log2n ,很明显，我们的四叉树根本不会高于 log2n

我们现在知道只包含黑色结点的“黑树”的高度，那我们现在把红色结点加回去，高度会变成多少呢？

从上面我画的红黑树的例子和定义看，在红黑树中，红色结点不能相邻，也就是说，有一个红色结点就要至少有一个黑色结点，将它跟其他红色结点隔开．红黑树中包含最多黑色结点的路径不会超过 log2n，所以加入红色结点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n。

所以，红黑树的高度只比高度平衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。

3.实现红黑树的基本思想

和AVL树一样，在进行结点的插入和删除时，就会破坏红黑树的一些规则．在红黑树中主要破坏的是以下两点：

1.     任何相邻的结点都不能同时为红色，也就是说，红色结点是被黑色结点隔开的；
2.     每个结点，从该结点到达其可达叶子结点的所有路径，都包含相同数目的黑色结点；

很显然，我们需要也仅仅需要处理的就是如何把被破坏了的这两点规则还原回去．在还原之前，我们需要了解两个很重要的操作：左旋与右旋（围绕某个结点的右旋），
如图，其中 a，b，c 表示子树，可以为空。

          

 相对于当前子树的父结点来说，左旋相当于接入父结点的X结点向左旋转了，右旋相当于接入父结点的Y结点向右旋转了，感觉有个动画的效果是最好的了，哈哈哈～～不过也可以自己在脑中想象了啦

左旋和右旋操作对应的C/C++代码如下：

void rbtree_left_rotate(rbtree *T, rbtree_node *x) {
 
	rbtree_node *y = x->right;  // x  --> y  ,  y --> x,   right --> left,  left --> right
    rbtree_node *b = y->left;
 
 
	x->right = b; //1 1
	if (b != T->nil) { //1 2
        b->parent = x;
	}
 
	y->parent = x->parent; //1 3
	if (x->parent == T->nil) { //1 4
		T->root = y;
	} else if (x == x->parent->left) {
		x->parent->left = y;
	} else {
		x->parent->right = y;
	}
 
	y->left = x; //1 5
	x->parent = y; //1 6
}
 
 
void rbtree_right_rotate(rbtree *T, rbtree_node *y) {
 
	rbtree_node *x = y->left;
    rbtree_node *b = x->right;
 
	y->left = b;
	if (b != T->nil) {
        b->parent = y;
	}
 
	x->parent = y->parent;
	if (y->parent == T->nil) {
		T->root = x;
	} else if (y == y->parent->right) {
		y->parent->right = x;
	} else {
		y->parent->left = x;
	}
 
	x->right = y;
	y->parent = x;
}

4、红黑树的插入删除操作

4.1插入操作

        之前有提到过，二叉搜索树的字典操作的时间复杂度为O(h)，而红黑树的操作却可以在O(lgn)_内完成。为了做到这一点，我们肯定需要在插入之后进行一些结点的调整，让其满足红黑树的性质。所以在完成插入之后，还需要对树进行调整，对结点重新着色，并旋转。

        红黑树的结点插入可以分为插入过程和调整过程；