数据结构 — 浅析红黑树原理以及实现

╰半夏微凉° 2022-06-06 06:52 174阅读 0赞

# 浅析红黑树原理以及实现 #

*我们在上一篇博客认识到了[平衡二叉树(AVLTree)][AVLTree]，了解到平衡二叉树的性质，其实平衡二叉树最大的作用就是查找,AVL树的查找、插入*

*和删除在平均* *和* *最坏情况下都是O(logn)。AVL树的效率就是高在这个地方。如果在AVL树中插入或删除节点后，使得高度之差大于1。此*

*时，AVL树的平衡状态就被破* *坏，* *它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理, 现在呢，我*

*们来思考一下虽然AVL树的查找效率高，但是* *呢构建* *一颗AVL树的成本是多少？？ 因为当它的高度差大于1的时候，就要触发旋转算法来*

*调节平衡二叉树，所以当你数据足够大的时候，那么你创建* *一* *颗平衡* *二叉树的成本其实不小. 这个时候就有人开始思考，并且提出了* *红*

*黑树的理论，那么红黑树到底比AVL树好在哪里？？*

*首先我们应该知道由于AVL树的性质，当它的任意两个分支之间的高度差大于一的时候就会触发旋转算法,所以构建一棵树得触发很多次*

*旋转算法，这里* *的AVL树的查找时间复杂度为O(logN)，但是* *红* *黑树它的性质让它的查找的时间复杂度为O(nlogN).可以看出AVL树时间复*

*杂* *度优于红黑树，BUT！！ 在计* *算机* *中它* *的计算速度惊人每秒的运算量都是亿级的，所以nlogN和logN在计算机面前没有什么区别，红*

*黑* *树触发旋转算法的概率要远远小于AVL树，这时* *构建一* *个红黑树的成本也就远远小于AVL树，所以生活中经常使用的都是红黑树.（AVL*

*树只是红黑树的一个前身，红黑树就是AVL树的加强版）* *首先我们来认识红黑树的性质，红黑树是一颗二叉搜索树，它在每个节点上增*

*加* *了一个存储为来表示节点的颜色，可以RED或BLACK,通过对任何一条从* *根到叶子简单路径上的颜色约束，红黑树保证最长路径不超过*

*最短路径的两倍，因而近似平衡.*

**红黑树的具体性质**

***1.每个节点的颜色不是红色就是黑色.***

***2.红黑树的根节点必须是黑色的.***

***3.如果一个节点是红色的，则它的两个子节点是黑色的.***

***4.对每一个节点，从该节点到齐所有后代节点的简单路径上，均包含相同数目的黑色节点.***

其实当我们的上面这些条件满足后，这棵树就是已经是一个最长路径不超过最短路径的两倍了. 具体为什么？？ 这里我解释一下.

![20171102162304978][]

有这张图我也不需要再解释什么了，你的最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，最后黑色节点相同时，最长路

径刚好是最短路 径的两倍. 可以看到这几个性质看起来没有联系，但是环环相扣最后构成一个红黑树. 所以我们构建红黑树的时候一定

要注意性质.

***红黑树的插入***

*首先红黑树的插入其实不是那么容易实现的，以前搜索树的插入我们很容易理解现在我们首先思考一个问题，你插入节点的默认颜*

*色是RED或* *BLACK？*  *这里我们需要根据性质来思考，首先如果插入黑节点，这个可以直接插入无论它的父亲是什么颜色，但是红黑*

*树* *的性质是每条路径的黑色节点数目相同* *这个时候你再想想那其他路径的黑色节点数目一定比你现在少一个节点，所以调整起来* *是*

*非常繁琐的. 插入红节点不需要调整其他路径，如果它的父亲* *为黑，那么直接插入，如果他的父亲为红那么在该路径上面开始分*

*情况调整. 所以插入节点默认颜色一定要为红.如果为黑调节成本太大了.* *接下来开始插入节点如果插入节点的父亲为黑那么直接插*

*入后返回不需要做任何调整. 但是如果插入节点的父亲为红，那么就需要调整了.具体的调整* *过程可以分为三个情况：*

**1. 新插入节点Cur的父亲为红，并且爷爷节点(parentparent)为黑，叔叔节点(uncle)存在且为红.**

**![20171103124851303][]**

*此时对该子树进行操作，parent节点和uncle节点变为黑，parentparent节点变为红，这样我们就保证该子树中每条路径中黑色节点相同*

