1. Toy模板网首页
  2. > Toy博客

C++数据结构--红黑树

10月前 作者：高比拜仁0824 分类：Toy博客 阅读(48) 违法举报

这篇具有很好参考价值的文章主要介绍了C++数据结构--红黑树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。如图所示：
C++数据结构--红黑树,C++,c++,数据结构,开发语言,c语言,windows,visual studio

二、红黑树的性质

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

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

因为根节点是黑色是固定的，并且不能有连续的红色节点，每条路径黑色节点的个数一样，也就是说最短路就是全黑，最长路径就是一黑一红相间，所以一条路径的红色节点要么和黑色节点一样多，要么少于黑色节点，即同一条路径黑色节点的占比是大于等于50%的，所以最长路径一定不超过最短路径的2倍。

三、红黑树的节点的定义

	//通过枚举定义红色和黑色的常量
	enum Colour
	{
		RED,
		BLACK
	};
	template <class K,class V>
	struct RBTreeNode
	{
	public:
		//红黑树存放的值
		pair<K, V> _kv;

		//节点的三叉链指针
		RBTreeNode<K,V>* _left;
		RBTreeNode<K,V>* _right;
		RBTreeNode<K,V>* _parent;

		//节点的颜色
		Colour _col;

		//构造函数
		RBTreeNode(const pair<K, V>& kv)
			:_kv(kv)
			, _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _col(RED)
		{}

	};

思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？
这个问题就是关于插入节点的时候我们默认插入的是黑色的节点还是红色的节点了，根据红黑树的规则，每一条路径的黑色节点的个数是一样的，假如我们插入黑色节点，那么某条路径的黑色节点就多了一个，也就是说其它路径的黑色节点也要增加一个，但是我们只插入了一个节点，要令其它路径的黑色节点的数量都增加一个，这个操作的难度显然是很大的，但是如果我们默认插入一个红色节点，那么我们最多违反了根节点为黑色或者连续两个红色节点的规则，主要还是容易违反连续两个红色节点的规则，这个问题只会影响当前节点到祖先这条路径，不会影响其他路径的节点，所以处理起来会更简洁一些，所以我们默认插入的节点是红色的。

四、红黑树结构

C++数据结构--红黑树,C++,c++,数据结构,开发语言,c语言,windows,visual studio

五、红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

  1. 按照二叉搜索树的规则插入新节点。
  2. 检测新节点插入后，红黑树的性质是否遭到破坏，如果是，就要通过变色加旋转操作维持红黑树的性质。

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点。

情况一: cur为红，p为红，g为黑，u存在且为红。
C++数据结构--红黑树,C++,c++,数据结构,开发语言,c语言,windows,visual studio
情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑。
因为旋转后需要把p变成黑色，所以p节点和p的父节点不能再出现连续两个红色节点，所以旋转+变色后就不用再沿祖先路径更新了。

C++数据结构--红黑树,C++,c++,数据结构,开发语言,c语言,windows,visual studio
情况一：
C++数据结构--红黑树,C++,c++,数据结构,开发语言,c语言,windows,visual studio
情况二：
C++数据结构--红黑树,C++,c++,数据结构,开发语言,c语言,windows,visual studio
情况三：
C++数据结构--红黑树,C++,c++,数据结构,开发语言,c语言,windows,visual studio
情况四：
C++数据结构--红黑树,C++,c++,数据结构,开发语言,c语言,windows,visual studio

