1.红黑树简介：

红黑树实际上和AVL都属于一棵用于存储数据的平衡二叉搜索树，但是这棵树并不是使用平衡因子去维持平衡的，而是结合限制条件对结点标红标黑去让树达到类似平衡的效果。

2.红黑树的限制条件和效率分析：

2.1限制条件

1. 每个结点不是红⾊就是⿊⾊
2. 根结点是⿊⾊的
3. 如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的
红⾊结点。
4. 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点

2.2效率分析

由规则四可以知道每条路径上的黑结点个数相同，那么在极端情况下，最短路径就是全黑，最长路径就是一黑一红，设最短路径长度为h，最长则为2h，2^{h}-1<N<2^{2h}-1,推导可得h基本上就是为一个logn，说明在插入的时候最差的时间复杂度也就为接近2*logn。

3.红黑树构建时的准备：

3.1红黑标记：

3.2红黑树的结点结构设计：

这里每个结点默认都是处理为红色，因为如果你处理成黑色的话，那当别的地方要处理成红色的时候，别的地方要保持规则四就很困难了，因为这个存储结构是一棵树。

3.3红黑树的结构设计：

template<class K, class V>
class rb_tree {
	typedef rb_tree_node<K,V> node;
private:
	node* root_=nullptr;
};

基本上和AVL树很类似。

3.4处理前的插入：

bool insert(const pair<K, V>& kv) {
	if (root_ == nullptr) {
		root_ = new node(kv);
		root_->col = BLACK;//规定的根为黑色
		return true;
	}
	node* cur = root_;//这部分就和别的二叉搜索树一致
	node* parent = root_;
	while (cur) {
		if (cur->kv_.first > kv.first) {
			parent = cur;
			cur = cur->left;
		}
		else if (cur->kv_.first < kv.first) {
			parent = cur;
			cur = cur->right;
		}
		else {
			return false;
		}
	}
	cur = new node(kv);
	if (parent->kv_.first > kv.first) {
		parent->left = cur;
	}
	else {
		parent->right = cur;
	}
	cur->parent = parent;

4.对违反规则的地方进行处理：

4.1情况1：

当插入x时，因为红色的子结点必须是黑色的，所以需要进行处理，如果他的叔叔结点是红色的，那么无论他是在6还是15插入，只需要把它的叔叔结点和父亲结点变为黑色，然后再把它的父亲变为红色。那么就能保证规则不被破坏，每条路的黑结点个数都相同。这里并不是就是结束！当变为红色的时候，可能导致上面的规则遭到破坏，也就是它的上方可能是红色的，那么它也得进行类似的处理。

4.2情况2：

当插入位置为在cur且叔叔为黑色或者不存在的时候，通过这样处理之后可以让规则得到满足。也就是进行一次右单选再与情况1进行相同方式的变色。

4.3情况3：

当cur位置为在cur且叔叔为黑色或者不存在的时候，通过这样处理之后可以让规则得到满足。也就是进行一次左单选再右单旋最后与情况1进行相同方式的变色。

这里还存在一种特殊情况，就是有可能根结点会被处理成红色，但是，根结点实际上是不会影响分路上黑结点分布相同的。所以最后只需要把根结点也处理成黑色就能保证规则不会出现问题。

通过这三种情况就能够把所有情况给包含进去了。

4.4代码展示：

	while (parent && parent->col == RED) {//
		node* grandfather = parent->parent;
		if (grandfather->left == parent) {//处理左子树
			if (grandfather->right && grandfather->right->col == RED) {//叔是红色
				parent->col = BLACK;//变色
				grandfather->right->col = BLACK;
				grandfather->col = RED;
				cur = grandfather;//往上接着迭代
				parent = grandfather->parent;
			}
			else {//叔叔不存在或者叔叔为黑色
				if (cur == parent->left) {//只需要单旋就能解决
					rotateR(grandfather);
					grandfather->col = RED;
					parent->col = BLACK;
				}
				else {//需要双旋才能解决
					rotateL(parent);
					rotateR(grandfather);
					grandfather->col = RED;
					parent->col = BLACK;
				}
				break;
			}
		}
		else {
			if (grandfather->left&&grandfather->left->col == RED) {//叔是红色
				parent->col = BLACK;//变色
				grandfather->left->col = BLACK;
				grandfather->col = RED;
				cur = grandfather;//往上接着迭代
				parent = grandfather->parent;
			}
			else {//叔叔不存在或者叔叔为黑色
				if (cur == parent->right) {//只需要单旋就能解决
					rotateL(grandfather);
					grandfather->col = RED;
					parent->col = BLACK;
				}
				else {//需要双旋才能解决
					rotateR(parent);
					rotateL(grandfather);
					grandfather->col = RED;
					parent->col = BLACK;
				}
				break;
			}
		}
		
	}root_->col = BLACK;//最后记得把根结点的颜色变为黑色
	return true;
}

5.完整代码展示：