*并且没有* *连续的红节点，然后再让cur等于parentparent节点继续往上继续调整，直到该树中没有连续的红节点. 具体的过程如图所示：*

*![20171103125221965][]*

**2. 新插入节点Cur的父亲为红，并且爷爷节点(parentparent)为黑，叔叔节点(uncle)不存在或存在且为黑.**

**![20171103125438587][]**

*首先我们要明白，第二种情况一定是第一种情况调整后，然后向上调整的时候所遇到的.也就是说你单纯插入一个节点是不可能碰到* *这*

*种情况,出现* *这种情况的原因就是，第一种情况调整后，它的parentparent节点变为红色，然后才会出现这种情况. 那么为什么呢？？*

***因为就拿上面这个子树来看，如果你cur是新插入的话，明显就很不合理！ 因为你的父亲是红的而你的叔叔是黑的！ 这条路径很明***

***显黑节点个*** ***数和别的路径不一样，所以只有一种可能那就是，cur以前是黑节点，因为颜色调整被变成红色，进而触发旋转操作.***

*然后我们对这棵子树进行操作，这里有一些旋转的知识如果不明白的话，可以去看我得上一个博客：[AVL树][AVLTree]. 该博客里面对旋转操作有*

*详细的讲解.* *好了我们继续. 拿这个图为例子. 我们需要根据parentparent节点进行右单旋. 然后将parent节点变为黑色，cur节点和*

*parentparent变为红色.* *当然如果parent为parentparent的右，cur为patent的右就是左单旋了. 具体过程如图所示:*

*![20171103125932327][]*

**2. 新插入节点Cur的父亲为红，并且爷爷节点(parentparent)为黑，叔叔节点(uncle)不存在或存在且为黑.**

*这种情况乍得一看跟上面一模一样（其实就是一模一样(手动微笑)）. 但是我在这里提的是一个特殊一点的情况,因为这里需要触发右*

*左双旋或者左右* *双旋. 我们看下图这种情况，它满足上述情况但是无法触发左单旋或者右单旋.所以我们得对它进行一点操作，让它可*

*以旋转.*

*![20171103131730167][]*

*就拿这个图来说，我们先对parent进行左单选，再然后针对parentpatent进行右单旋. 最后进行于上面相同的变色操作即可. 当然右左*

*双旋步骤也一样*

*![20171103132110147][]*

代码实现:

bool Insert(const K& key, const V& val)
    	{
    		//_Insert(_root, x, y);
    		if (_root == NULL)
    		{
    			_root = new Node(key, val);
    			_root->_col = BLACK;
    		}
    
    		Node* cur = _root;
    		Node* parent = cur;
    
    		while (cur)
    		{
    			if (cur->_key > key)
    			{
    				parent = cur;
    				cur = cur->_left;
    			}
    			else if (cur->_key < key)
    			{
    				parent = cur;
    				cur = cur->_right;
    			}
    			else if (cur->_key == key)
    			{
    				return true;
    			}
    		}
    
    		if (parent->_key > key)
    		{
    			parent->_left = new Node(key, val);
    			parent->_left->_parent = parent;
    			cur = parent->_left;
    		}
    		else
    		{
    			parent->_right = new Node(key, val);
    			parent->_right->_parent = parent;
    			cur = parent->_right;
    		}
    	
    		//目前父亲节点，插入节点，叔叔节点已经就绪.
    		while(parent && parent->_col == RED)
    		{
    			Node* parentparent = parent->_parent;
    			Node* uncle = NULL;
    
    			if (parentparent->_left == parent)
    				uncle = parentparent->_right;
    
    			else
    				uncle = parentparent->_left;
    
    			if(uncle && uncle->_col == RED)
    			{
    				parentparent->_col = RED;
    				parent->_col = BLACK;
    				uncle->_col = BLACK;
    
    				cur = parentparent;
    				parent = cur->_parent;
    
    			}
    			else if (uncle == NULL || uncle->_col == BLACK)
    			{
    				if (parentparent->_left == parent)
    				{
    					if (parent->_left == cur)
    					{
    						RotateR(parentparent);
    						parent->_col = BLACK;
    					}
    					else
    					{
    						RotateLR(parentparent);
    						cur->_col = BLACK;
    					}
    				}
    				else
    				{
    					if (parent->_right == cur)
    					{
    						RotateL(parentparent);
    						parent->_col = BLACK;
    					}
    					else
    					{
    						RotateRL(parentparent);
    						cur->_col = BLACK;
    					}
    				}
    				parentparent->_col = RED;
    				if (parentparent == _root)
    				{
    					_root = parent;
    				}
    			
    			}
    			else
    			{
    				assert(false);
    			}
    			if (_root->_col == RED)
    			{
    				_root->_col = BLACK;
    			}
    		}
    		return false;
    	}

