红黑树C++实现-创新互联

目录

创新互联公司坚持“要么做到，要么别承诺”的工作理念，服务领域包括：网站设计制作、成都做网站、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的万山网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

一、红黑树的概念

二、红黑树的性质

三、红黑树节点的定义

四、红黑树的插入

4.1 插入节点

4.2 插入节点的颜色

4.3 调整情况1

4.4 调整情况2

4.5 调整情况3

4.6 调整情况总结

五、调整的实现

5.1 调整的步骤分析

5.2 代码实现

六、树的平衡判断

七、源代码+测试代码

---

一、红黑树的概念

红黑树，是一种二叉搜索树，但在每个节点上增加一个存储位表示结点的颜色，可以是 Red 或 Black 。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确没有一条路径会比其他路径长出两倍，因而是接近平衡的。

二、红黑树的性质

1. 每个节点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个节点，从该节点到其后代叶节点的简单路径上，均包含相同数目的黑色节点。
5. 每个叶子节点都是黑色的(此处的叶子节点指的是空节点)

解读：

性质三：保证树中没有连续的红色节点

性质四：每条路径上黑色节点的数目相同

满足以上性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍

其中，其极限最短：全黑。极限最长：一黑一红……

三、红黑树节点的定义

因为性质一，节点的颜色不是红就是黑，所以我们可以使用枚举来清晰的区分。

四、红黑树的插入 4.1 插入节点

红黑树本质也是二叉搜索树，所以插入的方式是相同的。只是调整平衡的方式不同。插入的代码如下：

