signed

QiShunwang

“诚信为本、客户至上”

高阶数据结构与算法 | RB_Tree(红黑树)的实现

2021/6/9 9:23:38   来源:

红黑树

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

红黑树的性质 

  1. 每个节点不是红色就是黑色
  2. 根节点必须是黑色
  3. 如果一个节点是红的,则它的两个孩子是黑的(不存在连续的红节点)
  4. 从某一节点出发到所有的叶子节点,其中经过的黑色节点数量相等
  5. 每个叶子节点是黑色的(这里的叶子节点指的是NULL节点)

对于一个节点,到其叶子节点所经过的最短路径即全为黑色节点,最长路径则为一黑一红交错的路径

红黑树的实现: 

红黑树节点数据结构:

enum Color {
	Red,
	Black
};

template<class T>
struct RBTree {
	T _val;
	Color _color;
	RBTree<T>* _parent;
	RBTree<T>* _left;
	RBTree<T>* _right;
	RBTree(const pair<T>& val = T(), const Color& color = Red)
		:_val(val)
		,_color(color)
		,_parent(nullptr)
		,_left(nullptr)
		,_right(nullptr)
	{}
};

红黑树的插入:

插入分为两个步骤:

  1. 按照二叉搜索树的特性找到插入的位置
  2. 按照红黑树的特性进行调节(旋转+调整颜色)

决定新插入节点的颜色:

如果新插入的结点为红色,则有可能打破了不能有连续的红结点这一规则,而如果插入的是黑色,则又破坏了每个路径的黑节点数量相同这一规则。如果都会破坏的话,就需要选择一个方便修复的,而不能有连续的红结点这一规则,只需要进行一下颜色的变换或者旋转,就可以解决这个问题,所以新增节点都为红色

插入节点出现的各种情况:

情况1:插入节点的父节点为黑色

此时是最好的情况,因为没有破坏任何规则,所以此时无须任何处理.

情况2:插入节点的父节点为红色,叔叔节点也为红色,祖父为黑色

 因为出现了连续的红色节点,所以只需要进行颜色的修正即可解决.(将父节点和叔叔节点变黑,祖父节点变红即可).同时,因为祖父节点之上可能还有其它节点,还需要从祖父节点的位置继续向上调整.

情况3:插入节点的父节点为红色,叔叔为黑或者不存在,祖父为黑.孩子与父亲呈直线状态.

这里有两种情况:

  1. 如果叔叔存在,则此时的孩子节点可能是下面的子树在进行变色处理时,将其从原本的黑色变为了红色。(否则不满足路径黑节点数量相同的性质)
  2. 如果叔叔不存在,则此时的孩子节点是刚插入进来的结点,因为不能有连续的红结点,所以孩子和父亲必须有一个是黑色,但是此时又不满足黑节点数量相同的性质。

解决的方法也不难,只需要旋转+变色处理即可
和AVL树一样,因为父亲和孩子呈直线状态,所以只需要单旋即可。
如果父亲是祖父的左孩子,孩子是父亲的左孩子,此时祖父进行右单旋
如果父亲是祖父的右孩子,孩子是父亲的右孩子,此时祖父进行左单旋。

情况4:父亲为红色,叔叔为黑色或者不存在,祖父为黑色.孩子与父亲呈折现状态.

这种情况与情况3类似,采取的解决办法是双旋+变色处理

如果父亲是祖父的左孩子,孩子是父亲的右孩子,父亲此时需要左单旋.

如果父亲是祖父的右孩子,孩子是父亲的左孩子,父亲此时需要右单旋.

 左/右单旋后,交换父节点与新插入节点之后,就变成了情况3,接着按照情况3的处理办法接着处理即可.

