C++从零开始(day50)——RBTree模拟实现

这是关于一个普通双非本科大一学生的C++的学习记录贴

在此前，我学了一点点C语言还有简单的数据结构，如果有小伙伴想和我一起学习的，可以私信我交流分享学习资料

那么开启正题

今天分享的是关于RBTree模拟实现

1.RBTree概念

RBTree（红黑树），是一种二叉搜索树，在每个结点增加一个存储标识结点颜色，可以是RED或者BLACK（因而得名），通过对任意一条叶子路径上的各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而使近似平衡的

2.RBTree的性质

1.根节点是黑色的 

2.没有相邻的红结点

3. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 

4. 每个空结点都是黑色的

3.RBTree结点的定义

RBTree结点是一种三岔链，不仅存储了左右子树结点的指针，还要存储父亲结点的指针，当然还要存储结点颜色以及pair

enum Colour
{
	BLACK,
	RED
};
 
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
 
	pair<K, V> _kv;
	Colour _col;
 
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
		, _kv(kv)
	{}
};

4.RBLTree的插入

4.1插入流程

RBTree树插入数据可以分为两步

1.按照二叉搜索树的方式插入新结点

2.调整结点的颜色

在调节颜色时，有时需要旋转处理，旋转方式和我们刚学的AVLTree旋转方式一样

4.2插入情况

先按照二叉搜索树进行插入，当然注意颜色的处理

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 < kv.first)
	{
		parent->_right = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
 
 
    //。。。。。    
 
	_root->_col = BLACK;
 
	return true;
}

4.2.1叔叔为红色

当叔叔为红色时，把叔叔父亲变为黑，祖父变为红，往上继续迭代即可

4.2.1叔叔为黑色或不存在

当叔叔叔叔为黑色或不存在时，要进行旋转，旋转完成调色后，退出循环

while (parent && parent->_col == RED)
{
	Node* grandfater = parent->_parent;
	if (parent == grandfater->_left)
	{
		Node* uncle = grandfater->_right;
		// 情况一  uncle存在且为红
		if (uncle && uncle->_col == RED)
		{
			parent->_col = uncle->_col = BLACK;
			grandfater->_col = RED;
 
			cur = grandfater;
			parent = cur->_parent;
		}
		else
		{
			if (cur == parent->_left)
			{
				// 情况二
				RotateR(grandfater);
				parent->_col = BLACK;
				grandfater->_col = RED;
			}
			else
			{
				// 情况三
				RotateL(parent);
				RotateR(grandfater);
				cur->_col = BLACK;
				grandfater->_col = RED;
			}
 
			break;
		}
	}
	else // (parent == grandfater->_right)
	{
		Node* uncle = grandfater->_left;
		if (uncle && uncle->_col == RED)
		{
			parent->_col = uncle->_col = BLACK;
			grandfater->_col = RED;
 
			cur = grandfater;
			parent = cur->_parent;
		}
		else
		{
			//   g                
			//      p
			//         c
			if (cur == parent->_right)
			{
				RotateL(grandfater);
				parent->_col = BLACK;
				grandfater->_col = RED;
			}
			else
			{
				//   g                
				//      p
				//   c
				RotateR(parent);
				RotateL(grandfater);
				cur->_col = BLACK;
				grandfater->_col = RED;
			}
 
			break;
		}
	}
}

注意：：完成后，根可能为红色（违反红黑树性质），要处理为黑色

当然红黑树还有其他函数，以及迭代器，这些在后面模拟实现map和set里再深入探究

新手写博客，有不对的位置希望大佬们能够指出，也谢谢大家能看到这里，让我们一起学习进步吧！