红黑树（RBTree）

2024-08-24 13:50:12 浏览数 (2)

文章目录

  • 红黑树概念
  • 红黑树的性质
  • 红黑树节点定义
  • 红黑树的插入
    • 情况一: cur为红，p为红，g为黑，u存在且为红
    • 情况二: cur为红，p为红，g为黑，u不存在
    • 情况三: cur为红，p为红，g为黑，u存在且为黑
    • 插入完整代码
  • 红黑树验证
  • 红黑树与AVL树的比较
  • 红黑树的应用

红黑树概念

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

最长路径<=最短路劲*2

AVL树严格平衡因子，需要更多的旋转；红黑树近似平衡

红黑树的性质

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（不存在连续的红色节点）
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点（每条路劲都存在相同数量的黑色节点）
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

最短：全黑，最长：一黑一红

红黑树节点定义

代码语言：javascript复制
enum Colour
{
	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;
	Colour _col;

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

红黑树和AVL树一样，都是三叉链，需要做孩子节点和父亲节点，红黑树还需要记录每个节点的颜色，因此需要一个_col

红黑树的插入

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

  1. 按照二叉搜索的树规则插入新节点
  2. 检测新节点插入后，红黑树的性质是否造到破坏

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

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

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

上图所示，cur节点和p节点都是红色，违反了上述性质3.解决方式：将p节点和u节点变成黑色，g节点变成红色。g可能是这棵树的子树，如果不变红，这个子树路径黑色节点的数量都 1，破坏了性质4。

  • 如果g为根节点，调整完成后需要将g改成黑色
  • 如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续往上调整，原来的g变成cur。g的双亲如果是黑色，直接结束即可。

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

如果u节点不存在，则cur一定是新插入的节点，因为如果cur不是新插入的节点，则cur和p一定有一个节点的颜色相同，就不满足性质4。

解决方式：将p改为黑，g改为红，然后进行旋转 p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转

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

如果u节点存在且为黑，cur原来的节点一定是黑色的，现在看到红色是由情况一变过来的。

解决方式：将p改为黑，g改为红，然后进行旋转 p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转

插入完整代码

代码语言：javascript复制
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;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;

	// parent的颜色是黑色也结束
	while (parent && parent->_col == RED)
	{
		// 关键看叔叔
		Node* grandfather = parent->_parent;
		if (parent == grandfather->_left)
		{
			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   u
					// c 
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//      g  
					//   p     u
					//      c 
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}
		else
		{
			Node* uncle = grandfather->_left;
			// 叔叔存在且为红，-》变色即可
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else // 叔叔不存在，或者存在且为黑
			{
				// 情况二：叔叔不存在或者存在且为黑
				// 旋转 变色
				//      g
				//   u     p
				//            c
				if (cur == parent->_right)
				{
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//		g
					//   u     p
					//      c
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}
	}

	_root->_col = BLACK;

	return true;
}

红黑树验证

  1. 如果一个节点是红色的，则它的两个孩子结点是黑色的（不存在连续的红色节点）
  2. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点（每条路劲都存在相同数量的黑色节点） 性质3、4性质验证：遍历节点，遇到红色检查父亲是不是红色；每条路径都有相同数量黑色节点。

封装一个检查函数：

代码语言：javascript复制
bool Check(Node* root, int blackNum, const int refNum)
{
	if (root == nullptr)
	{
		//cout << blackNum << endl;
		if (refNum != blackNum)
		{
			cout << "存在黑色节点的数量不相等的路径" << endl;
			return false;
		}

		return true;
	}

	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout << root->_kv.first << "存在连续的红色节点" << endl;
		return false;
	}

	if (root->_col == BLACK)
	{
		blackNum  ;
	}

	return Check(root->_left, blackNum, refNum)
		&& Check(root->_right, blackNum, refNum);
}

判断是否平衡：

代码语言：javascript复制
bool IsBalance()
{
	if (_root->_col == RED)
	{
		return false;
	}

	int refNum = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			  refNum;
		}

		cur = cur->_left;
	}

	return Check(_root, 0, refNum);
}

红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(

log_2 N

)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树的应用

  1. C STL库 – map/set、mutil_map/mutil_set
  2. Java 库
  3. linux内核
  4. 其他一些库
parent return root 搜索 存储

0 人点赞