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

今天药忘吃喽~ 2022-08-06 15:07 64阅读 0赞

随机构建的二叉查找树的高度期望值为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

RBTree.cpp

#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);

Result:

![Center][]

**删除：**

待续…

[Center]: /images/20220805/c3fc4c8c27bc45ff982c5479a978ab6c.png