RBTree（红黑树）模拟实现（插入）

目录

红黑树的性质

红黑树的模拟插入

叔叔存在且为红色

叔叔不存在

旋转情况​​​​​​​

叔叔存在且为黑色

总结

插入实现

节点

插入逻辑

左单旋

右单旋

---

红黑树是一颗平衡搜索二叉树，但是红黑树并不像 AVL 树一样是高度平衡二叉树，任意一颗红黑树，它的子树不会超出它任意一个子树高度的二倍。

红黑树的性质

• 每个节点不是红色就是黑色
• 根节点是黑色的
• 每个叶子节点（nil 节点/空节点）都是黑色的
• 如果一个叶子节点是红色的，那么它的孩子节点都必须是黑色的
• 任意一条路径上包含的黑色节点的数量都是相等的

其中，红黑树的平衡，就是由上面五条决定的。但是这里看到上面的五条并没有提到高度等字眼，红黑树也并不靠高度来维持平衡。

所以通过上面的条件，红黑树的高度虽然比 AVL 树的高度要高，但是红黑树的旋转次数是要比 AVL 树的少的，对于计算机而言，虽然高度可能比 AVL 树高，但是就搜索树的搜索时间复杂度为 O(log n) 来说，即使是红黑树的高度要相差二倍，那么时间复杂度最差也就是 O(log 2n) ，而对于计算机来说，这点时间并不算什么。

红黑树的模拟插入

红黑树的插入也是有几种情况，这几种情况分别需要不同的对待，所以下面我们看一下。

但是在插入之前，我们先想个问题，我们在插入的时候是插入红色节点呢？还是黑色节点？

• 如果我们插入黑色节点，那么单条路径上的黑色节点的个数就变化了，所以我们还需要去修改其他路径的黑色节点，所以插入黑色节点的话，需要修改的节点数比较多
• 插入红色节点，插入红色节点的话，我们的红黑树可能就不满足了，因为如果插入节点的父亲节点是红色的，那么就不满足红色节点的孩子节点必须是黑色的，所以这时候我们就需要对它的父亲节点进行修改颜色，或者是它的叔叔，并不会像插入黑色节点那样，需要对其他的路径都做修改
• 所以，如果我们插入黑色节点的话，需要调整的工作量就比较大，但是如果我们插入红色节点的话，是有可能是不需要调整的，因为可能插入的节点的父亲节点就是黑色的，就算插入的父亲节点是红色的，那么也只需要修改它的父亲节点，或者是叔叔节点

叔叔存在且为红色

这里有一颗红黑树：

 假设我们现在要插入的节点是 21：

这时候，我们看到 cur 位置已经插入了节点 21，但是插入之后，该红黑树违反了，“红色节点的孩子节点必须是黑色的” 这一条规定，所以为例维持红黑树，我们需要对其进行变色，或者是旋转等操作来使其依旧是红黑树。

既然上面违反了 “红色几点的孩子节点必须是黑色的”，那么我们在看一下，cur 有没有叔叔节点，如果有的话，那么我们在看一下叔叔节点的颜色是不是红色的，如果都满足的话，那么下面我们就把父亲节点和叔叔节点都变为黑色的，然后把祖父节点变为红色，这样的话，这两条路径的黑色节点数量就不变了：

但是这里变色结束后，我们看到祖父节点是红色的，祖父节点的父亲节点也是红色的，所以我们可以继续刚才的步骤，知道祖父节点的颜色变为黑色，或者是祖父节点没有父亲节点，或者是其他情况的时候就结束，所以这时候，我们将祖父节点赋值给 cur 节点，然后继续啊上面的循环：

这时候，我们的祖父节点没有父亲节点，也就表示祖父节点就是根了，那么也就可以跳出循环，不过跳出循环后，我们的根节点不满足“根节点是黑色的”，这一条规定，所以出了循环之后，我们可以把根节点置为黑色：

在这样变色之后，该红黑树还是红黑树。

