[数据结构]详解红黑树

发布于：2025-07-06 ⋅ 阅读:(34) ⋅ 点赞:(0)

一、红黑树概念

红黑树是一棵二叉搜索树，他的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。 通过对任何一条从根到叶子的路径上各个结点的颜色进⾏约束，红黑树确保没有一条路径会⽐其他路径长出2倍，因而是接近平衡的。

1.1 红黑树规则

  1. 每个结点不是红色就是黑色
  2. 根结点是黑色的
  3. 如果⼀个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意⼀条路径不会有连续的红色结点。
  4. 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点

在这里插入图片描述

1.2 如何保证最长路径不超过最短路径的2倍

这里由红黑树的规则来进行限制，在极端情况下最短路径全是黑结点，因不会存在红节点连续情况下，所以最长路径结点必然是一黑一红交替，所以极端情况下最长路径长度是最短路径的二倍

二、红黑树实现

2.1 红黑树结构

对于红黑树的结构，采用AVL数的三叉链实现方式，只不过，AVL树是采用平衡因子来控制平衡的，红黑树是采用红黑结点来控制平衡的。

enum Colour
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K,V>* _left;
	RBTreeNode<K,V>* _right;
	RBTreeNode<K,V>* _parent;
	Colour _col;

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

2.2 插入

红黑树的插入过程和AVL树类似，大于当前结点去右边，小于当前结点去左边。

红黑树插入结点的逻辑分为三步：

  1. 按二叉搜索树的插入方法，找到待插入位置。
  2. 将待插入结点插入到树中。
  3. 若插入结点的父结点是红色的，则需要对红黑树进行调整。

插入完毕后，就要来维持平衡了，那么，什么情况下需要来维持平衡呢？当然是由红黑树规则确定，通过查阅规则可知：只有当红结点连续时，才会进行调整。那么该如何调整呢？难道只是简单将父亲结点变颜色吗？如果叔叔结点是黑色的话，我们将父亲变为红色，是不是会引发不同路径黑色结点不一致问题，所以要结合实际情况来进行处理。

2.2.1 变色

什么情况下可以进行变色处理：父亲结点和叔叔结点颜色都为红色时，便可以进行变色，然后交由上一层处理。在这里插入图片描述

在这里插入图片描述

通过这个抽象图可以看出如果父亲结点和叔叔结点均为红色进行变色处理，然后继续对上层进行处理即可。

2.2.2 单旋+变色

当出现叔叔存在且为黑时，单纯使用变色已经无法处理了，这时我们需要进行旋转处理。若祖孙三代的关系是直线（cur、parent、grandfather这三个结点为一条直线），则我们需要先进行单旋操作，再进行颜色调整，颜色调整后这棵被旋转子树的根结点是黑色的，因此无需继续往上进行处理。在这里插入图片描述

2.2.3 双旋+变色

插入结点的叔叔不存在。如果插入前parent下面再挂黑色结点，就会导致图中两条路径黑色结点的数目不相同，而parent是红色的，因此parent下面自然也不能挂红色结点，所以说这种情况下的cur结点一定是新插入的结点。

和情况二一样，若祖孙三代的关系是直线（cur、parent、grandfather这三个结点为一条直线），则我们需要先进行单旋操作，再进行颜色调整，颜色调整后这棵被旋转子树的根结点是黑色的，因此无需继续往上进行处理。

在这里插入图片描述

说明一下： 当直线关系为，parent是grandfather的右孩子，cur是parent的右孩子时，就需要先进行左单旋操作，再进行颜色调整。

