【C++】详解红黑树并模拟实现

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

前言:

       上篇文章我们一起学习了AVL树比模拟实现,我们发现AVL树成功地把时间复杂度降低到了O(logN)。但是同时我们不难发现一个问题,在构建AVL树中我们也付出了不小的代价,频繁的旋转操作导致效率变低。为了解决这个问题,我们本章将迎来更为实用的红黑树,他在提高查找效率的同时也相对AVL树提高了构建树的效率,他的应用将更加广泛(比如map、set的底层实现就是红黑树)!

目录

(一)红黑树的概念

1、概念

2、特性

(二)红黑树的模拟实现

1、结点的定义

2、结点的查找实现(Find)

3、结点的插入实现(Insert)*重点

3.1前序问题

3.2具体流程

情况一:叔叔存在且为红——变色处理

情况二:叔叔不存在or叔叔存在且为黑——旋转+变色

 情况三:叔叔不存在or叔叔存在且为黑——双旋+变色(区别于情况二)

4、具体代码(Find+Insert)

(三)验证红黑树

1、中序遍历

2、验证红黑树几大特性

3、测试用例

(四)项目完整代码


(一)红黑树的概念

1、概念

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black,所以叫红黑树

通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

【C++】详解红黑树并模拟实现,c++,数据结构

2、特性

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

思考:

为什么满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点
个数的两倍?
这里我们从路径最短的情况和最长的情况分析:
我们假设该红黑树每条路径黑色结点数是3
路径最短的情况:
这条路径没有红色结点,如下图:

【C++】详解红黑树并模拟实现,c++,数据结构

路径最长的情况:
这条路径一个黑色节点接着一个红色节点,交相出现:
                                 

【C++】详解红黑树并模拟实现,c++,数据结构

这时我们发现最短路径时,一条路径上有三个结点(情况一);最长路径时,一条路径上有五个节点(情况二)。所以可以保证其最长路径中节点个数不会超过最短路径节点个数的两倍。

(二)红黑树的模拟实现

1、结点的定义

我们还是沿用AVL树节点的三叉链定义方法,颜色我们用枚举来实现:

【C++】详解红黑树并模拟实现,c++,数据结构

ps:这里一开始结点定义为红色的原因,我们在后文插入的时候会详细讲解。

2、结点的查找实现(Find)

在红黑树中的Find(查找)操作和之前二叉搜索树和AVL树实现方法一样,这里我们简单带过。

结点存的值比当前结点小就向左找,比当前结点大就向右找,最后遇到空节点表示没找到。

【C++】详解红黑树并模拟实现,c++,数据结构

3、结点的插入实现(Insert)*重点

3.1前序问题

首先,我们解答上面留下的那个问题,

为什么新插入的结点要默认给红色的?

  • 假设我们默认给新增的结点黑色,那么一定违反上面红黑树的特性4(对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点 )。这样我们还要对其他路径进行修改黑色结点的数量。
  • 但是如果默认给红色,我们则是可能违反特性3(如果一个节点是红色的,则它的两个孩子结点是黑色的 )。为什么说是可能,因为如果他的父亲节点是黑色则不违反。就算违反了。每条路径黑色结点的数量还是一样的,我们只需要调整所在的那一条路径即可,代价相对小了许多。

3.2具体流程

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

(分别对应parent,grandfather,uncle的意思)

插入几大流程:

  • 按照搜索二叉树的查找方法,找到要插入的位置
  • 将新增结点插入到待插入位置
  • 如果需要调整则调整红黑树

其中需不需要调整主要是看叔叔颜色的情况。

下面具体分析:

我们先给出一个基本的图示

【C++】详解红黑树并模拟实现,c++,数据结构

这里的三角形就相当于AVL树中的小长方形,代表了一部分子树。

情况一:叔叔存在且为红——变色处理
  • cur为红,p为红,g为黑, u存在且为红

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

首先我们知道,红黑树调整主要看叔叔,第一步我们将父亲变成黑色,为了维护性质4,我们也要将叔叔的颜色变成黑色,同时也要将祖父结点的颜色变成红色,因为我们此时处理的不一定是整棵树,有可能是某个子树,如果此时不是子树,就需要将根节点变成黑色。这样我们就在局部调整颜色并保证了不破坏规则。

 【C++】详解红黑树并模拟实现,c++,数据结构