bool Insert(const pair& kv)
	{
		if (!_root)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _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.2 插入节点的颜色

接下来我们就要分析，插入的节点默认应该是红色还是黑色。

首先分析插入黑节点。如下：

插入黑节点后，直接就破坏了红黑树的规则四，因为每条路径上的黑色节点数不再相同了，所以说插入黑节点是一定会出错的。

接下来我们看看插入红节点。

此中情况下，破坏了规则三，其红节点下必须是黑节点。

在这种情况下，插入红节点，既没有破坏规则三，也没有破坏规则四。所以说，插入红节点有几率会破坏规则，而插入黑节点一定会破坏规则，且破坏了整棵树，所以我们默认插入红节点。

那如果出现以上插入红节点破坏规则我们要怎么处理呢？

我们采取 变色+旋转 的策略，以上这种情况我们只需要变色即可解决。如图所示：

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；

但当新插入节点的双亲结点颜色为红色时，就违反了性质三不能有连续在一起的红色节点，此时就需要对红色数分情况来解决。

即双亲黑色不调整，双亲红色则调整。

4.3 调整情况1

情况一：cur 为红，parent为红，grandfather为黑，uncle存在且为红.

解决方式：将p，u 改为黑，g改为红，然后把 g 当作 cur，继续向上调整。

4.4 调整情况2

情况二：cur 为红，p 为红，g 为黑，u 不存在/ u 存在且为黑。

1. 如果 u 节点不存在，则 cur 一定是新插入节点，因为如果 cur 不是新插入节点，则 cur 和 p 一定有一个节点的颜色是黑色，就不满足性质4：每条路径黑色节点的个数相同。
2. 如果 u 节点存在，则其一定是黑色的，那么 cur 节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为 cur 的子树在调整的过程中将 cur 节点的颜色由黑色改成红色。

此时这种情况，单纯的变色是无法解决的，我们就要采取旋转+变色的方式。

此时我们的解决策略是将 p 变黑，g 变红，然后让其对 g 进行右单旋。

4.5 调整情况3

情况三：cur 为红，p 为红，g 为黑，u 不存在 / u 存在且为黑

调整策略：

p 为 g 的左孩子，cur 为 p 的右孩子，则针对 p 进行左单旋，则转变为情况 2，然后再进行情况 2 的右单旋+变色即可。

4.6 调整情况总结

在学习了AVL 树 之后，这三种情况其实也都能理解，接下来我们对其做一个总结。

红黑树的关键在于叔叔。因为知道叔叔节点的情况，可以了解到另一棵子树的高度情况。

三种情况：

1. u 存在且为红，变色并继续向上处理
2. u 不存在或为黑，进行 单旋+变色
3. u 不存在或为黑，插入方式为折线，进行 双旋+变色。

五、调整的实现 5.1 调整的步骤分析

1. 只有当cur 为红，p 为红，g 为黑，则进行调整。(p为黑不用调整，p 为红，则grandfather必然为黑，要不然此时不为红黑树)
2. 查看 uncle 的位置，同时也是判断插入节点在 g 的左子树还是右子树。
3. 情况1，uncle存在且为红，进行情况一的调整(变色+继续往上更新)。
4. 如果uncle不存在或为黑，则为情况二或三
5. 如果插入在边侧，则进行单旋+变色
6. 如果插入在内侧，则进行双旋+变色。

5.2 代码实现

以下只有调整的代码，没有截取插入的代码。

//1.因为插入的节点为红色， 如果parent也为红色，进行处理
while (parent && parent->_col == RED)
{
	Node* grandfater = parent->_parent;
	//2.判断爷节点的合法性
	assert(grandfater);
	assert(grandfater->_col == BLACK);
	//3.查看叔叔
	//4.首先判断叔叔位于grandfater的left 还是 right
	if (grandfater->_left == parent)
	{
		Node* uncle = grandfater->_right;
		//5.情况1，叔叔存在 && 叔叔为红色
		if (uncle && uncle->_col == RED)
		{
			//6.将父、树变黑，祖父变红
			parent->_col = uncle->_col = BLACK;
			grandfater->_col = RED;
			//7.并继续往上处理
			cur = grandfater;
			parent = cur->parent;
		}
		//8.情况2+情况3  uncle不存在或为黑
		else
		{
			//9.判断单旋还是双旋
			//      g          
			//    p   u
			//  c            右单旋+变色
			if (cur == parent->_left)
			{
				RotateR(grandfater);
				parent->_col = BLACK;
				grandfater->_col = RED;
			}
			//    g          左右双旋+变色
			//   p  u        
			//    c
			else
			{
				RotateL(parent);
				RotateR(grandfater);
				cur->_col = BLACK;
				grandfater->_col = RED;
			}
			break;
		}
	}
	else
	{
		Node* uncle = grandfater->_left;
		if (uncle && uncle->_col == RED)
		{
			parent->_col = uncle->_col = BLACK;
			grandfater->_col = RED;
			//继续往上处理
			cur = grandfater;
			parent = cur->parent;
		}
		else
		{
			//9.判断单旋还是双旋
			//      g          
			//    u   p
			//          c    左单旋+变色
			if (cur == parent->_right)
			{
				RotateL(grandfater);
				parent->_col = BLACK;
				grandfater->_col = RED;
			}
			//    g          右左双旋+变色
			//   u  p        
			//     c
			else
			{
				RotateR(parent);
				RotateL(grandfater);
				cur->_col = BLACK;
				grandfater->_col = RED;
			}
			break;
		}
	}
}

//因为以上会将祖父变红，直接将_root变黑
_root->_color = BLACK;
return true;

好的，实现了插入之后，我们来使用一段测试代码测试一下 Insert

六、树的平衡判断

实现 Insert 之后，只能证明当前的结构是一棵搜索树，而不能证明其是否为红黑树，接下来我们还要编写一个Balanceu验证平衡。

所以这个判定平衡的函数应该按照红黑树的规则，来进行判定该树是否符合红黑树的性质。即，算每条路径上的黑节点数量，如果路径上的黑节点数量相同，则说明是红黑树。

实现步骤：

1. 计算最左/右边路径上的黑节点个数，将该值设为基准值。
2. 走前序遍历，遇到黑节点则将将计数器++
3. 如果当前节点的为红，并且父节点也为红则直接返回false。
4. 如果该路径上的黑节点总数等于基准值，则返回true，反之返回false。

代码如下：

bool IsBalance()
{
	if (_root == nullptr)
	{
		return true;
	}
	if (_root->_col == RED)
	{
		cout<< "根节点不是黑色"<< endl;
		return false;
	}

	//设置基准值,以来校验路径上的黑节点
	int benchmark = 0;
	Node* cur = _root;
    //计算左侧路径上的黑色节点数量
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			++benchmark;
		}
		cur = cur->_left;
	}
	return PrevCheck(_root, 0, benchmark);
}
bool PrevCheck(Node* root, int blackNum, int Benchmark)
{
	if (root == nullptr)
	{
		if (blackNum != Benchmark)
			return false;
		else
			return true;
	}
	if (root->_col == BLACK)
		++blackNum;
	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout<< "存在连续的红色节点"<< endl;
		return false;
	}

	return PrevCheck(root->_left, blackNum, Benchmark)
		&& PrevCheck(root->_right, blackNum, Benchmark);
}

以上检查方式就按照红黑树的三条重要性质进行了检查，