***红黑树的删除***

*红黑树的删除有一定的难度，这里我就说的没有这么详细了其实它跟搜索树的删除很类似就是寻找一个替换节点然后删掉它的替换节点*

![20171103132834778][]

*我们要删除del这个时候，直接删除del成本太高了，然后我们寻找一个边缘节点跟他交换，然后再删除它.所以呢，这样删除的成本是*

*最小的.* *删除分三个情况：*

*1.del的左为空.*

*2.del的右为空.*

*3.del的左右都不为空.*

*前两种很容易思考，第三种左右都不为空的情况才需要我们的边缘替换法.所以我这里附上搜索二叉树的删除的代码. 红黑树删除的代*

*码暂时我还没有**解决所以这里之后搜索二叉树的删除代码. 我们可以想着思考思考说不定就写完了.*

*代码实现：*

bool Remove(const K& key)
    	{
    		if (_root == NULL)
    		{
    			return false;
    		}
    		Node* cur = _root;
    		Node* parent = NULL;
    		while (cur)
    		{		
    			if (cur->key > key)
    			{
    				parent = cur;
    				cur = cur->_left;
    			}
    			else if (cur->key < key)
    			{
    				parent = cur;
    				cur = cur->_right;
    			}
    			else if (cur->key == key)
    			{
    				break;
    			}
    		}
    
    		Node* del = cur;
    		if (cur->_left == NULL) //左为空
    		{
    			if (parent == NULL)
    			{
    				_root = cur->_right;
    				if (_root)
    					_root->_parent = NULL;
    			}
    			else
    			{
    				if (parent->_left == cur)
    					parent->_left = cur->_right;
    				
    				else			
    					parent->_right = cur->_right;
    			
    				if (cur->_right)
    					cur->_right->_parent = parent;
    			}
    		}
    		else if (cur->_right == NULL)//右为空
    		{
    			if (parent == NULL)
    			{
    				_root = cur->_left;
    				if (_root)
    					_root->_parent = NULL;
    			}
    			else
    			{
    				if (parent->_left == cur)
    					parent->_left = cur->_left;
    				else
    					parent->_right = cur->_left;
    
    				if (cur->_left)
    					cur->_left->_parent = parent;
    			}	
    		}
    
    		else //左右都不为空
    		{
    			if (parent == NULL || cur == parent->_left) //如果cur在左边.
    			{
    				del = cur->_right;
    
    				while (del->_left)
    				{
    					del = del->_left;
    				}
    
    				del->_parent->_left = del->_right;;
    			}
    			else //cur在parent的右边.
    			{
    				del = cur->_left;
    
    				while (del->_right)
    				{
    					del = del->_right;
    				}
    
    				del->_parent->_right = del->_left;
    			}
    			cur->key = del->key;
    			cur->val = del->val;
    		}
    
    		delete del;
    	}

**编写一个检验该二叉树是否为红黑树的程序：**

*这里首先解决一个最棘手的问题，如何判断一个路径上面的黑节点相同？ 我们很容易想到，可以先遍历一条路径找到一个基准值，然*

*后和其他路径做**比较，代码实现就是每次走到叶子结点的时候，比较该条路径的黑色节点节点个数是否和基准值相等？ 如果不**相等*

*那么返回false. 所以我们参数里面**需要一个m（传递黑色节点基准值）和n(记录该条路径上面的黑色节点个数).*

*那么我们来瞧瞧代码实现：*

bool ISRBtree()
    	{
    		if (_root->_col == RED)
    		{
    			return false;
    		}
    		size_t n = 0;
    		size_t m = 0;
    		Node* cur = _root;
    		while (cur)
    		{
    			if (cur->_col == BLACK)
    			{
    				n++;
    			}
    			cur = cur->_left;
    		}
    		return _ISRBtree(_root, m, n);
    	}
    
    	bool _ISRBtree(Node* root, size_t m, size_t n)
    	{
    		if (root == NULL)
    		{
    			if (m == n)
    				return true;
    			else
    				return false;
    		}
    
    
    		if (root->_col == BLACK)
    		{
    			m++;
    		}
    		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
    		{
    			return false;
    		}
    
    		return _ISRBtree(root->_left, m, n) && _ISRBtree(root->_right, m, n);
    
    	}

