二叉搜索树:红黑树的原理和实现

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


前言

💭上文我们在遇到问题:二叉搜索树退化到单支导致效率和性能降低时,利用了AVL树解决。但是由于AVL树是一棵绝对平衡的树,每次修改树结构都要保证左右子树高度差的绝对值不超过1,这可能会引发多次旋转。因此,若我们要设计出一棵结构动态变化的二叉搜索树,利用AVL树的效率并不高。基于这个原因,红黑树诞生了。

1. 红黑树的概念

🔴⚫
红黑树(RBTree)是一种二叉搜索树,在每个节点设置一个存储域用于指明该节点的颜色 (Red或Black),进而,通过限制任一条从根到叶子节点的路径上的各个节点的着色方式,使得任一条路径的长度都不超过另一条路径,最终达到接近平衡的树结构。

📃红黑树结构示意图:

二叉搜索树:红黑树的原理和实现
其中,NIL为空节点


2. 红黑树的性质

每一棵红黑树,都满足以下五条性质:

  1. 每个节点不是黑色就是红色
  2. 根节点为黑
  3. 对于每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点
  4. 不允许有相邻的两个红色节点
  5. 每个叶节点都为黑(此处的叶节点指NIL节点)

💡这五条性质,保证了红黑树最长路径长度不超过最短路径长度的二倍。

  • 为何要引进 NIL 节点?

保证任意节点都有两个分叉,这样才能使得红黑树接近平衡。不这样做的话,若直接以平时的叶子节点作叶节点,极端情况下,下面这棵树同样满足红黑树的性质,但是其已经退化成链表了,查找效率为O(N)。

二叉搜索树:红黑树的原理和实现

  • 如何保证最长路径长度不超过最短路径的二倍?

二叉搜索树:红黑树的原理和实现

如图所示,我们以8为根节点的红黑树为例(只关注左右两条路径,假设左路径是最短路径,右路径是最长路径,图中三角形是一些能保证整棵树为红黑树的不同情况的子树)

由性质3可得,最短路径中的黑节点必须与最长路径中的黑节点数量相同,又由性质4,最终可得最短路径节点全为黑,且与最长路径中黑节点数量相同。而最长路径中,在与最短路径拥有相同数量黑节点的前提下,穿插了红色节点,使之长度最长的方法是每个黑节点都带一个红节点。这样一来,最长路径的长度就是最短路径的二倍,此时最长路径最后一个节点为红,插入红色节点违反性质4,插入黑色节点违反性质3,因此最长路径长度不超过最短路径长度的二倍。如图中,左边路径长度为3(最短),右边路径长度为6(最长)。


3. 红黑树的定义

// 枚举:红和黑
enum COLOR 
{
	RED,
	BLACK,
};


// RBTree的节点
template <class V>
struct RBTreeNode
{
	typedef RBTreeNode<V> Self;

	V _v; // 数据域
	Self* _left;
	Self* _right;
	Self* _parent;
	COLOR _col; // 颜色域

	RBTreeNode(const V& v)
		:_v(v)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

// RBTree的大致结构
template <class V>
class RBTree
{
	typedef RBTreeNode<V> node;

public:
	RBTree()
		:_root(nullptr)
	{}
	
private:
	node* _root;
};

4. 红黑树的插入操作

💭红黑树的插入,是其区别于AVL树的最大亮点,红黑树的插入减少了一些旋转,使用变色+旋转的调整方式,提高了插入效率。

💨红黑树的插入操作可分为两步

  1. 按照二叉搜索树的规则,插入新节点

插入新节点默认为红。如果默认为黑,则必定违反性质3,需要做的调整更多。而默认为红,有可能会违反性质4,需要做出调整,也可能不违反任何性质,无需调整。因而选择第二种方案,减少插入时的调整次数,提高效率。

template <class V>
class RBTree
{
	typedef RBTreeNode<V> node;
public:
	//...
	bool insert(const V& v)
	{
		if (_root == nullptr)
		{
			_root = new node(v);
			_root->_col = BLACK;
			return true;
		}

		//插入
		node* cur = _root;
		node* parent = nullptr;

		while (cur)
		{
			if (v < cur->_v)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (v > cur->_v)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}

		cur = new node(v);

		if (cur->_v < parent->_v)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		// ...
	}
	
private
	node* _root;
};
  1. 检查插入后是否破坏了红黑树结构,若是则需进行调整

💭因为新节点的默认颜色是红色,所以:

  1. 如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;
  2. 如果新插入节点的双亲节点颜色为红色时,就违反了性质3不允许有相邻的两个红色节点,此时需要对红黑树分情况来讨论,不同情况有不同调整方法:

约定:二叉搜索树:红黑树的原理和实现

需要调整时,cur为红,p为红,g为黑(否则调整前p、g就已经破坏了红黑树的规则)。因此我们重点看uncle节点的情况,uncle节点的存在与否、着色状态决定了该如何调整。



1️⃣情况1:uncle节点存在且为红

注意,此时看到的树可能是某棵子树,也有可能是整棵树。
二叉搜索树:红黑树的原理和实现

  • 📝调整方法:p,u变黑,g变红。这样做不仅解决了相邻两个红节点的问题,还使得以g为根到任意叶子节点的每条路径的黑节点数量不变。但是要注意g还需继续向上调整。

为什么g还需要向上继续调整?

  • 当这棵树是某棵子树时,g一定还有双亲节点,若g的双亲节点为红色,则需要继续向上调整。
  • 当这棵树是整颗树时,g是根节点,则需要修改g的颜色为黑,否则会破坏性质2(根节点为黑)。
  • 🔎综上所述,cur可以是新插入节点,也可以是由a、b子树插入节点调整(情况1)后变成红色。 若cur为新插入的节点,易得a、b为空树。此时c、d、e皆为空树,否则插入前的树并不是红黑树。若cur是调整后得来的红节点,则各个子树又有不同情况。总而言之,插入新节点前该树必须满足红黑树的性质。

二叉搜索树:红黑树的原理和实现

  • 因为情况1并不涉及旋转,不会调整树的物理结构,所以调整方法与cur的插入位置无关,只要满足条件即可。下面四种情况均属于情况1的调整。

二叉搜索树:红黑树的原理和实现




2️⃣情况2:uncle节点不存在/存在且为黑

  1. uncle不存在。cur只能是新插入节点的情况(不能是由子树调整而来变红)。abcde子树均不存在,否则插入之前不满足红黑树的性质。
    二叉搜索树:红黑树的原理和实现

  2. uncle存在且为黑。cur只能是由子树调整而来变红 (即情况1变化而来) 的情况(不能是新插入节点),否则调整前不满足红黑树的性质。

二叉搜索树:红黑树的原理和实现

假设cur为新插入节点,则插入前树结构如图所示(暂且不考虑NIL节点),违反性质3。
二叉搜索树:红黑树的原理和实现

(1)(2)的调整方法都是一样的。不同于情况1,情况二无法单凭节点的变色完成调整,而是要借助旋转+变色。旋转方式与AVL树的旋转大同小异。

  1. 左左——右单旋
    二叉搜索树:红黑树的原理和实现

  2. 右右——左单旋
    二叉搜索树:红黑树的原理和实现

  3. 左右——左右双旋二叉搜索树:红黑树的原理和实现

  4. 右左——右左双旋
    二叉搜索树:红黑树的原理和实现

💬代码实现

template <class V>
class RBTree
{
	typedef RBTreeNode<V> node;

public:
	//...
	bool insert(const V& v)
	{
		if (_root == nullptr)
		{
			_root = new node(v);
			_root->_col = BLACK;
			return true;
		}

		//插入
		node* cur = _root;
		node* parent = nullptr;

		while (cur)
		{
			if (v < cur->_v)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (v > cur->_v)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}

		cur = new node(v);

		if (cur->_v < parent->_v)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		// 调整
		
		node* grandfather = nullptr, *uncle = nullptr;

		while (parent && parent->_col == RED) // parent存在且为红色时需继续向上调整
		{
			grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				uncle = grandfather->_right;
			}
			else
			{
				uncle = grandfather->_left;
			}

			//情况1:u存在且为红
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续向上更新
				cur = grandfather;
				parent = cur->_parent;
			}