若祖孙三代的关系是折现（cur、parent、grandfather这三个结点为一条折现），则我们需要先进行双旋操作，再进行颜色调整，颜色调整后这棵被旋转子树的根是黑色的，因此无需继续往上进行处理。在这里插入图片描述

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;
    while (parent && parent->_col == RED)
    {
        Node* grandparent = parent->_parent;
        if (grandparent->_left == parent)
        {
            Node* uncle = grandparent->_right;
            if (uncle && uncle->_col == RED)
            {
                uncle->_col = parent->_col = BLACK;
                grandparent->_col = RED;
                cur = grandparent;
                parent = cur->_parent;
            }
            else
            {
                if (cur == parent->_left)
                {
                    RotateR(grandparent);
                    parent->_col = BLACK;
                    grandparent->_col = RED;
                }
                else if (cur == parent->_right)
                {
                    RotateL(parent);
                    RotateR(grandparent);
                    cur->_col = BLACK;
                    grandparent->_col = RED;
                }
                else
                {
                    assert(false);
                }
                break;
            }
        }
        else if (grandparent->_right == parent)
        {
            Node* uncle = grandparent->_left;
            if (uncle && uncle->_col == RED)
            {
                uncle->_col = parent->_col = BLACK;
                grandparent->_col = RED;
                cur = grandparent;
                parent = cur->_parent;
            }
            else
            {
                if (cur == parent->_right)
                {
                    RotateL(grandparent);
                    parent->_col = BLACK;
                    grandparent->_col = RED;
                }
                else if (cur == parent->_left)
                {
                    RotateR(parent);
                    RotateL(grandparent);
                    cur->_col = BLACK;
                    grandparent->_col = RED;
                }
                else
                {
                    assert(false);
                }
                break;
            }
        }
        else
        {
            assert(false);
        }
    }
    _root->_col = BLACK;
    return true;
}

void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    if (subRL)
        subRL->_parent = parent;
    Node* parentParent = parent->_parent;
    if (parentParent == nullptr)
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        if (parent == parentParent->_left)
        {
            parentParent->_left = subR;
        }
        else
        {
            parentParent->_right = subR;
        }
        subR->_parent = parentParent;
    }
}

void RotateR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR)
        subLR->_parent = parent;
    Node* parentParent = parent->_parent;
    if (parentParent == nullptr)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if (parent == parentParent->_left)
        {
            parentParent->_left = subL;
        }
        else
        {
            parentParent->_right = subL;
        }
        subL->_parent = parentParent;
    }
}

2.3 查找

红黑树的查找函数与二叉搜索树的查找方式一模一样，逻辑如下：

  • 若树为空树，则查找失败，返回nullptr。
  • 若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
  • 若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
  • 若key值等于当前结点的值，则查找成功，返回对应结点。
Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < key)
		{
			cur = cur->_right;
		}
		else if (cur->_kv.first > key)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}

	return nullptr;
}

2.4 验证

这里获取最长路径和最短路径，检查最长路径不超过最短路径的2倍是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。所以我们还是去检查4点规则，满足这4点规则，一定能保证最长路径不超过最短路径的2倍。

  1. 规则1枚举颜色类型，天然实现保证了颜色不是黑色就是红色。
  2. 规则2直接检查根即可
  3. 规则3前序遍历检查，遇到红色结点查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲的颜色就方便多了。
  4. 规则4前序遍历，遍历过程中用形参记录跟到当前结点的blackNum(黑色结点数量)，前序遍历遇到4黑色结点就++blackNum，走到空就计算出了一条路径的黑色结点数量。再任意一条路径黑色结点数量作为参考值，依次比较即可。
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);
}

三、代码总览

完整代码

#pragma once
#include <assert.h>
enum Colour
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K,V>* _left;
	RBTreeNode<K,V>* _right;
	RBTreeNode<K,V>* _parent;
	Colour _col;

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

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	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;
		while (parent && parent->_col == RED)
		{
			Node* grandparent = parent->_parent;
			if (grandparent->_left == parent)
			{
				Node* uncle = grandparent->_right;
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandparent->_col = RED;
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else if (cur == parent->_right)
					{
						RotateL(parent);
						RotateR(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						assert(false);
					}
					break;
				}
			}
			else if (grandparent->_right == parent)
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandparent->_col = RED;
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else if (cur == parent->_left)
					{
						RotateR(parent);
						RotateL(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						assert(false);
					}
					break;
				}
			}
			else
			{
				assert(false);
			}
		}
		_root->_col = BLACK;
		return true;
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		Node* parentParent = parent->_parent;
		if (parentParent == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		Node* parentParent = parent->_parent;
		if (parentParent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}
			subL->_parent = parentParent;
		}
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	int Height()
	{
		return _Height(_root);
	}

	int Size()
	{
		return _Size(_root);
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

	bool IsBalance()
	{
		if (_root == nullptr)
			return true;

		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);
	}

private:

	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);
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	int _Size(Node* root)
	{
		if (root == nullptr)
			return 0;

		return _Size(root->_left) + _Size(root->_right) + 1;
	}

private:
	Node* _root = nullptr;
};

完!

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布