#include <iostream>
using namespace std;
enum color {
	RED,
    BLACK
};
template<class K,class V>
class rb_tree_node {
public:
	rb_tree_node(const pair<K, V>& kv) :
		kv_(kv)
		, right(nullptr)
		, left(nullptr)
		, parent(nullptr)
		, col (RED){}
	rb_tree_node* right;
	rb_tree_node* left;
	rb_tree_node* parent;
	pair<K, V> kv_;
	color col;
};
template<class K, class V>
class rb_tree {
	typedef rb_tree_node<K,V> node;
public:
	bool insert(const pair<K, V>& kv) {
		if (root_ == nullptr) {
			root_ = new node(kv);
			root_->col = BLACK;
			return true;
		}
		node* cur = root_;
		node* parent = root_;
		while (cur) {
			if (cur->kv_.first > kv.first) {
				parent = cur;
				cur = cur->left;
			}
			else if (cur->kv_.first < kv.first) {
				parent = cur;
				cur = cur->right;
			}
			else {
				return false;
			}
		}
		cur = new node(kv);
		if (parent->kv_.first > kv.first) {
			parent->left = cur;
		}
		else {
			parent->right = cur;
		}
		cur->parent = parent;
		while (parent && parent->col == RED) {
			node* grandfather = parent->parent;
			if (grandfather->left == parent) {
				if (grandfather->right && grandfather->right->col == RED) {//叔是红色
					parent->col = BLACK;//变色
					grandfather->right->col = BLACK;
					grandfather->col = RED;
					cur = grandfather;//往上接着迭代
					parent = grandfather->parent;
				}
				else {//叔叔不存在或者叔叔为黑色
					if (cur == parent->left) {//只需要单旋就能解决
						rotateR(grandfather);
						grandfather->col = RED;
						parent->col = BLACK;
					}
					else {//需要双旋才能解决
						rotateL(parent);
						rotateR(grandfather);
						grandfather->col = RED;
						parent->col = BLACK;
					}
					break;
				}
			}
			else {
				if (grandfather->left&&grandfather->left->col == RED) {//叔是红色
					parent->col = BLACK;//变色
					grandfather->left->col = BLACK;
					grandfather->col = RED;
					cur = grandfather;//往上接着迭代
					parent = grandfather->parent;
				}
				else {//叔叔不存在或者叔叔为黑色
					if (cur == parent->right) {//只需要单旋就能解决
						rotateL(grandfather);
						grandfather->col = RED;
						parent->col = BLACK;
					}
					else {//需要双旋才能解决
						rotateR(parent);
						rotateL(grandfather);
						grandfather->col = RED;
						parent->col = BLACK;
					}
					break;
				}
			}
			
		}root_->col = BLACK;
		return true;
	}
	void rotateR(node* parent) {
		node* sub_L = parent->left;
		node* sub_LR = sub_L->right;
		parent->left = sub_LR;
		if (sub_LR) {
			sub_LR->parent = parent;
		}
		sub_L->right = parent;
		if (parent == root_) {
			root_ = sub_L;
		}
		node* ppnode;
		ppnode = parent->parent;
		if (ppnode) {
			if (ppnode->right == parent) {
				ppnode->right = sub_L;
			}
			else {
				ppnode->left = sub_L;
			}
		}
		parent->parent = sub_L;
	}
	void rotateL(node* parent) {
		node* sub_R = parent->right;
		node* sub_RL = sub_R->left;
		parent->right = sub_RL;
		if (sub_RL) {
			sub_RL->parent = parent;
		}
		sub_R->left = parent;
		if (parent == root_) {
			root_ = sub_R;
		}
		node* ppnode;
		ppnode = parent->parent;
		if (ppnode) {
			if (ppnode->right == parent) {
				ppnode->right = sub_R;
			}
			else {
				ppnode->left = sub_R;
			}
		}
		parent->parent = sub_R;
	}
	void inorder() {
		inorder_(root_);
	}
private:
	void inorder_(node* root) {
		if (root == nullptr) {
			return;
		}
		inorder_(root->left);
		cout << root->kv_.first <<" ";
		inorder_(root->right);
	}
	node* root_=nullptr;
};
int main() {
	rb_tree<int, int>tree1;
	tree1.insert({ 2,2 });
	tree1.insert({ 3,2 });
	tree1.insert({ 1,2 });
	tree1.insert({ 5,2 });
	tree1.insert({ 4,2 });
	tree1.insert({ 6,2 });
	tree1.inorder();
	return 0;
}


 

# c++ # 数据结构 # 算法
Logo
腾讯云开发者社区

腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。

更多推荐

Elasticsearch复杂数据类型终极指南：从入门到精通

Elasticsearch作为功能强大的搜索引擎，支持多种复杂数据类型，让开发者能够灵活处理各种结构化和非结构化数据。本文将带你全面了解Elasticsearch中的复杂数据类型，从基础概念到实际应用，助你轻松掌握数据建模的核心技巧。## 内部对象：构建层级化数据结构在Elasticsearch中，对象类型（Object）是最基础的复杂数据类型之一，用于表示具有嵌套关系的数据。例如，我们可

avatar 腾讯云开发者社区

终极指南：Flink SQL连接器版本管理从混乱到有序的升级之路

Apache Flink作为流处理领域的佼佼者，其SQL连接器的版本管理一直是开发者面临的核心挑战。本文将系统讲解Flink SQL连接器版本管理的最佳实践，帮助你轻松应对版本兼容性问题，实现从混乱到有序的升级之旅。## 连接器版本管理的常见痛点 😫在Flink应用开发中，连接器版本管理常常让开发者头疼不已。不同版本的连接器可能导致各种兼容性问题，例如API变更、功能差异甚至运行时错误。

avatar 腾讯云开发者社区

如何快速搭建Neon无服务器PostgreSQL：面向初学者的完整指南

Neon是一款革命性的无服务器PostgreSQL解决方案，它通过分离存储和计算层，实现了自动扩缩容、类代码式数据库分支以及零级扩展能力。本指南将帮助你从零开始搭建Neon开发环境，体验这款创新数据库的强大功能。## 准备工作：环境要求与依赖项在开始搭建Neon环境前，请确保你的系统满足以下要求：- Linux操作系统（推荐Ubuntu 20.04+或Debian 11+）- Git

avatar 腾讯云开发者社区