			//情况2:u不存在/u存在且为黑
			else
			{
				if (cur == parent->_left && parent == grandfather->_left)
				{
					// 左左——右单旋
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else if (cur == parent->_right && parent == grandfather->_right)
				{
					// 右右——左单旋
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else if (cur == parent->_right && parent == grandfather->_left)
				{
					// 左右——左右双旋
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				else if (cur == parent->_left && parent == grandfather->_right)
				{
					// 右左——右左双旋
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				// 经过情况2调整后,子树根节点必为黑,因此直接结束更新
				break;
			}
		}
		// 最后写定根节点为黑色
		_root->_col = BLACK;

		return true;
	}
	
private:
	// 右单旋
	void RotateR(node* pParent)
	{
		node* subL = pParent->_left;
		node* subLR = subL->_right;
		node* ppParent = pParent->_parent;

		//1.pParent(父)和subLR(子)
		pParent->_left = subLR;
		if (subLR)
			subLR->_parent = pParent;

		//2.subL(父)和pParent(子)
		subL->_right = pParent;
		pParent->_parent = subL;

		//3.ppParent(父)和subL(子)
		if (pParent == _root)
		{
			_root = subL;
		}
		else
		{
			if (ppParent->_left == pParent)
			{
				ppParent->_left = subL;
			}
			else
			{
				ppParent->_right = subL;
			}
		}
		subL->_parent = ppParent;
	}

	// 左单旋
	void RotateL(node* pParent)
	{
		node* subR = pParent->_right;
		node* subRL = subR->_left;
		node* ppParent = pParent->_parent;

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

		subR->_left = pParent;
		pParent->_parent = subR;

		if (pParent == _root)
		{
			_root = subR;
		}
		else
		{
			if (ppParent->_left == pParent)
			{
				ppParent->_left = subR;
			}
			else
			{
				ppParent->_right = subR;
			}
		}
		subR->_parent = ppParent;
	}

	node* _root;
};

5. 红黑树的验证

💭验证一棵树是否为红黑树,不能像AVL树一样简单粗暴地判断左右子树高度差的绝对值是否小于1,因为红黑树只是接近平衡。红黑树的验证需要验证其五条性质是否都成立

⭕红黑树的性质

  1. 每个节点不是黑色就是红色
  2. 根节点为黑
  3. 对于每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点
  4. 不允许有相邻的两个红色节点
  5. 每个叶节点都为黑(此处的叶节点指NIL节点)

性质1和性质5无需验证,通过代码就已经保证了。我们需要验证性质2、3、4。

💡思路:

  • 验证性质2:直接判断即可
  • 验证性质3:先选取任一路径(一般旋转最左或最右路径),计算其黑节点数量,作为参考值,然后再用每一条路径的黑节点数量与参考值比较,只要有一条路径上的黑节点数量与参考值不相等,则不满足红黑树旋转3。
  • 验证性质4:判断当前节点与其parent节点是否同时为红即可。(parent节点必存在,孩子节点不一定存在且情况多,所以选取parent与当前节点比较)。

💬代码实现

class RBTree
{
	typedef RBTreeNode<V> node;
public:
	//...
	bool IsRBTree()
	{
		if (_root == nullptr)
		{
			return true;
		}
		
		// 判断性质2
		if (_root->_col == RED)
		{
			cout << "违反性质2:根节点为黑" << endl;
			return false;
		}

		// 求任意一条路径上的黑色节点数量,让其他路径上的与之对比
		// 选取最左路径
		node* left = _root;
		int ref = 0;
		while (left)
		{
			if (left->_col == BLACK)
			{
				ref++;
			}
			left = left->_left;
		}
		// NIL节点也是黑色
		ref++;

		// 检查左右子树,需要传入路径到达当前节点的黑节点的数量
		return check(_root->_left, 1, ref) && check(_root->_right, 1, ref);
	}
	
private:

	bool check(node* cur, int prevBlackCount, const int& refBlackCount)
	{
		if (cur == nullptr)
		{
			// 当前路径到达终点
			// 黑色节点个数与参照值比较

			// 加上NIL节点
			prevBlackCount++;

			if (prevBlackCount != refBlackCount)
			{
				cout << "违反性质3:每条路径的黑节点数量应相同" << endl;
				return false;
			}
			else
			{
				return true;
			}
		}

		// 判断性质4
		if (cur->_col == RED && cur->_parent->_col == RED)
		{
			cout << "违反性质4:不允许有相邻的两个红节点" << endl;
			return false;
		}
		
		// 计算路径到达当前节点的黑节点的数量
		int curBlackCount = cur->_col == BLACK ? prevBlackCount + 1 : prevBlackCount;

		return check(cur->_left, curBlackCount, refBlackCount)
			&& check(cur->_right, curBlackCount, refBlackCount);
	}
	
	node* _root;
};

💬 测试函数

void testRBTree()
{
	RBTree<int> rbt;
	
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		rbt.insert(a[i]);
	}

	if (rbt.IsRBTree())
	{
		cout << "The tree is a RBTree!!!" << endl;
	}
}

📃 简易的递归图
二叉搜索树:红黑树的原理和实现

二叉搜索树:红黑树的原理和实现


6. 红黑树和AVL树的比较

💭红黑树和AVL树都是常见的自平衡二叉搜索树,它们都能够保证树的高度不会过高,从而保证了树的查询、插入和删除操作的时间复杂度都是O(logN)。但是它们之间有一些不同点。

上面提到,红黑树是近似平衡,而AVL树是绝对平衡,因此,红黑树的查找效率低于AVL树。那么这对使用红黑树的影响大吗?那么需要探讨一下近似平衡的概念。