1.根节点为黑色；2.不存在连续的红节点；3.每条路径上的黑节点个数相同。

满足以上三点才能证明该结构为红黑树。

接下来我们进入测试。

测试一：

测试二：

注意一件事情，我们使用的是键值对的形式进行插入的，如果 k 存在了，则不会进行插入，并且红黑树中的排序是按照 k 的大小进行排序的，所以使用 find 函数时，要按 pair.first 查找，因为 pair.second并按搜索树的规则存储的。 

七、源代码+测试代码

红黑树代码(实现了插入、查找、中序遍历、高度、平衡检测)

#includeusing namespace std;

enum Color { RED, BLACK };
//节点的定义
templatestruct RBTreeNode
{
	RBTreeNode* _left;	
	RBTreeNode* _right;	
	RBTreeNode* _parent;	

	pair_kv;			    
	Color _col;					

	RBTreeNode(const pair& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)               
	{}
};
//红黑树
templateclass RBTree
{
	typedef RBTreeNodeNode;
public:
	bool Insert(const pair& kv)
	{
		if (!_root)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _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* grandfater = parent->_parent;
			assert(grandfater);
			assert(grandfater->_col == BLACK);
			if (grandfater->_left == parent)
			{
				Node* uncle = grandfater->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfater->_col = RED;
					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}					else
					{
						RotateL(parent);
						RotateR(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfater->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfater->_col = RED;
					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;

	}
	void Inorder()
	{
		_Inorder(_root);
	}
	int Height()
	{
		return _Height(_root);
	}
	pairFind(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first >key)
			{
				cur = cur->_left;
			}
			else if (cur->_kv.first< key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur->_kv;
			}
		}
		return pair(0, 0);
	}
	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return true;
		}
		if (_root->_col == RED)
		{
			cout<< "根节点不是黑色"<< endl;
			return false;
		}

		//设置基准值,以来校验路径上的黑节点
		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++benchmark;
			}
			cur = cur->_left;
		}
		return PrevCheck(_root,0, benchmark);
	}
	
private:

	bool PrevCheck(Node* root, int blackNum,int Benchmark)
	{
		if (root==nullptr)
		{
			//cout<< blackNum<< endl;
			if (blackNum == 2)                 //     3 
			{                                  //   7   16
				int n = 0;                     //      11
			}                                  //
			if (blackNum != Benchmark)
				return false;
			else 
			return true;
		}
		if (root->_col == BLACK)
			++blackNum;
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout<< "存在连续的红色节点"<< endl;
			return false;
		}

		return PrevCheck(root->_left, blackNum, Benchmark)
		&& PrevCheck(root->_right, blackNum, Benchmark);
	}

	void _Inorder(Node* root)
	{
		if (root)
		{
			_Inorder(root->_left);
			cout<< root->_kv.first<< ":"<< root->_kv.second<< endl;
			_Inorder(root->_right);
		}
	}

	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		return max(_Height(root->_left), _Height(root->_right)) + 1;
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		subR->_left = parent;
		if (subRL)  
			subRL->_parent = parent;

		Node* ppNode = parent->_parent;
		parent->_parent = subR;
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else  
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* ppNode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;
		if (ppNode)
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
		else
		{
			_root = subL;
			subL->_parent = nullptr;
		}
	}
    //成员变量 _root 
	Node* _root=nullptr; 
};

测试代码

void TestRBTree1()
{
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	RBTreet1;
	for (auto e : a)
	{
		t1.Insert(e);
	}
	t1.Inorder();

	//检测是否为红黑树
	if (t1.IsBalance())
		cout<< "Is RedBlackTree"<< endl;
	else
		cout<< "Not RedBlackTree"<< endl;

	//查找 18 
	cout<< "Find（18）：";
	int result = t1.Find(18);
	cout<< result<< endl;

}

void TestRBTree2()
{
	size_t N = 10000000;
	RBTreet1;
	for (size_t i = 0; i< N; ++i)
	{
		t1.Insert(i);
	}
	cout<<"Height:"<< t1.Height()<< endl;

	//检测是否为红黑树
	if (t1.IsBalance())
		cout<< "Is RedBlackTree"<< endl;
	else
		cout<< "Not RedBlackTree"<< endl;

	int  result = t1.Find(23451);
	cout<< result<< endl;

}

int main()
{
	TestRBTree1();
	TestRBTree2();
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

标题名称：红黑树C++实现-创新互联
网址分享：http://cqcxhl.com/article/csjcdj.html