参考代码

		bool Insert(const pair<K, V>& kv)
		{
			//如果是空树，那么就直接插入一个黑色节点做根即可
			//注意要改颜色，因为节点的颜色默认是红色的
			if (_root == nullptr)
			{
				_root = new Node(kv);
				_root->_col = BLACK;
				return true;
			}

			//根据二叉搜索树的规则插入节点，同时记录父节点
			Node* parent = nullptr;
			Node* cur = _root;

			while (cur)
			{
				if (kv.first < cur->_kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (kv.first > cur->_kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(kv);
			if (kv.first < parent->_kv.first)
			{
				parent->_left = cur;
				cur->_parent = parent;
			}
			else if (kv.first > parent->_kv.first)
			{
				parent->_right = cur;
				cur->_parent = parent;
			}

			//走到这里已经插入完成，后面是检查新插入的节点有没有破坏红黑树的规则的逻辑

			//检查新插入的节点是否满足红黑树的规则，如果不满足就要进行变色/变色+旋转
			//因为新插入的cur节点的颜色一定是红色的，当cur的父节点存在并且为红色
			//时说明出现了连续的两个红色节点，这时需要进行变色/变色+旋转，如果父节点
			// 不存在或者存在且为黑色时就无需再处理了。
			// 为什么父节点有可能不存在？因为这是一个循环，循环更新往祖先处理可能到达根节点，
			//到了根节点就无需再处理了
			while (parent && parent->_col == RED)
			{
				Node* grandfather = parent->_parent;

				if (parent == grandfather->_left)
				{
					Node* uncle = grandfather->_right;

					if (cur == parent->_left)
					{
						//             grandfather
						//     parent
						//cur

						//画图
						//叔叔存在且为红
						if (uncle && uncle->_col == RED)
						{
							//变色
							parent->_col = BLACK;
							uncle->_col = BLACK;
							grandfather->_col = RED;

							//继续沿祖先路径检查
							cur = grandfather;
							parent = cur->_parent;//这里曾经漏写了
						}
						//叔叔不存在或者存在且为黑
						else//(uncle==nullptr||uncle->_col==BLACK)
						{
							//单纯的左边高，进行右单旋+变色
							RotateR(grandfather);
							grandfather->_col = RED;
							parent->_col = BLACK;

							//旋转完之后无需再沿祖先路径处理
							break;
						}
					}
					else//cur == parent->_right
					{
						//              grandfather
						//       parent
						//              cur

						//画图
						//叔叔存在且为红
						if (uncle && uncle->_col == RED)
						{
							//变色
							parent->_col = BLACK;
							uncle->_col = BLACK;
							grandfather->_col = RED;

							//继续往上调整
							cur = grandfather;
							parent = cur->_parent;//这里曾经忘记写
						}
						//叔叔不存在或者存在且为黑
						else//(uncle==nullptr || uncle->_col == BLACK)
						{
							//左右双旋
							RotateL(parent);
							RotateR(grandfather);
							//变色
							grandfather->_col = RED;
							cur->_col = BLACK;

							//旋转后就无需再沿祖先路径检查了，具体原因画图理解
							break;
						}

					}
				}
				else//(parent == grandfather->_right)
				{
					Node* uncle = grandfather->_left;
					if (cur == parent->_right)
					{
						//          grandfather
						//                         parent
						//                                    cur

						//画图
						//叔叔存在且为红
						if (uncle && uncle->_col == RED)
						{
							//变色
							parent->_col = BLACK;
							uncle->_col = BLACK;
							grandfather->_col = RED;

							//继续沿祖先路径检查
							cur = grandfather;
							parent = cur->_parent;
						}
						//叔叔不存在或者存在且为黑
						else//(uncle==nullptr || uncle->_col == BLACK)
						{
							//单纯的右边高，进行左单旋+变色
							RotateL(grandfather);
							grandfather->_col = RED;
							parent->_col = BLACK;

							//旋转+变色后就不需要再沿祖先路径检查了
							break;
						}
					}
					else//(cur == parent->_left)
					{
						//          grandfather
						//                          parent
						//          cur

						//叔叔存在且为红
						if (uncle && uncle->_col == RED)
						{
							//变色
							parent->_col = BLACK;
							uncle->_col = BLACK;
							grandfather->_col = RED;
							
							//继续沿祖先路径检查
							cur = grandfather;
							parent = cur->_parent;
						}
						//叔叔不存在或者存在且为黑
						else//(uncle==nullptr || uncle->_col == BLACK)
						{
							//根据模型可知需要右左双旋+变色
							RotateR(parent);
							RotateL(grandfather);
							grandfather->_col = RED;
							cur->_col = BLACK;

							//旋转后就不需要再沿祖先路径检查了
							break;
						}
					}
				}
			}

			_num++;

			//最后记得把根节点的颜色改成黑色
			_root->_col = BLACK;
			return true;
		}
		//旋转的细节如果不清楚的话请看上一篇关于AVL树的旋转，红黑树的旋转和AVL树的旋转是一样的
		void RotateL(Node* parent)
		{
			assert(parent);
			Node* cur = parent->_right;
			Node* curleft = cur->_left;
			Node* parentParent = parent->_parent;

			parent->_right = curleft;
			cur->_left = parent;
			if (curleft)
			{
				curleft->_parent = parent;
			}
			parent->_parent = cur;

			if (parent == _root)
			{
				_root = cur;
				cur->_parent = nullptr;
			}
			else
			{
				if (parent == parentParent->_left)
				{
					parentParent->_left = cur;
				}
				else
				{
					parentParent->_right = cur;
				}
				cur->_parent = parentParent;
			}

		}

		void RotateR(Node* parent)
		{
			assert(parent);
			Node* cur = parent->_left;
			Node* curright = cur->_right;
			Node* parentParent = parent->_parent;

			parent->_left = curright;
			cur->_right = parent;
			if (curright)
			{
				curright->_parent = parent;
			}
			parent->_parent = cur;

			if (parent == _root)
			{
				_root = cur;
				cur->_parent = nullptr;
			}
			else
			{
				if (parent == parentParent->_left)
				{
					parentParent->_left = cur;
				}
				else
				{
					parentParent->_right = cur;
				}

				cur->_parent = parentParent;
			}

		}

五、代码汇总

#pragma once


#include <iostream>
using namespace std;
#include <assert.h>

namespace kb
{
	enum Colour
	{
		RED,
		BLACK
	};

	template <class K,class V>
	struct RBTreeNode
	{
	public:
		//红黑树存放的值
		pair<K, V> _kv;

		//节点的三叉链指针
		RBTreeNode<K,V>* _left;
		RBTreeNode<K,V>* _right;
		RBTreeNode<K,V>* _parent;

		//节点的颜色
		Colour _col;

		//构造函数
		RBTreeNode(const pair<K, V>& kv)
			:_kv(kv)
			, _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _col(RED)
		{}

	};

	template <class K,class V>
	class RBTree
	{
		typedef RBTreeNode<K, V> Node;
	public:
		bool Insert(const pair<K, V>& kv)
		{
			//如果是空树，那么就直接插入一个黑色节点做根即可
			//注意要改颜色，因为节点的颜色默认是红色的
			if (_root == nullptr)
			{
				_root = new Node(kv);
				_root->_col = BLACK;
				return true;
			}

			//根据二叉搜索树的规则插入节点，同时记录父节点
			Node* parent = nullptr;
			Node* cur = _root;

			while (cur)
			{
				if (kv.first < cur->_kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (kv.first > cur->_kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(kv);
			if (kv.first < parent->_kv.first)
			{
				parent->_left = cur;
				cur->_parent = parent;
			}
			else if (kv.first > parent->_kv.first)
			{
				parent->_right = cur;
				cur->_parent = parent;
			}

			//走到这里已经插入完成，后面是检查新插入的节点有没有破坏红黑树的规则的逻辑

			//检查新插入的节点是否满足红黑树的规则，如果不满足就要进行变色/变色+旋转
			//因为新插入的cur节点的颜色一定是红色的，当cur的父节点存在并且为红色
			//时说明出现了连续的两个红色节点，这时需要进行变色/变色+旋转，如果父节点
			// 不存在或者存在且为黑色时就无需再处理了。
			// 为什么父节点有可能不存在？因为这是一个循环，循环更新往祖先处理可能到达根节点，
			//到了根节点就无需再处理了
			while (parent && parent->_col == RED)
			{
				Node* grandfather = parent->_parent;

				if (parent == grandfather->_left)
				{
					Node* uncle = grandfather->_right;

					if (cur == parent->_left)
					{
						//             grandfather
						//     parent
						//cur

						//画图
						//叔叔存在且为红
						if (uncle && uncle->_col == RED)
						{
							//变色
							parent->_col = BLACK;
							uncle->_col = BLACK;
							grandfather->_col = RED;

							//继续沿祖先路径检查
							cur = grandfather;
							parent = cur->_parent;//这里曾经漏写了
						}
						//叔叔不存在或者存在且为黑
						else//(uncle==nullptr||uncle->_col==BLACK)
						{
							//单纯的左边高，进行右单旋+变色
							RotateR(grandfather);
							grandfather->_col = RED;
							parent->_col = BLACK;

							//旋转完之后无需再沿祖先路径处理
							break;
						}
					}
					else//cur == parent->_right
					{
						//              grandfather
						//       parent
						//              cur

						//画图
						//叔叔存在且为红
						if (uncle && uncle->_col == RED)
						{
							//变色
							parent->_col = BLACK;
							uncle->_col = BLACK;
							grandfather->_col = RED;

							//继续往上调整
							cur = grandfather;
							parent = cur->_parent;//这里曾经忘记写
						}
						//叔叔不存在或者存在且为黑
						else//(uncle==nullptr || uncle->_col == BLACK)
						{
							//左右双旋
							RotateL(parent);
							RotateR(grandfather);
							//变色
							grandfather->_col = RED;
							cur->_col = BLACK;

							//旋转后就无需再沿祖先路径检查了，具体原因画图理解
							break;
						}

					}
				}
				else//(parent == grandfather->_right)
				{
					Node* uncle = grandfather->_left;
					if (cur == parent->_right)
					{
						//          grandfather
						//                         parent
						//                                    cur

						//画图
						//叔叔存在且为红
						if (uncle && uncle->_col == RED)
						{
							//变色
							parent->_col = BLACK;
							uncle->_col = BLACK;
							grandfather->_col = RED;

							//继续沿祖先路径检查
							cur = grandfather;
							parent = cur->_parent;
						}
						//叔叔不存在或者存在且为黑
						else//(uncle==nullptr || uncle->_col == BLACK)
						{
							//单纯的右边高，进行左单旋+变色
							RotateL(grandfather);
							grandfather->_col = RED;
							parent->_col = BLACK;

							//旋转+变色后就不需要再沿祖先路径检查了
							break;
						}
					}
					else//(cur == parent->_left)
					{
						//          grandfather
						//                          parent
						//          cur

						//叔叔存在且为红
						if (uncle && uncle->_col == RED)
						{
							//变色
							parent->_col = BLACK;
							uncle->_col = BLACK;
							grandfather->_col = RED;
							
							//继续沿祖先路径检查
							cur = grandfather;
							parent = cur->_parent;
						}
						//叔叔不存在或者存在且为黑
						else//(uncle==nullptr || uncle->_col == BLACK)
						{
							//根据模型可知需要右左双旋+变色
							RotateR(parent);
							RotateL(grandfather);
							grandfather->_col = RED;
							cur->_col = BLACK;

							//旋转后就不需要再沿祖先路径检查了
							break;
						}
					}
				}
			}

			_num++;

			//最后记得把根节点的颜色改成黑色
			_root->_col = BLACK;
			return true;
		}

		size_t Size()
		{
			return _num;
		}

		bool Isbalance()
		{
			return _Isbalance(_root);
		}

		void Inorder()
		{
			_Inorder(_root);
		}

	private:

		bool CheckColour(Node* root, int blackNum, int BenchMark)
		{
			//走到空树说明这条路径已经走完了，需要检查黑色节点的个数和基准值相不相等
			if (root == nullptr)
			{
				//如果不相等，证明不平衡，返回false
				if (blackNum != BenchMark)
				{
					return false;
				}
				//如果相等，则说明本条路径没有出事，还要检查其它路径
				return true;
			}

			//如果出现连续红色节点证明这棵树出问题了，返回false
			if (root->_col == RED && root->_parent && root->_parent->_col == RED)
			{
				return false;
			}

			if (root->_col == BLACK)
			{
				blackNum++;
			}

			//递归检查所有路径的颜色
			return CheckColour(root->_left, blackNum, BenchMark)
				&& CheckColour(root->_right, blackNum, BenchMark);

		}

		bool _Isbalance(Node* root)
		{
			//空树可以认为是平衡的
			if (root == nullptr)
			{
				return true;
			}

			//根节点不是黑色说明这棵树出事了
			if (root->_col != BLACK)
			{
				return false;
			}

			//先算出一条路径的黑色节点的个数作为基准值，检查其它路径的黑色节点数目是否跟这个标准值
			//是否一样，如果不一样就证明这棵树不平衡了，那么如果这个基准值本身就是错的呢，那也没有关系，
			//只要有路径的黑色节点和其它路径不相等，就说明肯定有其中一条路径出问题了，至于是哪条路径
			//出问题就不重要了
			int BenchMark = 0;
			Node* cur = root;
			while (cur)
			{
				if (cur->_col == BLACK)
				{
					BenchMark++;
				}
				cur = cur->_left;
			}

			//检查所有路径中是否有连续红色节点和各路径中黑色节点的数目是否相等
			return CheckColour(root, 0, BenchMark);
		}

		void _Inorder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			_Inorder(root->_left);
			cout << root->_kv.second << " ";
			_Inorder(root->_right);
		}
		
		//旋转的细节如果不清楚的话请看上一篇关于AVL树的旋转，红黑树的旋转和AVL树的旋转是一样的
		void RotateL(Node* parent)
		{
			assert(parent);
			Node* cur = parent->_right;
			Node* curleft = cur->_left;
			Node* parentParent = parent->_parent;

			parent->_right = curleft;
			cur->_left = parent;
			if (curleft)
			{
				curleft->_parent = parent;
			}
			parent->_parent = cur;

			if (parent == _root)
			{
				_root = cur;
				cur->_parent = nullptr;
			}
			else
			{
				if (parent == parentParent->_left)
				{
					parentParent->_left = cur;
				}
				else
				{
					parentParent->_right = cur;
				}
				cur->_parent = parentParent;
			}

		}

		void RotateR(Node* parent)
		{
			assert(parent);
			Node* cur = parent->_left;
			Node* curright = cur->_right;
			Node* parentParent = parent->_parent;

			parent->_left = curright;
			cur->_right = parent;
			if (curright)
			{
				curright->_parent = parent;
			}
			parent->_parent = cur;

			if (parent == _root)
			{
				_root = cur;
				cur->_parent = nullptr;
			}
			else
			{
				if (parent == parentParent->_left)
				{
					parentParent->_left = cur;
				}
				else
				{
					parentParent->_right = cur;
				}

				cur->_parent = parentParent;
			}

		}

	private:
		Node* _root = nullptr;
		int _num = 0;//统计树的节点个数
	};

	void testRBTree(void)
	{
		RBTree<int, int> rbt;
		int arr[]= { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
		for (const auto& e : arr)
		{
			rbt.Insert(make_pair(e, e));
		}
		/*rbt.Inorder();*/
		cout << rbt.Size() << endl;

		bool ret = rbt.Isbalance();
		cout << ret << endl;

		cout << endl;

	}

	void testRBTree1(void)
	{
		RBTree<int, int> rbt;
		int N = 10000;
		srand((unsigned int)time(nullptr));
		for (size_t i=0;i<N;i++)
		{
			int e = rand();
			rbt.Insert(make_pair(e, e));
		}
		cout << rbt.Size() << endl;

		bool ret = rbt.Isbalance();
		cout << ret << endl;
		cout << "插入完成" << endl;

	}
}

以上就是红黑树的相关内容了，最重要的是要理解当红黑树插入元素后违反了红黑树的规则时该如何对节点进行旋转加变色来使这棵红黑树重新回到平衡的。至于删除节点的操作就不实现了，有兴趣的可以去看看《算法导论》这本书，里面有讲红黑树删除操作的。

好啦，以上就是今天想要跟大家谈的关于红黑树的最重要的内容了，你学会了吗？如果你感觉到有所帮助，那么点点小心心，点点关注呗，后期还会持续更新C++的相关知识哦，我们下期见啦！！！文章来源地址https://www.toymoban.com/news/detail-707862.html

到了这里，关于C++数据结构--红黑树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【高阶数据结构】红黑树 {概念及性质；红黑树的结构；红黑树的实现；红黑树插入操作详细解释；红黑树的验证}

    【高阶数据结构】红黑树 {概念及性质；红黑树的结构；红黑树的实现；红黑树插入操作详细解释；红黑树的验证}

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

    2024年02月09日
    浏览(48)
  • 数据结构 | 红黑树

    数据结构 | 红黑树

    节点的左边比节点的值小，右边比节点的值大。 节点要么是 红色 ，要么是 黑色 根节点 是黑色 叶子节点都是黑色的空节点 红黑树中红色节点的子节点都是黑色 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点 在添加或者删除节点的时候，如果不满足这些性质会

    2024年01月21日
    浏览(43)
  • 数据结构——红黑树

    数据结构——红黑树

    目录 概念 性质 结点的定义  插入 调整 当p是g的左孩子时 当p为g的右孩子时 插入完整代码 红黑树的检测 红黑树完整代码（包括测试数据）   红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是RED或BLACK。 通过对任何一条从根到叶子的路径

    2023年04月09日
    浏览(45)
  • 【数据结构】红黑树

    【数据结构】红黑树

    🐱作者：一只大喵咪1201 🐱专栏：《数据结构与算法》 🔥格言： 你只管努力，剩下的交给时间！ 在学习AVL树的时候，我们知道，当修改AVL树的结构(插入，删除)时，会通过旋转来保证平衡因子不超过1，所以频繁的修改结构会导致效率低下，今天我们学习的红黑树就完美解

    2023年04月17日
    浏览(48)
  • 【数据结构-树】红黑树

    【数据结构-树】红黑树

    💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(43)
  • [数据结构]-红黑树

    [数据结构]-红黑树

    前言 作者 ： 小蜗牛向前冲 名言： 我可以接受失败，但我不能接受放弃   如果觉的博主的文章还不错的话，还请 点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、红黑树的基本知识  1、红黑树的概念 2、性质  二、红黑树的模拟实

    2024年02月04日
    浏览(45)
  • 红黑树数据结构

    红黑树数据结构

    现在JAVASE中HashMap中底层源码是由数组+链表+红黑树进行设计的，然后很多地方也是用到红黑树，这里单独对红黑树数据结构进行简单的介绍。 目录 红黑树概念 红黑树的性质 自平衡规则 代码   红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可

    2024年02月01日
    浏览(39)
  • 数据结构篇十：红黑树

    数据结构篇十：红黑树

      红黑树是解决单支树问题的另一种解决方法，它相比较AVL树减少了调整的次数，AVL是一格绝对平衡的树，而红黑树只要求最长路径不超过最短路径的二倍，相比较大大减少了调整次数。在实际中更多的也是使用红黑树，就比如后面的map和set，我们就是以红黑树进行封装的

    2024年03月12日
    浏览(51)
  • 数据结构入门-11-红黑树

    数据结构入门-11-红黑树

    史上最负盛名的平衡二叉树–红黑树，但其实就是2-3树的一种实现 也是BST，每一个节点都有颜色 性质 看 后面推导出来的结论 2-3树 ：和红黑树是等价的 满足BST的基本性质，但不是一种二叉树 有两种节点： 2-3 绝对平衡：根节点到叶子节点 一定相同 2.3.1 如何维护绝对平衡

    2023年04月17日
    浏览(41)
  • 【数据结构】红黑树详解

    【数据结构】红黑树详解

    目录 前言： 红黑树的概念： 红黑树的性质: 红黑树节点的定义： 红黑树的插入： 情况1：cur为红，p为红，g为黑，u存在且为红  情况2：cur为红，p为红，g为黑，u不存在或者u为黑（p和cur都在其父亲节点同一侧） 情况3：cur为红，p为红，g为黑，u不存在或者u为黑（p和cur在其父

    2024年04月14日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包