  • 近似平衡
    红黑树通过对从根到叶子节点的任一条路径上各个节点的着色方式的限制,以达到近似平衡的效果,即最长路径长度不超过最短路径的二倍。近似平衡,通俗理解,在效率方面,越接近平衡越优,越不平衡越差,若要得到其查找的时间复杂度,就要分近似平衡的最优情况和最差情况讨论。
  1. 最优情况:每条路径都是全黑,或者每条路径都是一红一黑相间。此时的红黑树是满二叉树,即最平衡的情况,查找的时间复杂度为O(logN)
    二叉搜索树:红黑树的原理和实现

  2. 最差情况:每个节点的往左右的两条路径,一条全黑,一条一红一黑相间,此时左右两条路径有一条是另一条的两倍,这种情况下为最差情况。抽象示意图如下:

二叉搜索树:红黑树的原理和实现

⭕分析:

设全黑路径长度(即最短路径长度):h

  • 极端情况下,当N黑很大时,N红相对于N黑很小,可忽略不计

    N = N黑 + N红

    N = N黑

  • 此时只考虑黑色节点,可以想象成将红色节点都往最底部挪,那么上层是一个由黑色节点组成的满二叉树

    故:N黑 = N = 2^h-1

    h = logN

因为:全黑路径长度 = 最短路径长度 = h
所以:最长路径长度 = 2×最短路径长度 = 2h = 2logN

🔎红黑树最差情况的查找,就是去找最长路径的最后一个节点,综上推论,大概要找2logN次。而在AVL树中,由于绝对平衡的结构,查找一个节点只需找logN次

  • 给一个很大的数,比方说10亿。那么,在一棵10亿节点的AVL树中,查找的最坏情况是找30次(log10亿)。而在一棵10亿节点的红黑树中,查找的最坏情况是找60次(2*log10亿)。可见,红黑树的查找效率略低于AVL树,但是二者是同一个量级的,对于计算机来说,这点差别不算什么。所以这点效率区别对红黑树的使用影响并不大。

  • 对于树的插入和删除。AVL树在插入或删除节点时,可能会需要更多地通过旋转操作来保持树的平衡,而旋转操作可能会导致更多的旋转,从而导致插入和删除操作的时间复杂度可能会比红黑树更高。而红黑树通过着色和旋转操作来保持平衡,旋转次数比AVL树少。因此红黑树插入和删除操作的效率可能会更高。

💡得出结论:如果需要频繁进行插入和删除操作,且对查询效率要求不是特别高,可以选择红黑树;如果对查询效率有比较高的要求,且能够容忍插入和删除操作的效率稍低,可以选择AVL树。实际应用中,红黑树用的更多。


7. 红黑树的应用

