算法系列笔记4(红黑树)

       随机构建的二叉查找树的高度期望值为O(lgn),并不代表所有的二叉查找树的高度都为O(lgn)。但是对于有些二叉查找树的变形来说，动态集合各基本操作的性能却总是很好的，如红黑树、B树、平衡二叉树(AVL树)、跳跃表(确切的说不是树，或多或少有树的结构)、treaps(树堆)等。这里我们讲解红黑树。

       平衡的意思就是完成动态数据集的操作(minimum、maximum、search、predecessor(前驱)、successor(后继)、insert及delete)在O(lgn)时间内完成。

定义：

红黑树在二叉查找树的基础上增加了色域-red或者black。 一棵红黑树要满足下面4条性质：(1)结点要么是红的，要么是黑的。

(2)根和叶子节点都是黑的。

(3)一个结点是红的，那么它的父节点必须是黑的。

(4)任一结点到其叶子节点的简单路径上黑结点的个数要相同= 黑高度(不包括自身结点，但包括叶子节点)。

性质：

一个具有n个结点(不包括叶子节点)的红黑树的高度不超过2lg(n+1)。

因此这些动态集合的操作都在O(lgn)时间内能完成，所以红黑树是平衡的。

操作(插入和删除)

红黑树操作与二叉查找树的主要区别在于插入和删除，其它都是一样的。可参见上一篇blog。

插入：

并且红黑树只能通过插入操作来创建一棵红黑树以维持红黑特性。红黑树的插入操作分为三种情况.如下图

待传…..

其中case1为着色，可以一直可以向上移动，每次移动2层，由于树高≤2lg(n+1)，所以最多循环lg(n+1)次。case2和case3是终止情形，各旋转一次，都为O(1)时间。所以红黑树的插入操作可以在O(lgn)时间内完成.

代码如下：

RBTree.h

#ifndef RBTREE
#define RBTREE
#include <iostream>
#include <string>
using namespace std;

class BSTNode{
public:
	BSTNode *left, *right;
	BSTNode *parent;
	int val;
	string color;
};

class RBTree{
public:
	RBTree(const int &rootVal){
		root = new BSTNode();
		root->val = rootVal;
		root->parent = NULL;
		root->left = NULL;
		root->right = NULL;
		root->color = "black";
	}
	
	void insertRBTree(BSTNode *root, const int &value);   // 红黑树的插入
	void inorderRBTree(BSTNode *p);
	BSTNode *root;
private:
	BSTNode *insertBST(BSTNode *p, const int &value);       // 二叉树的插入
};

#endif

#include "RBTree.h"
using namespace std;

BSTNode* RBTree::insertBST(BSTNode *p, const int &value){
	BSTNode *y = NULL;
	BSTNode *in = new BSTNode();
	in->left = NULL;
	in->right = NULL;
	in->val = value;
	in->parent = NULL;

	while(p != NULL){
		y = p;
		if(p->val > in->val) p = p->left;
		else p = p->right;
	}
	
	if(y == NULL)
		p = in;
	else{
		in->parent = y;
		if(y->val > in->val) y->left = in;
		else y->right = in;
	}
	return in;
}

void RBTree::insertRBTree(BSTNode *root1, const int &value){
	BSTNode * in = insertBST(root1, value);
	in->color = "red";
	while(in != root1 && in->color == "red"){            // 对红黑特性进行调整
		if(in->parent->color == "black") return;   //  也就保证了必须
		if(in->parent == in->parent->parent->left){
			BSTNode *y = in->parent->parent->right;
			if(y != NULL && y->color == "red"){   //  case 1
				y->color = "black";
				y->parent->color = "red";
				in->parent->color ="black";
				in = in->parent->parent;
			}
			else{
				if(in == in->parent->right){      // case 2   in->parent 左旋
					BSTNode *pa = in->parent;
					in->parent = pa->parent;
					pa->parent->left = in;
					pa->parent = in;
					if(in->left != NULL)
						in->left->parent = pa;
					pa->right = in->left;
					in->left = pa;
					in = pa;
				}
				// case 3    in->parent->parent 右旋
				BSTNode *pa = in->parent;
				BSTNode *gpa = in->parent->parent;
				if(gpa->parent != NULL){
					if(gpa == gpa->parent->left){
						gpa->parent->left = pa;
					}else
						gpa->parent->right = pa;
				}
				pa->parent = gpa->parent;
				if(pa->right != NULL)
					pa->right->parent = gpa;
				gpa->left = pa->right;
				pa->right = gpa;
				gpa->parent = pa;
				pa->color = "black";
				gpa->color = "red";
			}
		}
		else{
			BSTNode *y = in->parent->parent->left;
			if(y != NULL && y->color == "red"){   //  case 1
				y->color = "black";
				y->parent->color = "red";
				in->parent->color ="black";
				in = in->parent->parent;
			}else{                               // do the same as A  but left与right对换
				if(in == in->parent->left){      // case 2   in->parent 右旋
					BSTNode *pa = in->parent;
					in->parent = pa->parent;
					pa->parent->right = in;
					pa->parent = in;
					if(in->right != NULL)
						in->right->parent = pa;
					pa->left = in->right;
					in->right = pa;
					in = pa;
				}
				// case 3    in->parent->parent 左旋
				BSTNode *pa = in->parent;
				BSTNode *gpa = in->parent->parent;
				if(gpa->parent != NULL){
					if(gpa == gpa->parent->left){
						gpa->parent->left = pa;
					}else
						gpa->parent->right = pa;
				}
				pa->parent = gpa->parent;
				if(pa->left != NULL)
					pa->left->parent = gpa;
				gpa->right = pa->left;
				pa->left = gpa;
				gpa->parent = pa;
				pa->color = "black";
				gpa->color = "red";
			}
		}
	}
	root1->color = "black";
}


void RBTree::inorderRBTree(BSTNode *p){
	if(p == NULL) return;
	if(p->left != NULL) inorderRBTree(p->left);
	cout << p->val << p->color  << " ";
	if(p->right != NULL) inorderRBTree(p->right);
}

Main.cpp

int a[10] = {5,4,6, 7,2,4, 1, 8, 5, 10};
	RBTree rbt(a[0]);
	for(int i =1; i < 10; i++)
		rbt.insertRBTree(rbt.root, a[i]);

	cout << "中序遍历的结果: " << endl;
	rbt.inorderRBTree(rbt.root);

删除：

待续…