上面就是叔叔存在且为红色的情况。

叔叔不存在

如果是这种情况的话，那么就是叔叔不存在的情况，我们已经插入了 cur 节点，而这时候就是叔叔不存在的情况，那么这时候就不能靠改变父亲的颜色来维持红黑树了，因为这里只把父亲的颜色改变后和把祖父的颜色改变后，那么最右边的路径上黑色节点的数量就变少了，与其他路径的黑色节点的数量不同，所以不能光改变父亲和祖父的颜色，这时候就需要旋转加变色，那么怎么样旋转？这里我们可以对 grandparent 节点进行右单旋，然后将 parent 节点变为黑色，祖父节点变为红色：

 下一步就是将祖父节点变为红色，父亲节点变为黑色：

经过这样的旋转和变色之后，该树还是红黑树，不过刚才使用的是右单旋，那么怎么样判断是左单旋，还是右单旋，亦或者是右左双旋，或者是左右双旋？

旋转情况

在红黑树的旋转的判断条件并不是高度，而是看 cur parent 以及 grandparent 三个节点的位置。

1. 如果 parent 是 grandparent 的 left ，并且 cur 也是 parent 的 left ，那么就使用的是右单旋

2. 如果 parent 是 grandparent 的 right，并且 cur 也是 parent 的 right，那么就使用的是左单旋

3. 如果 parent 是 grandparent 的 right，并且 cur 也是 parent 的 left ，那么就使用的是右左双旋

4. 如果 parent 是 grandparent 的 left ，并且 cur 也是 parent 的 right，那么就使用的是左右双旋

所以下面我们看一下叔叔不存在，双旋的情况：

这时候，我们插入的节点是 24 这个节点，然后我们发现叔叔不存在，所以我们需要使用旋转加变色的方案，我们发现 parent 是 grandparent 的左，而 cur 是 parent 的右，所以我们需要使用左右双旋：

先对 parent 进行左单旋

 在对 grandparent 进行右单旋

旋转结束后，我们发现颜色不正确，所以我们在这种情况下，需要将grandparent 变为 红色，然后将 cur 变为 黑色。

叔叔存在且为黑色

上面就是叔叔存在且为黑色，我们到 cur 位置插入，但是这里我们先进行叔叔存在且为红色，所以我们向上跟新：

到这时候，就变成叔叔存在且为黑色了，所以这时候我们也不能单靠变色来解决问题，我们需要旋转加变色。

这时候的旋转也是按照上面的规则来的，我们看到parent 是 grandparent 的 右边，cur 是 parent 的右边所以这时候我们使用的是左单旋：

旋转结束后就是这个样子，但是颜色并不符合红黑树，所以我们还需要变色来处理，这种情况下，我们只需要把 grandparent 变为红色，父亲变为黑色：

其实叔叔不存在和叔叔存在且为黑色的情况是相同的，如果是单旋的话，那么就是旋转结束后，将付清的颜色变为黑色，然后将祖父的颜色变为红色，如果是双旋的话，那么就是将 cur 的颜色变为黑色，祖父的颜色变为红色。

下面看一下双旋的情况

这时候 cur 还是插入的节点，这时候我们跟新一次，然后就可以达到叔叔存在且为黑色，并且还是双旋的情况：

 此时就是叔叔存在且为黑色，并且我们发现 parent 是grandparent 的右边，cur 是 parent 的左边，所以这里我们使用的是右左双旋：

对 parent 进行右单旋

在对 grandparent 使用左单旋转

 这时候，就是将 grandparent 变为红色，然后将 cur 变为 黑色，所以我们在模拟插入后，发现叔叔不存在和存在且为黑的情况是一样的，所以我们后面就可以将叔叔存在且为红色分为一类，和叔叔不存在，或者存在且为黑色，分为一类，将这两类分开处理。

总结

旋转规则上面以及说过了，下面说一下变色：

1. 单旋情况下，将 grandparent 变为红色， parent 变为黑色