调整的部分可能是一整棵树,也可能是某一棵子树

  • 如果g是根节点,调整完成后,需要将g改为黑色
  • 如果g是子树,g一定有双亲,且g的双亲如果是红色,需要继续向上调整

 【C++】详解红黑树并模拟实现,c++,数据结构

情况一的情景下,我们只关心颜色的调整就可以在不破坏规则的情况下插入结点!


情况二:叔叔不存在or叔叔存在且为黑——旋转+变色

【C++】详解红黑树并模拟实现,c++,数据结构

情况二可能就是从情况一调整变化得到的情况。

具体情况 1

当叔叔不存在时:

【C++】详解红黑树并模拟实现,c++,数据结构

我们调整颜色总会破坏规则,此时结合上面长路径不会超过短路径二倍的特性我们分析,英爱使用到了和AVL树相似的旋转处理。

【C++】详解红黑树并模拟实现,c++,数据结构

  • 此时是左边高了,我们对图示树进行右单旋,这里的旋转和AVL树中旋转的方式如出一辙,可以拿过来直接复用。
  • 同样的道理,如果是右边高了,我们就可以进行左单旋,旋转的方法也和AVL树中的如出一辙,也可拿过来直接复用。(这里我们就不像AVL树那样详细解释了,实现方法是一样的,如果读者不太了解可以看上一篇文章)

 具体情况 2

当叔叔存在且为黑时:

按照上文说明,这种情况必定是由情况一变化而来的。

此时也是旋转+变色

【C++】详解红黑树并模拟实现,c++,数据结构

这样子才能保护好红黑树的结构。


 情况三:叔叔不存在or叔叔存在且为黑——双旋+变色(区别于情况二)

同样是 叔叔不存在 or 叔叔存在且为黑,为啥分为情况二和情况三呢?

上述旋转的情况都是单边的情况,也就是说,cur、p、g在一条线上的情况,若是出现了这三者不在一条直线的时候,单旋就解决不了问题了。

区别:

  • p是g的左,cur是p的左,那么是情况二 —— 单旋
  • p是g的左,cur是p的右,那么是情况三 —— 双旋

此时我们就引入了双旋

(这里我们可以结合上一篇AVL树来区别单旋和双旋)

【C++】详解红黑树并模拟实现,c++,数据结构

  • 先以p为旋转点再以g为旋转点
  • 先变到情况二的样子
  • 再根据情况二来继续变

其实看完情况二和三有些人就会有疑问了,看上去每条路径上黑色结点树不一样啊,为什么要这样旋转变色?

再此之前我们推测过当叔叔存在且为黑时,一定是由情况一变来的,所以cur一开始是黑的,这个树并不违反性质,子树由情况一变化之后的子树结点的颜色也相应变化了,只是没有显示出来而已。

4、具体代码(Find+Insert)

Node* Find(const K& key)
	{
		Node* cur = _root;

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

		return nullptr;
	}


	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;


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

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

		//调整颜色
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)//u存在且为红
			{
				Node* uncle = grandfather->_right;

				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
			

			else//u不存在或者为黑,旋转加变色
			{
				if (cur == parent->_left)
				{
					//    g
					//  p   u
					//c

					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}

				else
				{
					//     g
					//   p   u
					//     c

					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}

		else//grandfather->_right == parent
		{
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == RED)
			{
				//     g
				//  u    p
				//          c
				uncle->_col = BLACK;
				parent->_col = BLACK;
				grandfather->_col = RED;

				cur = grandfather;
				parent = cur->_parent;
			}

			else// :u不存在/u存在且为黑,旋转+变色
			{
				if (cur == parent->_right)
				{
					//     g
					//  u    p
					//          c
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;

				}
				else
				{
					//      g
					//   u     p
                    //      c
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}


		}

		_root->_col = BLACK;
		return true;
    }

(三)验证红黑树

老样子,我们在上一章模拟实现AVL树后用了几个函数来验证我们构建的树是否是AVL树,这里我们也要验证一下我们构建的这棵树是否是红黑树。

几个验证要点:

  • 这棵树是否是二叉搜索树
  • 根结点是否是黑色结点
  • 红色结点的子结点是否是黑色结点
  • 每条路径黑色结点树是否一样

满足这几个要点,也就是红黑树的特性,那么这棵树1就是红黑树了。

1、中序遍历

一棵树是红黑树的前提就是他必须是二叉搜索树,二叉搜索树的特点就是中序遍历是有序的。

void InOrder()
	{
		return _InOrder(_root);
	}


void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}