  1. C++ STL库 – map/set、mutil_map/mutil_set
  2. Java 库
  3. linux内核
  4. 其他一些库

💭下一篇文章将带你了解map和set,并分析如何用红黑树实现它们。


完。文章来源地址https://www.toymoban.com/news/detail-429016.html

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

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

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

相关文章

  • 【C++】红黑树的原理与实现

      文章目录 一、引言 二、红黑树的概念与性质 2、1 红黑树的概念 2、2 红黑树的性质 三、红黑树的定义与实现 3、1 红黑树的定义 3、2 插入新节点 3、2、1 默认插入红色节点 3、3 插入情况分类 3、3、1 情况一(根据颜色向上调整) 3、3、2 情况二(单次旋转+变色) 3、3、3 情

    2024年02月13日
    浏览(43)
  • 【高阶数据结构】红黑树 {概念及性质;红黑树的结构;红黑树的实现;红黑树插入操作详细解释;红黑树的验证}

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

    2024年02月09日
    浏览(46)
  • 红黑树的概念与实现

    目录 ​一、红黑树的概念 1.什么是红黑树 2.红黑树满足的性质 3.红黑树存在的意义 二、红黑树的实现 1.类的构建 2.插入函数 (1)插入一个节点 (2)调整节点 (3)旋转 三、红黑树的检验 红黑树是一种二叉搜索树,每个结点增加一个变量表示结点的颜色,颜色只能是Red或

    2024年02月02日
    浏览(36)
  • 【C++】红黑树的模拟实现

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

    2024年02月08日
    浏览(46)
  • 红黑树的了解以及代码实现

            红黑树是在二叉搜索树的基础上 添加颜色 , 通过对任何一条路径的颜色的限制,确保红黑树的任何一条路径不会超过其他路径的两倍 ,是一棵近似平衡的树。         红黑树的节点不是红色就是黑色,其节点的排列除了需要按二插搜索树的规则来插入之外,还

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

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

    2024年02月09日
    浏览(43)
  • 数据结构与算法(三):树论(树形结构、二叉树、二叉搜索树、红黑树、Btree&B+Tree、赫夫曼树、堆树)

    树论(树形结构、二叉树、二叉搜索树、红黑树、Btree、B+Tree、赫夫曼树、堆树) 在树形结构里面重要的术语: 结点:树里面的元素。 父子关系:结点之间相连的边 子树:当结点大于1时,其余的结点分为的互不相交的集合称为子树 度:一个结点拥有的子树数量称为结点的

    2024年02月01日
    浏览(93)
  • Java 数据结构篇-实现红黑树的核心方法

      🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍      文章目录         1.0 红黑树的说明         2.0 红黑树的特性         3.0 红黑树的成员变量及其构造方法         4.0 实现红黑树的核心方法         4.1 红黑树内部类的核心方法         (1)判

    2024年01月24日
    浏览(43)
  • 【C++】二叉搜索树的原理及实现

      二叉搜索树(Binary Search Tree,BST)是一种常用的数据结构,本文将介绍二叉搜索树的原理与特性,并给出C++代码实现,最后对其性能进行详细的分析。    文章目录 简介 一、二叉搜索树的概念 二、二叉搜索树的操作及实现 2、1 二叉搜索树的插入 2、1、1 插入的原理 2、1、2

    2024年02月14日
    浏览(48)
  • 【C++】AVL(平衡二叉搜索树)树的原理及实现

    文章目录 一、引言 二、AVL树的概念 三、AVL树的插入 3、1 AVL树的简单插入 3、2 旋转分类  3、2、1 新节点插入较高右子树的右侧:左单旋 3、2、2 新节点插入较高左子树的左侧:右单旋 3、2、3 新节点插入较高左子树的右侧:左右双旋(先左后右) 3、2、4 新节点插入较高右

    2024年02月13日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包