2. 双旋情况下，将 grandparent 变为红色， cur 变为黑色

插入实现

节点

• 红黑树同样是kv结构，所以需要一个存储kv的变量
• 既然是红黑树，那么除了三叉链，当然还需要一个颜色来控制

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

插入逻辑

	bool insert(const pair& kv)
	{
		if (_root == nullptr)
		{
			// 根节点为空，插入到根节点
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
 
		Node* cur = _root, *parent = nullptr;
		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->_parent = parent;
		if (parent->_kv.first < kv.first)
			parent->_right = cur;
		else
			parent->_left = cur;
 
		// 维护红黑树
		//当父亲不为空，并且父亲的颜色是红色就继续调整
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				// parent 是 grandfather 的左边
				//       g
				//    p
				Node* uncle = grandfather->_right;
				// 如果叔叔存在，且叔叔的颜色为红色
				// 那么就将叔叔和父亲的颜色全都改为黑色，然后将祖父的颜色改为红色
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					//向上迭代
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					// 叔叔不存在或者叔叔存在但是叔叔的颜色为黑色
					if (cur == parent->_left)
					{
						//         g
						//     p
						//  c
						//右单旋
						RotateR(grandfather);
						//将父亲的节点变为黑色，祖父的节点变为红色
						parent->_col = BLACK;
						grandfather->_col = RED;
						break;
					}
					else
					{
						//     g
						//  p
						//     c
						//左右双旋
						RotateL(parent);
						RotateR(grandfather);
						//将cur 的颜色变为黑色，祖父的节点变为红色
						cur->_col = BLACK;
						grandfather->_col = RED;
						break;
					}
				}
			}
			else
			{
				// parent 是 grandfather 的右边
				//     g
				//        p
				Node* uncle = grandfather->_left;
				// 如果叔叔存在，且叔叔的颜色为红色
				// 那么就将叔叔和父亲的颜色全都改为黑色，然后将祖父的颜色改为红色
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					//向上迭代
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					// 叔叔不存在或者叔叔存在但是叔叔的颜色为黑色
					if (cur == parent->_right)
					{
						//    g
						//       p
						//          c
						//左单旋
						RotateL(grandfather);
						//将父亲的节点变为黑色，祖父的节点变为红色
						parent->_col = BLACK;
						grandfather->_col = RED;
						break;
					}
					else
					{
						//       g
						//           p
						//       c
						//右左双旋
						RotateR(parent);
						RotateL(grandfather);
						//将cur 的颜色变为黑色，祖父的节点变为红色
						cur->_col = BLACK;
						grandfather->_col = RED;
						break;
					}
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}

而旋转，我们以及在 AVL 就以及说过了，树的旋转是搜索树的旋转规则，并不是AVL 树或者红黑树特有的，所以旋转是通用的，只是红黑树的旋转不需要维持平衡因子，只需要旋转即可。

左单旋

	// 左单旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curLeft = cur->_left;
 
		parent->_right = curLeft;
		if (curLeft)
		{
			curLeft->_parent = parent;
		}
		cur->_left = parent;
		Node* pparent = parent->_parent;
		parent->_parent = cur;
		if (pparent == nullptr)
		{
			// parent 就是根节点
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (parent == pparent->_left)
			{
				pparent->_left = cur;
			}
			else
			{
				pparent->_right = cur;
			}
			cur->_parent = pparent;
		}
	}

右单旋

	//右单旋
	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curRight = cur->_right;
 
		parent->_left = curRight;
		if (curRight)
		{
			curRight->_parent = parent;
		}
		cur->_right = parent;
		Node* pparent = parent->_parent;
		parent->_parent = cur;
		if (pparent == nullptr)
		{
			// 说明 parent 是根节点
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (parent == pparent->_left)
			{
				pparent->_left = cur;
			}
			else
			{
				pparent->_right = cur;
			}
			cur->_parent = pparent;
		}
	}