bool Insert(const std::pair<K, V>& val){
    //判断树是否为空
	if (_root == nullptr){
		_root = new Node(val, Black);
		return true;
	}
    //查找
	Node* cur = _root;
	Node* parent = nullptr;

	while (cur){
		if (val.first > cur->_val.first){
			parent = cur;
			cur = cur->_right;
		}
		else if (val.first < cur->_val.first){
			parent = cur;
			cur = cur->_left;
		}
		else{
			return false;
		}
	}

	//新插入节点为红色
	cur = new Node(val, Red);

	//保存插入的结点,因为后面会往上更新红黑树,所以cur可能会变化。
	Node* newNode = cur;

	//判断插入位置
	if (cur->_val.first > parent->_val.first){
		parent->_right = cur;
	}
	else{
		parent->_left = cur;
	}
	cur->_parent = parent;

	//更新红黑树,如果父节点的颜色为黑,则说明满足条件,不需要处理,如果为红,则说明不满足,需要处理。
	while (parent && parent->_color == Red){
		Node* ppNode = parent->_parent;

		//如果父节点为祖父的左子树
		if (ppNode->_left == parent){
			//此时判断叔叔节点的状态,红黑树状态取决于叔叔
			Node* uncle = ppNode->_right;

			//第一种情况,如果叔叔节点存在且为红,则直接把父亲和叔叔变黑,祖父节点边红即可。然后再从祖父的位置继续往上调整
			if (uncle && uncle->_color == Red){
				//变色
				uncle->_color = parent->_color = Black;
				ppNode->_color = Red;

				//继续往上
				cur = ppNode;
				parent = cur->_parent;
			}
			/*
				叔叔节点为黑或者不存在,此时有两种情况
				情况二:cur为父节点的左子树,即直线状态。
				情况三:cur为父节点的右子树,即折线状态。

				情况二单旋一次后更改颜色即可完成
				对于情况三,如果将其进行一次旋转后再稍微处理,就可以转换成情况二
			 */
			else{
		     	//因为这里的双旋和AVL不一样,可以不用处理平衡因子,所以如果为折线则先旋转处理后,将其转换为直线处理即可。

				//第三种情况,折线状态,转换为直线状态处理
				if (parent->_right == cur){
					RotateL(parent);
					//单旋后再交换节点,即可变成直线状态。
					std::swap(parent, cur);
				}

				//处理第二种状态
				RotateR(ppNode);

				parent->_color = Black;
				ppNode->_color = Red;

				//处理完成
				break;
			}

		}
		//如果父亲为祖父的右子树
		else{
			//此时叔叔为左子树。
			Node* uncle = ppNode->_left;

			if (uncle && uncle->_color == Red){
				uncle->_color = parent->_color = Black;
				ppNode->_color = Red;

				cur = ppNode;
				parent = cur->_parent;
			}
			else{
				if (parent->_left == cur){
					RotateR(parent);
					std::swap(cur, parent);
				}

				RotateL(ppNode);

				ppNode->_color = Red;
				parent->_color = Black;

				break;
			}
		}
	}
	//为了防止不小心把根节点改为红色,最后手动改为黑色即可
	_root->_color = Black;
	return true;
}

旋转:左旋AND右旋

//左旋:
     void RotateL(){
         Node* subR = parent->_right;
         Node* subRL = subR->_left;
         
         subR->_left = parent;
         parent->_right = subRL;
         if(subRL){
             subRL->_parent = parent;
         }
         //连接subR与祖父节点
         if(parent == _root){
             _root = subR;
             subR->_parent = nullptr;
         }else{
             Node* g = parent->_parent;
             subR->_parent = g;
             if(g->_left == parent){
                 g->_left = subR;
             }else{
                 g->_right = subR;
             }
         }
         parent->_parent = subR;
     }

//右旋:
     void RotateR(Node* parent) {
         Node* subL = parent->_left;
         Node* subLR = subL->_right;
 ​
         subL->_right = parent;
         parent->_left = subLR;
         if (sunLR) {
             subLR->_parent = parent;
         }
         if (parent == root) {
             _root = subL;
             subL->_parent = nullptr;
         }
         else {
             Node* g = parent->_parent;
             subL->_parent = g;
             if (g->_left == parent) {
                 g->_left = subL;
             }
             else {
                 g->_right = subL;
             }
         }
         //再连接parent的_parent
         parent->_parent = subL;
     }