**演示结果：**

**![20171103134835055][]**

***总结***

*红黑树是一个非常重要的数据结构，现在生活当中的使用我们就能看的出来，可能我们并不需要它的底层构造但是我们要学习一个语*

*言. 最快的途径就**是大师写出来的代码，手头都是资料我们要学习别人的巧妙的地方. 多看源码多多构造经典的算法，或者容器.*

*尝试自己编写代码，理解那个框架, 这**样对我们的进步都是非常有用的.红黑树目前我就总结这么多，哪里有不足欢迎大家来指出来*

*，我会虚心改正.*

*所有代码实现：*

#include<iostream>
    #include<Windows.h>
    #include<assert.h>
    using namespace std;
    
    enum colour
    {
    	RED,
    	BLACK
    };
    
    template<class K, class V>
    struct RBTreeNode
    {
    	K _key;
    	K _val;
    
    	RBTreeNode<K, V>* _left;
    	RBTreeNode<K, V>* _right;
    	RBTreeNode<K, V>* _parent;
    
    	colour _col;
    
    	RBTreeNode(const K& key, const V& val)
    		:_key(key)
    		, _val(val)
    		, _left(NULL)
    		, _right(NULL)
    		, _parent(NULL)
    		, _col(RED)
    	{}
    };
    
    template<class K, class V>
    class RBTree
    {
    	typedef RBTreeNode<K, V> Node;
    public:
    	RBTree()
    		:_root(NULL)
    	{}
    
    	bool Insert(const K& key, const V& val)
    	{
    		//_Insert(_root, x, y);
    		if (_root == NULL)
    		{
    			_root = new Node(key, val);
    			_root->_col = BLACK;
    		}
    
    		Node* cur = _root;
    		Node* parent = cur;
    
    		while (cur)
    		{
    			if (cur->_key > key)
    			{
    				parent = cur;
    				cur = cur->_left;
    			}
    			else if (cur->_key < key)
    			{
    				parent = cur;
    				cur = cur->_right;
    			}
    			else if (cur->_key == key)
    			{
    				return true;
    			}
    		}
    
    		if (parent->_key > key)
    		{
    			parent->_left = new Node(key, val);
    			parent->_left->_parent = parent;
    			cur = parent->_left;
    		}
    		else
    		{
    			parent->_right = new Node(key, val);
    			parent->_right->_parent = parent;
    			cur = parent->_right;
    		}
    	
    		//目前父亲节点，插入节点，叔叔节点已经就绪.
    		while(parent && parent->_col == RED)
    		{
    			Node* parentparent = parent->_parent;
    			Node* uncle = NULL;
    
    			if (parentparent->_left == parent)
    				uncle = parentparent->_right;
    
    			else
    				uncle = parentparent->_left;
    
    			if(uncle && uncle->_col == RED)
    			{
    				parentparent->_col = RED;
    				parent->_col = BLACK;
    				uncle->_col = BLACK;
    
    				cur = parentparent;
    				parent = cur->_parent;
    
    			}
    			else if (uncle == NULL || uncle->_col == BLACK)
    			{
    				if (parentparent->_left == parent)
    				{
    					if (parent->_left == cur)
    					{
    						RotateR(parentparent);
    						parent->_col = BLACK;
    					}
    					else
    					{
    						RotateLR(parentparent);
    						cur->_col = BLACK;
    					}
    				}
    				else
    				{
    					if (parent->_right == cur)
    					{
    						RotateL(parentparent);
    						parent->_col = BLACK;
    					}
    					else
    					{
    						RotateRL(parentparent);
    						cur->_col = BLACK;
    					}
    				}
    				parentparent->_col = RED;
    				if (parentparent == _root)
    				{
    					_root = parent;
    				}
    			
    			}
    			else
    			{
    				assert(false);
    			}
    			if (_root->_col == RED)
    			{
    				_root->_col = BLACK;
    			}
    		}
    		return false;
    	}
    
    	bool ISRBtree()
    	{
    		if (_root->_col == RED)
    		{
    			return false;
    		}
    		size_t n = 0;
    		size_t m = 0;
    		Node* cur = _root;
    		while (cur)
    		{
    			if (cur->_col == BLACK)
    			{
    				n++;
    			}
    			cur = cur->_left;
    		}
    		return _ISRBtree(_root, m, n);
    	}
    
    	void print()
    	{
    		_print(_root);
    	}
    
    protected:
    
    	void _print(Node* root)
    	{
    		if (root == NULL)
    			return;
    
    		_print(root->_left);
    		cout << root->_val << " ";
    		_print(root->_right);
    	}
    
    	bool _ISRBtree(Node* root, size_t m, size_t n)
    	{
    		if (root == NULL)
    		{
    			if (m == n)
    				return true;
    			else
    				return false;
    		}
    
    
    		if (root->_col == BLACK)
    		{
    			m++;
    		}
    		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
    		{
    			return false;
    		}
    
    		return _ISRBtree(root->_left, m, n) && _ISRBtree(root->_right, m, n);
    
    	}
    
    	void RotateLR(Node*& parent)
    	{
    
    		RotateL(parent->_left);
    
    		RotateR(parent);
    	}
    
    	void RotateRL(Node*& parent)
    	{
    		RotateR(parent->_right);
    		RotateL(parent);
    	}
    
    	void RotateR(Node*& parent)
    	{
    		Node* subL = parent->_left;
    		Node* subLR = NULL;
    		if (subL)
    			subLR = subL->_right;
    		parent->_left = subLR;
    		if (subLR)
    			subLR->_parent = parent;
    		Node* ppNode = parent->_parent;
    		subL->_right = parent;
    		parent->_parent = subL;
    		if (ppNode == NULL)
    		{
    			_root = subL;
    			_root->_parent = NULL;
    		}
    		else
    		{
    			if (ppNode->_left == parent)
    				ppNode->_left = subL;
    			else
    				ppNode->_right = subL;
    			subL->_parent = ppNode;
    		}
    	}
    
    	void RotateL(Node*& parent)
    	{
    		Node* subR = parent->_right;
    		Node* subRL = NULL;
    		if (subR)
    			subRL = subR->_left;
    
    		parent->_right = subRL;
    		if (subRL)
    			subRL->_parent = parent;
    
    		Node* ppNode = parent->_parent;
    		subR->_left = parent;
    		parent->_parent = subR;
    
    		if (ppNode == NULL)
    		{
    			_root = subR;
    			_root->_parent = NULL;
    		}
    		else
    		{
    			if (ppNode->_left == parent)
    				ppNode->_left = subR;
    			else
    				ppNode->_right = subR;
    			subR->_parent = ppNode;
    		}
    	}
    
    
    private:
    	Node* _root;
    };
    
    
    
    void Test()
    {
    	RBTree<int, int> T;
    	//8 9 2 4 1 6 3 5
    	T.Insert(8, 8);
    	T.Insert(9, 9);
    	T.Insert(2, 2);
    	T.Insert(4, 4);
    	T.Insert(1, 1);
    	T.Insert(6, 6);
    	T.Insert(3, 3);
    	T.Insert(5, 5);
    
    	cout << "该二叉树是否为红黑树??" << T.ISRBtree() << endl;
    	T.print();
    	system("pause");
    
     }

[AVLTree]: http://blog.csdn.net/dawn_sf/article/details/72859178
[20171102162304978]: /images/20220606/31795cfc04154e10b238210640f28a8d.png
[20171103124851303]: /images/20220606/e483d1b1c7204057bbb48067cc39c0c8.png
[20171103125221965]: /images/20220606/7349f895f4e24dfa91478c2ab85f70f2.png
[20171103125438587]: /images/20220606/7fbc26838db04250b4963f36bc4e1a5a.png
[20171103125932327]: /images/20220606/e686edbff1c445eaae13feb5062cefa0.png
[20171103131730167]: /images/20220606/6fce3e6deb914e8d94b8826948eaaa6f.png
[20171103132110147]: /images/20220606/9f953a3e8bab49a58d6ee81b4dbb4f5b.png
[20171103132834778]: /images/20220606/84fa2f4e18644eac9a6afbbe45ade8d9.png
[20171103134835055]: /images/20220606/b17925660432408aa69bebbe49d33dcc.png