红黑树——原理刨析

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

        众所周知,红黑树是从AVLTree树中衍变而来的,所以在学红黑树之前还是要好好的理解一下AVLTree树的原理,为理解红黑树减轻理解负担,好了进入正题。

红黑树原理:

        由名可知,红黑树——肯定是与颜色有关的一个树,又因为是从AVLTree树中衍化过来的,所以也是搜索树(不是平衡二叉树,后面讲解定义时会详细解释),通过对不同情况的处理,去调整红黑树节点的颜色或者红黑树的高度去使其满足,红黑树的定义规则。

红黑树的定义:

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

红黑树——原理刨析,树,C++,数据结构,数据结构,c++

如上图,就是红黑树。

红黑树的性质:

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

思考:为什么满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍?

答:上述红黑树的性质第4条 说明每条路上面的黑色节点数量都是相等的,所以说该节点的左右子树可以有一棵子树全为黑色节点 另一个红黑节点交替(红节点数量与黑节点数量相等),这就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍。

红黑树中重要的函数讲解:

        和AVLTree一样,插入函数是难点,但是掌握AVLTree之后,这里的插入就不怎么难了,AVLTree中提到左旋,右旋,这里不做讲解,如有疑惑,参考上篇文章,有流程图

        在我看来红黑树与AVLTree不同点就是规则不同,红黑树是靠颜色去调整高度差,而AVLTree是通过平衡因子去调节的。

红黑树——原理刨析,树,C++,数据结构,数据结构,c++

红黑树——原理刨析,树,C++,数据结构,数据结构,c++

红黑树——原理刨析,树,C++,数据结构,数据结构,c++

情况一:整棵树或者子树为上上图,就只能进行颜色更新 将uncle更新为黑色 父亲更新为黑色 祖父更新为红色 再继续向上以同样的方式更新 直到更新到根节点或者进行了一次旋转调整 (旋转调整会将树的高度改变并将颜色确定为最终的颜色)就不再向上更新

红黑树——原理刨析,树,C++,数据结构,数据结构,c++

情况二:uncle存在且为黑或者不存在

红黑树——原理刨析,树,C++,数据结构,数据结构,c++

红黑树——原理刨析,树,C++,数据结构,数据结构,c++

1,先进行情况一的颜色更新,出现了旋转的情况,再进行旋转 最后进行旋转的颜色更新

红黑树——原理刨析,树,C++,数据结构,数据结构,c++

               

        2,刚开始整棵树就为要旋转的情况或者为整棵树的子树,如上图

单选和双旋在AVLTree中已经讲解过了,这里最重要的就是如何进行颜色更新,而不是旋转。

        

红黑树完整代码:文章来源地址https://www.toymoban.com/news/detail-745630.html

#pragma once
#include<iostream>
using namespace std;

enum color
{
	BLACK,
	RED
};

template<class K,class V>
struct RBTreeNode
{

	RBTreeNode<K, V>* _parent;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	pair<K, V> _kv;
	color _col;

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

	}
};

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
private:
	Node* _root = nullptr;

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 (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);
		cur->_col = RED;
		if (parent->_kv.first < cur->_kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfater = parent->_parent;
			assert(grandfater);

			//祖父颜色不为黑 说明红黑树在插入之前就是不平衡的
			assert(grandfater->_col == BLACK);
			if (parent == grandfater->_left)
			{
				Node* uncle = grandfater->_right;
				if (uncle && uncle->_col == RED)
				{
					grandfater->_col = RED;
					parent->_col = uncle->_col = BLACK;

					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
					if (parent->_left == cur)
					{
						//    g
						//  p   u
						//c
						RotateR(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}
					else
					{
						//    g
						//  p   u
						//    c
						RotateL(parent);
						RotateR(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfater->_left;
				if (uncle && uncle->_col == RED)
				{
					grandfater->_col = RED;
					parent->_col = uncle->_col = BLACK;

					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
					if (parent->_right == cur)
					{
						//    g
						//  u   p
						//        c
						RotateL(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}
					else
					{
						//    g
						//  u   p
						//     c
						RotateR(parent);
						RotateL(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}
	void Inorder()
	{
		_Inorder(_root);
	}
	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return false;
		}
		if (_root->_col == RED)
		{
			cout << "根节点为红色,不是红黑树" << endl;
			return false;
		}
		int benchmark = 0;
		return PrevCheck(_root, 0, benchmark);
	}
	private:
		bool PrevCheck(Node* root, int blackNum, int& benchmark)
		{
			if (root == nullptr)
			{
				if (benchmark == 0)
				{
					blackNum = benchmark;
					return true;//第一次遍历到空 没有比较意义 将第一次的黑色节点作为参考去判断
				}
				if (blackNum != benchmark)
				{
					cout << "红黑树各路黑色节点数量不相同" << endl;
					return false;
				}
				else
				{
					return true;
				}
			}
			if (root->_col == BLACK)
			{
				blackNum++;
			}
			if (root->_col == RED && root->_parent->_col == RED)
			{
				cout << "出现连续红色节点,不是红黑树" << endl;
				return false;
			}

			return PrevCheck(root->_left,blackNum,benchmark) 
				&& PrevCheck(root->_right,blackNum,benchmark);
		}
		void _Inorder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Inorder(root->_left);
			cout << root->_kv.first << ":" << root->_kv.second << endl;
			_Inorder(root->_right);
		}
	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 (ppNode == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
				subL->_parent = ppNode;
			}
			else
			{
				ppNode->_right = subL;
				subL->_parent = ppNode;
			}
		}
	}
	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;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}
};
void TestRBTree1()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 0,5,30,25,20,4,13,30,28,27 };  // 测试双旋平衡因子调节
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	RBTree<int, int> t1;
	for (auto e : a)
	{
		t1.insert(make_pair(e, e));
	}

	t1.Inorder();
	cout << "IsBalance:" << t1.IsBalance() << endl;
}

void TestRBTree2()
{
	size_t N = 1000;
	srand(time(0));
	RBTree<int, int> t1;
	for (size_t i = 0; i < N; ++i)
	{
		int x = rand();
		cout << "Insert:" << x << ":" << i << endl;
		t1.insert(make_pair(x, i));
	}
	cout << "IsBalance:" << t1.IsBalance() << endl;
}

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

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

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

相关文章

  • 数据结构——红黑树

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

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

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

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

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

    2024年02月01日
    浏览(40)
  • C++数据结构--红黑树

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

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

    数据结构可视化演示链接,也就是图片演示的网址 数据结构之AVL Tree 数据结构之B树和B+树 数据结构之Radix和Trie 数据结构之二叉搜索树 红黑树是一种二叉查找树,但在每个结点上增加了一个存储位表示结点的颜色,可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个

    2024年01月17日
    浏览(43)
  • 数据结构--红黑树详解

    红黑树(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)
  • 数据结构篇十:红黑树

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

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

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

    2023年04月17日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包