ps:为了符合用户的使用习惯,我们还是采取嵌套的方式,大家不明白的可以看一下上一篇文章验证处有说明哦!

2、验证红黑树几大特性

相对AVL树,验证红黑树是更加麻烦的,几个要点:

  • 首先判断根结点是否是黑色
  • 判断每条路径黑色结点数我们思路是先取一条路径黑色结点数量为基准值,然后递归统计其他路径的数目,遇到空结点再比较
  • 遇到红色结点我们如果判断他的孩子结点是否是黑色,如果是要跳过(代码不好写),不如换个思路,遇到一个红色结点就判断双亲是否是红色,如果是(存在连续红色结点)返回false。
bool IsBalance()
	{
		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 _Check(_root, 0, benchmark);
	}


private:
	bool _Check(Node* root, int blackNum, int benchmark)
	{
		if (root == nullptr)
		{
			if (benchmark != blackNum)
			{
				cout << "某条路径黑色节点的数量不相等" << endl;
				return false;
			}

			return true;
		}

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

		if (root->_col == RED
			&& root->_parent
			&& root->_parent->_col == RED)
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		return _Check(root->_left, blackNum, benchmark)
			&& _Check(root->_right, blackNum, benchmark);
	}

通过递归的方式将每条支路都走了一遍和基准值比较,并且将红黑树的性质全都验证了。

3、测试用例


void Test_RBTree1()
{
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	RBTree<int, int> t1;
	for (auto e : a)
	{
		/*	if (e == 14)
		{
		int x = 0;
		}*/

		t1.Insert(make_pair(e, e));
		//cout << e << "插入:" << t1.IsBalance() << endl;
	}

	t1.InOrder();
	cout << endl;
	cout << t1.IsBalance() << endl;
}


void Test_RBTree2()
{
	srand(time(0));
	const size_t N = 5000000;
	RBTree<int, int> t;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand() + i;
		t.Insert(make_pair(x, x));
		//cout << t.IsBalance() << endl;
	}

	//t.Inorder();

	cout << t.IsBalance() << endl;
	cout << t.Height() << endl;
}

精检验,没有问题:

【C++】详解红黑树并模拟实现,c++,数据结构

(四)项目完整代码

#pragma once
#include<iostream>
#include<assert.h>

using namespace std;

enum Colour
{
	RED,
	BLACK,
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;


	RBTreeNode(const pair<K,V>& kv)
		:
	    _left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_kv(kv),
		_col(RED)
	{}
};


template<class K,class V>
struct RBTree
{
	typedef RBTreeNode<K, V> Node;
	void Destroy(Node* root)
	{
		_Destroy(root);
		root = nullptr;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;

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

		return nullptr;
	}


	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;


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

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

		//调整颜色
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)//u存在且为红
			{
				Node* uncle = grandfather->_right;

				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
			

			else//u不存在或者为黑,旋转加变色
			{
				if (cur == parent->_left)
				{
					//    g
					//  p   u
					//c

					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}

				else
				{
					//     g
					//   p   u
					//     c

					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}

		else//grandfather->_right == parent
		{
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == RED)
			{
				//     g
				//  u    p
				//          c
				uncle->_col = BLACK;
				parent->_col = BLACK;
				grandfather->_col = RED;

				cur = grandfather;
				parent = cur->_parent;
			}

			else// :u不存在/u存在且为黑,旋转+变色
			{
				if (cur == parent->_right)
				{
					//     g
					//  u    p
					//          c
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;

				}
				else
				{
					//      g
					//   u     p
                    //      c
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}


		}

		_root->_col = BLACK;
		return true;
    }


	void InOrder()
	{
		return _InOrder(_root);
	}

	int Height()
	{
		return _Height(_root);
	}

	bool IsBalance()
	{
		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 _Check(_root, 0, benchmark);
	}


private:
	bool _Check(Node* root, int blackNum, int benchmark)
	{
		if (root == nullptr)
		{
			if (benchmark != blackNum)
			{
				cout << "某条路径黑色节点的数量不相等" << endl;
				return false;
			}

			return true;
		}

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

		if (root->_col == RED
			&& root->_parent
			&& root->_parent->_col == RED)
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		return _Check(root->_left, blackNum, benchmark)
			&& _Check(root->_right, blackNum, benchmark);
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}

	int _Height(Node* root)
	{
		if(root==nullptr)
		{
			return 0;
		}
		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);

		return leftH > rightH ? leftH + 1 : rightH + 1;
	}
	
	void _Destroy(Node* root)
	{
		if (root == nullptr)
			return;

		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}


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

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

		Node* ppnode = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;

		if (ppnode == nullptr)
		{
			_root = subR;
			_root->_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 (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
	}
private:
	Node* _root=nullptr;
};


