数据结构之——红黑树

约定不等于承诺〃 2022-01-11 02:33 271阅读 0赞

红黑树是一棵二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是red或black。通过对任何一条从根到叶子简单路径上的颜色来约束，红黑树保证最长路径不超过最短路径的两倍，因而近似于平衡。

红黑树是满足下面红黑性质的二叉搜索树：

1.  每个节点，不是红色就是黑色的
2.  根节点是黑色的
3.  如果一个节点是红色的，则它的两个子节点是黑色的(没有连续的红节点)
4.  对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。（每条路径的黑色节点的数量相等）

这里分析一下为什么红黑树能保证最长路径不超过最短路径的两倍：首先因为第4条约束条件假设一棵树如下所示：

B B

B B B表示为黑色结点，那么要在其中插入任何一个黑色结点就需要保证第4条约定，而如果要插入红色结点，则第3条约束又使得红色结点只能插在黑色结点之间，因此一条路径最多变成：

B R

B B

B 因此，最长路径不超过最短路径的两倍，也就保证了搜索的效率；

下面是实现红黑树的插入过程：

#pragma once
    
    #include <iostream>
    using namespace std;
    
    //结点的颜色 红or黑
    enum Color
    {
    	RED,
    	BLACK
    };
    
    //结点结构体
    template <class K, class V>
    struct RBTreeNode
    {
    	K _key;
    	V _val;
    	RBTreeNode<K, V>* _left;
    	RBTreeNode<K, V>* _right;
    	RBTreeNode<K, V>* _parent;
    	Color _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)
    	{}
    	~RBTree()
    	{
    		_Clear(_root);
    	}
    
    	//插入结点
    	bool Insert(const K& key, const V& val)
    	{
    		if(_root == NULL)//如果根结点为NULL，创建新的结点为根结点返回true
    		{
    			_root = new Node(key, val);
    			_root->_col = BLACK;
    			return true;
    		}
    
    		//如果根结点不为NULL，则遍历树直到找到合适的插入位置
    		Node* cur = _root;
    		Node* prev = cur;
    		while(cur != NULL)
    		{
    			if(cur->_key == key)//如果树中已经有该结点，则返回false
    				return false;
    			else if(cur->_key > key)//如果关键值小于结点的关键值，则去左子树找
    			{
    				prev = cur;
    				cur = cur->_left;
    			}
    			else//否则关键值大于结点的关键值，去右子树找
    			{
    				prev = cur;
    				cur = cur->_right;
    			}
    		}
    		//循环结束，找到了合适的插入位置，判断应该插入到结点的左边还是右边
    		Node* tmp = new Node(key, val);
    		if(prev->_key > key)
    			prev->_left = tmp;
    		else
    			prev->_right = tmp;
    		tmp->_parent = prev;
    
    		//插入结点之后，就要开始判断目前的树是否符合红黑树的性质
    		while((tmp != _root) && (prev->_col == RED))
    		{
    			Node* grandfather = prev->_parent;//提取出tmp的祖父结点
    			if(grandfather->_left == prev)//如果prev是grandfather的左结点
    			{
    				//第一种情况
    				//tmp为红，prev为红，grandfather为黑，uncle存在且为红
    				//则将prev,uncle改为黑，grandfather改为红，然后把grandfather当成tmp，继续向上调整。
    				Node* uncle = grandfather->_right;
    				if(uncle != NULL && uncle->_col == RED)
    				{
    					prev->_col = BLACK;
    					uncle->_col = BLACK;
    					grandfather->_col = RED;
    
    					tmp = grandfather;
    					prev = tmp->_parent;
    				}
    				else//第二种情况:tmp为红，prev为红，grandfather为黑，uncle不存在/uncle为黑
    					//prev为grandfather的左孩子，tmp为prev的左孩子，则进行右单旋转；
    					//prev、grandfather变色--prev变黑，grandfather变红
    
    				{
    					//第三种情况
    					//tmp为红，prev为红，grandfather为黑，uncle不存在/uncle为黑
    					//prev为grandfather的左孩子，tmp为prev的右孩子，则针对prev做左单旋转；
    					//则转换成了情况二
    
    					if(prev->_right == tmp)
    					{
    						_RotateL(prev);
    						swap(tmp, prev);
    					}
    					_RotateR(grandfather);//进行右单旋
    					prev->_col = BLACK;
    					grandfather->_col = RED;
    					break;
    				}
    			}
    			else//当perv是grandfather的右结点的时候，和上面的情况相反
    			{
    				//第一种情况
    				//tmp为红，prev为红，grandfather为黑，uncle存在且为红
    				//则将prev,uncle改为黑，grandfather改为红，然后把grandfather当成tmp，继续向上调整。
    				Node* uncle = grandfather->_left;
    				if(uncle != NULL && uncle->_col == RED)
    				{
    					prev->_col = BLACK;
    					uncle->_col = BLACK;
    					grandfather->_col = RED;
    
    					tmp = grandfather;
    					prev = tmp->_parent;
    				}
    				else//第二种情况:tmp为红，prev为红，grandfather为黑，uncle不存在/uncle为黑
    					//prev为grandfather的右孩子，tmp为prev的右孩子，则进行左单旋转
    					//prev、grandfather变色--prev变黑，grandfather变红
    
    				{
    					//第三种情况
    					//tmp为红，prev为红，grandfather为黑，uncle不存在/uncle为黑
    					//prev为grandfather的右孩子，tmp为prev的左孩子，则针对prev做右单旋转
    					//则转换成了情况二
    
    					if(prev->_left == tmp)
    					{
    						_RotateR(prev);
    						swap(tmp, prev);
    					}
    					_RotateL(grandfather);//进行右单旋
    					prev->_col = BLACK;
    					grandfather->_col = RED;
    					break;
    				}
    			}
    		}
    		//如果根结点被调整成了红色，将其改为黑色，并会不影响左右黑结点的个数
    		if(_root->_col == RED)
    			_root->_col = BLACK;
    		return true;
    	}
    
    	void InOrder()
    	{
    		_InOrder(_root);
    		cout<<endl;
    	}
    
    	/*bool Find(const K& key)
    	{
    
    	}*/
    
    private:
    	void _Clear(Node* root)
    	{
    		if(root == NULL)
    			return;
    
    		_Clear(root->_left);
    		_Clear(root->_right);
    		delete root;
    		root = NULL;
    	}
    	
    	void _RotateL(Node* parent)//左单旋
        {
            Node* subR = parent->_right;
            Node* subRL = subR->_left;
     
            parent->_right = subRL;
            if (subRL != NULL)
                subRL->_parent = parent;
             
            Node* ppNode = parent->_parent;
     
            subR->_left = parent;
            parent->_parent = subR;
     
            if (ppNode == NULL)
                _root = subR;
            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 != NULL)
                subLR->_parent = parent;
     
            Node* ppNode = parent->_parent;
            subL->_right = parent;
            parent->_parent = subL;
     
            if (ppNode == NULL)
                _root = subL;
            else
            {
                if (ppNode->_left == parent)
                    ppNode->_left = subL;
                else
                    ppNode->_right = subL;
            }
    		subL->_parent = ppNode;
    	}
    
    	void _InOrder(Node* root)
    	{
    		if(root != NULL)
    		{
    			_InOrder(root->_left);
    			cout<<root->_key<<" ";
    			_InOrder(root->_right);
    		}
    	}
    
    private:
    	Node* _root;
    };
    
    
    void Test()
    {
    	int arr[] = {3, 4, 6, 1, 7, 2, 8};
    	RBTree<int, int> t;
    	for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i)
    		t.Insert(arr[i], i);
    
    	t.InOrder();
    }

运行程序：

[![wKioL1eeGTLBZhTBAABpj\_8nBYA643.png-wh\_50][wKioL1eeGTLBZhTBAABpj_8nBYA643.png-wh_50]][wKioL1eeGTLBZhTBAABpj_8nBYA643.png-wh_50]

《完》

转载于:https://blog.51cto.com/2627lounuo/1832660

[wKioL1eeGTLBZhTBAABpj_8nBYA643.png-wh_50]: /images/20220111/3f0fe5f53d39494c9d095bee99a5ed01.png