目录

下一篇博客

红黑树的优点以及特点

为什么要使用c++来创建红黑树

红黑树的定义/特性

举例

代码

解释一下为什么新定义的叶子结点的初始值为红色而不为黑色

本节总结

下一篇博客

C++红黑树（2/4）_木木em哈哈的博客-CSDN博客https://blog.csdn.net/mumuemhaha/article/details/131159253?spm=1001.2014.3001.5502

红黑树的优点以及特点

红黑树是一种自平衡二叉查找树，它能够保证在最坏情况下基本动态集合操作（插入、删除、查找）的时间复杂度为O(log n)。红黑树通过在每个节点上增加一个存储位来表示节点的颜色，可以将树保持黑平衡，具体来说就是满足任何一条从根到叶子节点的路径上的黑节点数量相等。红黑树的性质包括：根节点是黑色的；每个叶子节点都是黑色的空节点；如果一个节点是红色的，则它的两个子节点都是黑色的；任意一节点到其每个叶子的所有路径都包含相同数目的黑色节点。这些性质保证了红黑树的平衡性和查找效率。

为什么要使用c++来创建红黑树

C++ 使用红黑树是为了保证数据结构的平衡和高效地支持插入、删除、查找等操作。红黑树也是关联容器 map 和 set 的底层实现之一。并且可以更好的理解指针和逻辑思维能力。

并且相对于二叉树和其他树，红黑树可以实现相对更快的查找

但是相对于其他的树，它的平衡性调整会比较繁琐也比较难理解

红黑树的定义/特性

  • 红黑树只会出现红色节点以及黑色节点且根节点一定是黑色
  • 所有叶子节点到根节点所经过的黑色节点一定相同
  • 最短路径的两倍不会超过最长路径

举例

如图

这是一棵红黑树

而下面都不是红黑树

不符合第三个条件：

所有叶子节点到根节点所经过的黑色节点一定相同

不符合第二个条件

红色节点不能相邻出现（黑色可以）

代码

则我们可以看到写出c++/c的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;
enum Colour//定义一个颜色
{
	RED,
	BLACK,
};
template<typename T>//定义一个模版T
struct RBNode//一个节点的结构体
{
	RBNode* lchild,
		* rchild,
		* parent;
	T	data;
	Colour colour=RED;//初始化为RED也可以后面定义一个初始化函数
};

template <typename T>//再定义一个模版T（template只能联系到下面一句语句）
class RBTree//树
{
public:
	RBTree()
	{
		root = nullptr;
	}
	~RBTree()
	{
		ReleaseNode(root);
	}
private:
	void ReleaseNode(RBNode<T>* pnode)//删除节点，释放内存
	{
		if (pnode != nullptr)
		{
			ReleaseNode(pnode->lchild);
			ReleaseNode(pnode->rchild);
		}
		delete pnode;
	}
private:
	RBNode <T>* root;//根节点
};

int main()
{
	printf("OK");//还没有到定义的时候
	return 0;
}

如图，其实到目前为止定义一个红黑树以及初始化和普通的二叉树并没有什么区别。

但是我们已经把大致的框架搭建出来

接下来要做的就是插入数据的平衡性调整

解释一下为什么新定义的叶子结点的初始值为红色而不为黑色

这里需要主要注意为什么新定义的叶子结点的初始值为红色而不为黑色

因为如果为黑色，由于红黑树的第三条特性，没插入之前红黑树各个的叶子结点已保持了平衡

而插入数据之后平衡一定会被打破

从而造成每次插入数据之后都要进行一次平衡性调整平衡性调整的概率为100%

而如果红色只会在父亲节点为红色是因为第二条特性要进行平衡性调整，而在父亲节点为黑色时则直接插入，无需进行平衡性调整。

本节总结

本篇博客介绍了红黑树的优点以及红黑树定义，接下来的三篇会讲到当父亲节点为红色时的几种情况以及一些平衡性调整。

我会更加简单也会更加通俗的去说明红黑树的平衡性调整