查找:

bool Find(const std::pair<K, V>& data){
	//根据二叉搜索树的性质,从根节点出发,比根节点大则查找右子树,比根节点小则查找左子树
	Node* cur = _root;
	while (cur)
	{
		//比根节点大则查找右子树
		if (data.first > cur->_data.first)
		{
			cur = cur->_right;
		}
		//比根节点小则查找左子树
		else if (data.first < cur->_data.first)
		{
			cur = cur->_left;
		}
		//相同则返回
		else
		{
			return true;
		}
	}

	//遍历完则说明查找不到,返回false
	return false;
}

红黑树的验证:

  1. 根节点必须为黑节点
  2. 不存在连续的红节点
  3. 从某一节点出发到其所有的叶子节点,其中经过的黑色节点数量相等
bool IsRBTree(){
	if (_root == nullptr){
		//空树也是红黑树
		return true;
	}

	//违反性质1
	if (_root->_color != BLACK){
		return false;
	}

	//获取从根节点出发的任意一条子路径的黑色节点数,这里选取最左子树。
	Node* cur = _root;
	size_t blackCount = 0;
	size_t count = 0;

	while (cur){
    	if (cur->_color == BLACK){
			blackCount++;
		}

		cur = cur->_left;
	}

	//递归判断其他路径的黑色节点数
	return _IsRBTree(_root, count, blackCount);
}

bool _IsRBTree(Node* root, size_t count, const size_t blackCount){
	//此时说明已经走到叶子节点,判断黑色节点数是否相等,不相等则违反性质3
	if (root == nullptr){
		if (count != blackCount){
			return false;
		}
		else{
			return true;
		}
	}
	//如果没走完,就接着判断其他情况

	//判断性质2,如果存在连续的红结点,则返回错误
	Node* parent = root->_parent;

	if (parent && root->_color == RED && parent->_color == RED){
		return false;
	}

	//如果当前节点为黑色,则记录
	if (root->_color == BLACK){
		count++;
	}

	//接着递归判断当前节点的所有路径
	return _IsRBTree(root->_left, count, blackCount) && _IsRBTree(root->_right, count, blackCount);
}

完整代码: 