void Test_RBTree1()
{
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	RBTree<int, int> t1;
	for (auto e : a)
	{
		/*	if (e == 14)
		{
		int x = 0;
		}*/

		t1.Insert(make_pair(e, e));
		//cout << e << "插入:" << t1.IsBalance() << endl;
	}

	t1.InOrder();
	cout << endl;
	cout << t1.IsBalance() << endl;
}


void Test_RBTree2()
{
	srand(time(0));
	const size_t N = 5000000;
	RBTree<int, int> t;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand() + i;
		t.Insert(make_pair(x, x));
		//cout << t.IsBalance() << endl;
	}

	//t.Inorder();

	cout << t.IsBalance() << endl;
	cout << t.Height() << endl;
}

祝您学业有成!文章来源地址https://www.toymoban.com/news/detail-701528.html

到了这里,关于【C++】详解红黑树并模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

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

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

    2024年02月09日
    浏览(49)
  • 【C++】红黑树的概念与模拟实现

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

    2024年02月09日
    浏览(43)
  • 【C++】详解AVL树并模拟实现

      前言:   之前我们为了让数据存储效率提高,引进了二叉搜索树。   但是我们发现,二叉搜索树的时间复杂度还是O(N),因为二叉搜索树并不是非常的平衡。   并不是所有树都是满二叉树,可能出现单边书这样极端的情况,所以我们引进了查找效率更高的 AVL树 。 目录 (一

    2024年02月09日
    浏览(59)
  • 数据结构--红黑树详解

    红黑树(Red Black Tree)是一种自平衡二叉查找树。它是在 1972 年由 Rudolf Bayer 发明的,当时被称为平衡二叉 B 树(symmetric binary B-trees)。后来,在 1978 年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 由于其自平衡的特性,保证了最坏情形下在 O(logn) 时间复杂度内完

    2024年02月22日
    浏览(46)
  • 数据结构——红黑树详解

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

    2024年04月13日
    浏览(40)
  • 【数据结构】红黑树详解

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

    2024年04月14日
    浏览(54)
  • [数据结构 - C++] 红黑树RBTree

    我们在学习了二叉搜索树后,在它的基础上又学习了AVL树,知道了AVL树是靠平衡因子来调节左右高度差,从而让树变得平衡的。本篇我们再来学习一个依靠另一种平衡规则来控制的二叉搜索树——红黑树。 红黑树 ,是一种 二叉搜索树 , 但在每个结点上增加一个存储位表示

    2024年01月23日
    浏览(46)
  • 数据结构:红黑树讲解(C++)

    本文旨在 理解红黑树基本概念以及变色旋转规则 ,以理解C++ map 和 set 的底层原理,不会讲红黑树的删除操作。 对于基本的旋转操作(单旋和双旋),本文不会展开讲,详细讲解在这里: AVL树旋转讲解。 2.1概念 红黑树,是一种二叉搜索树,但在每个结点上 增加一个存储位表示

    2024年02月05日
    浏览(43)
  • 【高阶数据结构】红黑树详解

    这篇文章我们再来学习一种平衡搜索二叉树—— 红黑树 红黑树和AVL树都是常见的自平衡二叉搜索树,它们都可以用于高效地支持插入、删除和查找等操作。虽然它们都能够保持树的平衡性,但在不同的应用场景下,红黑树和AVL树有各自的优势和适用性。 红黑树(Red-Black Tr

    2024年02月12日
    浏览(40)
  • 【C++】红黑树模拟实现插入功能(包含旋转和变色)

    本篇主要讲解红黑树的模拟实现,实现之后再封装成map和set。 红黑树中所用到的旋转功能均源自我的上一篇博客,本篇中不会再详谈旋转,若对于旋转不了解的同学可以先看看上一篇博客:【C++】AVL树模拟实现插入功能 前一篇的AVL树,是严格平衡的一棵二叉搜索树,也就是

    2024年02月13日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包