C++红黑树(1/4)

mumuemhaha 2023-6-11 39 6/11

下一篇博客

C++红黑树(2/4)

红黑树的优点以及特点

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

红黑树的定义/特性

  • 1.红黑树只会出现红色节点以及黑色节点且根节点一定是黑色
  • 2.红色节点不能相邻出现(黑色可以)
  • 3.所有叶子节点到根节点所经过的黑色节点一定相同
  • 4.最短路径的两倍不会超过最长路径

举例

如图

这是一棵红黑树

C++红黑树(1/4)

而下面都不是红黑树

C++红黑树(1/4)

不符合第三个条件

C++红黑树(1/4)

不符合第二个条件

代码

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

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

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

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


  • 这里需要主要注意为什么新定义的叶子结点的初始值为红色而不为黑色
  • 因为如果为黑色,由于红黑树的第三条特性,没插入之前红黑树各个的叶子结点已保持了平衡
  • 而插入数据之后平衡一定会被打破
  • 从而造成每次插入数据之后都要进行一次平衡性调整
  • 而如果红色只会在父亲节点为红色是因为第二条特性要进行平衡性调整,而在父亲节点为黑色时则直接插入,无需进行平衡性调整。

总结

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

- THE END -
Tag:

mumuemhaha

6月11日23:55

最后修改:2023年6月11日
0

非特殊说明,本博所有文章均为博主原创。

共有 0 条评论