#include<iostream>
using namespace std;
	enum Color
	{
		BLACK,
		RED,
	};

	template<class K, class V>
	struct RBTreeNode
	{
		typedef RBTreeNode<K, V> Node;
		RBTreeNode(const std::pair<K, V>& data = std::pair<K, V>(), const Color& color = RED)
			: _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _data(data)
			, _color(color)
		{}

		Node* _left;
		Node* _right;
		Node* _parent;
		std::pair<K, V> _data;
		Color _color;
	};


	template<class K, class V>
	class RBTree
	{
	public:
		typedef RBTreeNode<K, V> Node;

		RBTree()
			: _root(nullptr)
		{}

		~RBTree()
		{
			destory(_root);
		}

		void _InOrderTravel(Node* root) const
		{
			if (root == nullptr)
				return;

			_InOrderTravel(root->_left);

			std::cout << root->_data.first << ':' << root->_data.second << std::endl;

			_InOrderTravel(root->_right);
		}

		void InOrderTravel() const
		{
			_InOrderTravel(_root);
		}

		void destory(Node*& root)
		{
			Node* node = root;
			if (!root)
				return;

			destory(node->_left);
			destory(node->_right);

			delete node;
			node = nullptr;
		}

		//右旋
		void RotateR(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;

			parent->_left = subLR;

			//如果subLR存在,则让他的父节点指向parent。
			if (subLR)
			{
				subLR->_parent = parent;
			}

			subL->_right = parent;

			Node* ppNode = parent->_parent;
			parent->_parent = subL;

			//两种情况
			//如果parent为根节点,则让subL成为新的根节点
			if (parent == _root)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			//如果不是根节点,则改变subL与其祖父节点的指向关系
			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 = subR->_left;

			parent->_right = subRL;

			if (subRL)
			{
				subRL->_parent = parent;
			}

			subR->_left = parent;
			Node* ppNode = parent->_parent;
			parent->_parent = subR;

			if (parent == _root)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			else
			{
				if (ppNode->_left == parent)
				{
					ppNode->_left = subR;
				}
				else
				{
					ppNode->_right = subR;
				}

				subR->_parent = ppNode;
			}
		}

		bool Find(const std::pair<K, V>& data)
		{
			//根据二叉搜索树的性质,从根节点出发,比根节点大则查找右子树,比根节点小则查找左子树
			Node* cur = _root;

			while (cur)
			{
				//比根节点大则查找右子树
				if (data.first > cur->_data.first)
				{
					cur = cur->_right;
				}
				//比根节点小则查找左子树
				else if (data.first < cur->_data.first)
				{
					cur = cur->_left;
				}
				//相同则返回
				else
				{
					return true;
				}
			}

			//遍历完则说明查找不到,返回false
			return false;
		}

		bool Insert(const std::pair<K, V>& data)
		{

			//按照二叉搜索树的规则先找到位置
			//创建根节点
			if (_root == nullptr)
			{
				_root = new Node(data, BLACK);

				return true;
			}

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

			while (cur)
			{
				if (data.first > cur->_data.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (data.first < cur->_data.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			//新插入节点为红色
			cur = new Node(data, RED);

			//保存插入的结点,因为后面会往上更新红黑树,所以cur可能会变化。
			Node* newNode = cur;

			//判断插入位置
			if (cur->_data.first > parent->_data.first)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			cur->_parent = parent;

			//更新红黑树,如果父节点的颜色为黑,则说明满足条件,不需要处理,如果为红,则说明不满足,需要处理。
			while (parent && parent->_color == RED)
			{
				Node* ppNode = parent->_parent;

				//如果父节点为祖父的左子树
				if (ppNode->_left == parent)
				{
					//此时判断叔叔节点的状态,红黑树状态取决于叔叔
					Node* uncle = ppNode->_right;

					//第一种情况,如果叔叔节点存在且为红,则直接把父亲和叔叔变黑,祖父节点边红即可。然后再从祖父的位置继续往上调整
					if (uncle && uncle->_color == RED)
					{
						//变色
						uncle->_color = parent->_color = BLACK;
						ppNode->_color = RED;

						//继续往上
						cur = ppNode;
						parent = cur->_parent;
					}
					/*
						叔叔节点为黑或者不存在,此时有两种情况
						情况二:cur为父节点的左子树,即直线状态。
						情况三:cur为父节点的右子树,即折线状态。

						情况二单旋一次后更改颜色即可完成
						对于情况三,如果将其进行一次旋转后再稍微处理,就可以转换成情况二
					 */
					else
					{
						//因为这里的双旋和AVL不一样,可以不用处理平衡因子,所以如果为折线则先旋转处理后,将其转换为直线处理即可。

						//第三种情况,折线状态,转换为直线状态处理
						if (parent->_right == cur)
						{
							RotateL(parent);
							//单旋后再交换节点,即可变成直线状态。
							std::swap(parent, cur);
						}

						//处理第二种状态
						RotateR(ppNode);

						parent->_color = BLACK;
						ppNode->_color = RED;

						//处理完成
						break;
					}

				}
				//如果父亲为祖父的右子树
				else
				{
					//此时叔叔为左子树。
					Node* uncle = ppNode->_left;

					if (uncle && uncle->_color == RED)
					{
						uncle->_color = parent->_color = BLACK;
						ppNode->_color = RED;

						cur = ppNode;
						parent = cur->_parent;
					}
					else
					{
						if (parent->_left == cur)
						{
							RotateR(parent);
							std::swap(cur, parent);
						}

						RotateL(ppNode);

						ppNode->_color = RED;
						parent->_color = BLACK;

						break;
					}
				}
			}

			//为了防止不小心把根节点改为红色,最后手动改为黑色即可
			_root->_color = BLACK;

			return true;
		}