红黑树详解

标签：cur parent pParent 节点详解红黑树 col

1 红黑树的概念

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

2 红黑树的性质

1. 每个结点不是红色就是黑色

2. 根节点是黑色的

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

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

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

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

3 红黑树节点的定义



enum Color
{
	RED,
	BLACK,
};

template <class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;// 节点的左孩子
	RBTreeNode<K, V>* _right; // 节点的右孩子
	RBTreeNode<K, V>* _parent;// 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)

	pair<K, V> _kv;// 节点的值域

	Color _col; // 节点的颜色

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


};

4 红黑树结构

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft 域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点，如下：

5 红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点

template<class ValueType>
 class RBTree
 {
 //……
 bool Insert(const ValueType& data)
 {
 PNode& pRoot = GetRoot();
 if (nullptr == pRoot)
 {
 pRoot = new Node(data, BLACK);
 // 根的双亲为头节点
pRoot->_pParent = _pHead;
 _pHead->_pParent = pRoot;
 }
 else
 {
 // 1. 按照二叉搜索的树方式插入新节点
// 2. 检测新节点插入后，红黑树的性质是否造到破坏，
//若满足直接退出，否则对红黑树进行旋转着色处理
}
 // 根节点的颜色可能被修改，将其改回黑色
pRoot->_color = BLACK;
 _pHead->_pLeft = LeftMost();
 _pHead->_pRight = RightMost();
 return true;
}
 private:
 PNode& GetRoot(){ return _pHead->_pParent;}
 // 获取红黑树中最小节点，即最左侧节点
PNode LeftMost();
 // 获取红黑树中最大节点，即最右侧节点
PNode RightMost();
 private:
 PNode _pHead;
};

2. 检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一: cur为红，p为红，g为黑，u存在且为红

cur和p均为红，违反了性质三，此处能否将p直接改为黑？

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，

p为g的右孩子，cur为p的右孩子，则进行左单旋转

p、g变色--p变黑，g变红

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑

针对每种情况进行相应的处理即可。

bool Insert(const ValueType& data)
 {
 // ...
 // 新节点插入后，如果其双亲节点的颜色为空色，则违反性质3：不能有连在一起的红色结点
while(pParent && RED == pParent->_color)
 {
 // 注意：grandFather一定存在
// 因为pParent存在，且不是黑色节点，则pParent一定不是根，则其一定有双亲
PNode grandFather = pParent->_pParent;
 // 先讨论左侧情况
if(pParent == grandFather->_pLeft)
 {
 PNode unclue = grandFather->_pRight;
 // 情况三：叔叔节点存在，且为红
if(unclue && RED == unclue->_color)
 {
 pParent->_color = BLACK;
 unclue->_color = BLACK;
 grandFather->_color = RED;
 pCur = grandFather;
 pParent = pCur->_pParent;
 }
 else
 {
 // 情况五：叔叔节点不存在，或者叔叔节点存在且为黑
if(pCur == pParent->_pRight)
 {
 _RotateLeft(pParent);
 swap(pParent, pCur);
 }
 }
 // 情况五最后转化成情况四
grandFather->_color = RED;
 pParent->_color = BLACK;
 _RotateRight(grandFather);
 }
 else
        {
        }
 }
 // ...
 }

我的代码

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);
	if (parent->_kv.first > kv.first)
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_right = cur;
		cur->_parent = parent;
	}
	cur->_col = RED;
	while (parent && parent->_col == BLACK)
	{
		Node* grandfather = parent->_parent;
		if (grandfather == nullptr)
			break;
		if (grandfather->_left == parent)
		{
			Node* uncle = grandfather->_right;
			if(uncle && uncle->_col==RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				//继续向上处理
				cur = parent;
				parent = cur->_parent;
			}
			else
			{
				//双旋
				if (cur == parent->_right)
				{
					RotateL(parent);
					swap(cur, parent);
				}

				RotateR(grandfather);
				grandfather->_col = RED;
				parent->_col = BLACK;

				break;
			}
		
		}
		else
		{
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				//继续向上处理
				cur = parent;
				parent = cur->_parent;
			}
			else
			{
				if (cur == parent->_left)
				{
					RotateR(parent);
					swap(parent, cur);
				}
				RotateL(grandfather);
				grandfather->_col = RED;
				parent->_col = BLACK;


				break;
			}

		}
		

	}

	_root->_col = BLACK;
	return true;

}
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;


	parent->_left = subRL;
	if (subRL)
		subRL->_parent = parent;

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

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

		subR->_parent = pparent;
	}


}

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

	parent->_left = subLR;
	if (subLR)
		parent = subLR->_parent;

	subL->_right = parent;
	Node* pparent = parent->_parent;
	subL = parent->_parent;

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

		subL->_parent = pparent;
	}

	
}

6 红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

2. 检测其是否满足红黑树的性质

bool IsValidRBTree()
{
	Node* pRoot = _root;
	// 空树也是红黑树
	if (nullptr == pRoot)
		return true;
	// 检测根节点是否满足情况
	if (BLACK != pRoot->_col)
	{
		cout << "违反红黑树性质二：根节点必须为黑色" << endl;
		return false;
	}
	// 获取任意一条路径中黑色节点的个数
	size_t blackCount = 0;
	Node* pCur = pRoot;
	while (pCur)
	{
		if (BLACK == pCur->_col)
			blackCount++;
		pCur = pCur->_left;
	}
	// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
	size_t k = 0;
	return _IsValidRBTree(pRoot, k, blackCount);
}

bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
{
	//走到null之后，判断k和black是否相等
	if (nullptr == pRoot)
	{
		if (k != blackCount)
		{
			cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
			return false;
		}
		return true;
	}
	// 统计黑色节点的个数
	if (BLACK == pRoot->_col)
		k++;
	// 检测当前节点与其双亲是否都为红色
	Node* pParent = pRoot->_parent;
	if (pParent && RED == pParent->_col && RED == pRoot->_col)
	{
		cout << "违反性质三：没有连在一起的红色节点" << endl;
		return false;
	}
	return _IsValidRBTree(pRoot->_left, k, blackCount) &&
		_IsValidRBTree(pRoot->_right, k, blackCount);
}

7 红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($log_2 N$)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

标签：cur,parent,pParent,节点,详解,红黑树,col
From： https://blog.csdn.net/weixin_66400112/article/details/139427057