【初阶与进阶C++详解】第十七篇：红黑树（插入+验证+查找）

🏆个人主页：企鹅不叫的博客

​ 🌈专栏

• C语言初阶和进阶
• C项目
• Leetcode刷题
• 初阶数据结构与算法
• C++初阶和进阶
• 《深入理解计算机操作系统》
• 《高质量C/C++编程》
• Linux

⭐️ 博主码云gitee链接：代码仓库地址

⚡若有帮助可以【关注+点赞+收藏】，大家一起进步！

💙系列文章💙

【初阶与进阶C++详解】第一篇：C++入门知识必备

【初阶与进阶C++详解】第二篇：C&&C++互相调用（创建静态库）并保护加密源文件

【初阶与进阶C++详解】第三篇：类和对象上（类和this指针）

【初阶与进阶C++详解】第四篇：类和对象中（类的六个默认成员函数）

【初阶与进阶C++详解】第五篇：类和对象下（构造+static+友元+内部类

【初阶与进阶C++详解】第六篇：C&C++内存管理（动态内存分布+内存管理+new&delete）

【初阶与进阶C++详解】第七篇：模板初阶（泛型编程+函数模板+类模板+模板特化+模板分离编译）

【初阶与进阶C++详解】第八篇：string类（标准库string类+string类模拟实现）

【初阶与进阶C++详解】第九篇：vector(vector接口介绍+vector模拟实现+vector迭代器区间构造/拷贝构造/赋值)

【初阶与进阶C++详解】第十篇：list(list接口介绍和使用+list模拟实现+反向迭代器和迭代器适配)

【初阶与进阶C++详解】第十一篇：stack+queue+priority_queue+deque（仿函数）

【初阶与进阶C++详解】第十二篇：模板进阶(函数模板特化+类模板特化+模板分离编译)

【初阶与进阶C++详解】第十三篇：继承(菱形继承+菱形虚拟继承+组合)

【初阶与进阶C++详解】第十四篇：多态（虚函数+重写（覆盖）+抽象类+单继承和多继承）

【初阶与进阶C++详解】第十五篇：二叉树搜索树（操作+实现+应用KVL+性能+习题）

【初阶与进阶C++详解】第十六篇：AVL树-平衡搜索二叉树（定义+插入+旋转+验证）

---

---

💎一、红黑树概念和性质

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。它是通过控制节点颜色的方式来控制这棵树的相对平衡，最长路径的小于最短路径的2倍，这使得红黑树在最坏的情况下，也能有O(logN) 的查找效率，最短路径是全黑，最长路径是一黑一红。

红黑树的性质：

1.结点是红色或黑色。
2.根结点是黑色。
3.所有叶子都是黑色。（叶子是空结点）
4.每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
5.从任一节结点到其每个叶子的所有路径都包含相同数目的黑色结点
上面的五个性质还可以用更通俗的语言描述为三句话：

1.根节点是黑色的
2.没有连续的红节点
3.每条路径的黑节点数目相同（每条路径指的是从根节点到黑色的空节点）,一条路径上红色节点的数量一定不会超过黑色节点的数量

💎二、红黑树节点定义

本质一样是二叉搜索树，和AVL树不同的是，增加了颜色的定义

//枚举，定义颜色
enum Color
{
	RED,//0
	BLACK,//1
};


//节点类
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)
		:_kv(kv),
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_col(RED)//默认设置为红色，因为这个满足性质3且不会破坏性质4
	{}
};

💎三、红黑树结构

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
private:
	Node* _root = nullptr;
};

💎四、红黑树插入（重要）

🏆1.寻找插入的位置

若key值大于当前结点的key值，则向右寻找；若小于，则向左寻找；若相等，说明数据冗余，返回false。

🏆2.判断是否符合红黑树规则

插入的新节点默认是红色，同时要符合条路径上黑色结点数量相等这条规则，故判断是否为红黑树就转换为判断是否存在连续红色的结点，对于新插入的结点，若其父亲颜色为黑色，则满足红黑树的规则，无需调整，而若其父亲颜色为红色，则规则被破坏，需要调整。

插入节点应为什么是默认成红色？如果是黑色呢？

如果选择插入黑结点，那1条路径上就多了1个黑结点，破坏了性质5(从任一节结点到其每个叶子的所有路径都包含相同数目的黑色结点)，代价很大。插入红结点，如果它的父亲结点是黑色则不用调整，它的父亲是红色那我们在进行后序的处理。

总结一下，其实无论选红还是黑，后续都要再处理，但是处理的代价不一样：
1.插入黑色结点一定破坏性质5，调整起来会很麻烦
2.插入红结点不一定破坏红黑树的性质，它的父亲结点是红色才进行调整，比插入黑结点调整起来方便。

🏆3.破坏红黑树规则，调整节点颜色

以下用p来代表parent结点，cur代表cur为新增结点,g代表grandparent结点，u代表uncle结点。

1.1如果插入节点的父亲是黑色节点，那么可以直接结束，不需要继续调整了

1.2如果插入节点为的父亲为红色节点

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

解决方法：此时只需变色，将parent和uncle变为黑色，grandparent变为红色，同时，因为祖父之上可能还有其他节点，还需要从祖父g的位置继续向上调节。

情况二：cur在p的左边，p为红，g为黑，u存在为黑色/u不存在 （孩子，父亲，祖父呈直线状态）-单旋

分析处理：

1. 如果叔叔存在，叔叔是黑色，则此时的孩子节点可能是下面的子树在进行变色处理(情况一)时，将其从原本的黑色变为了红色。（否则不满足路径黑节点数量相同的性质），如果父亲是祖父的左孩子，孩子是父亲的左孩子，此时祖父进行右单旋。
2. 如果叔叔不存在，则此时的孩子节点是刚插入进来的结点，因为不能有连续的红结点，所以孩子和父亲必须有一个是黑色，但是此时又不满足黑节点数量相同的性质，所以进行右旋转，不用往上处理了。
3. 旋转完后，p变为黑色，g变为红色

情况三：cur在p的右边，p为红，g为黑，u存在为黑色/u不存在 (孩子，父亲，祖父呈折线状态)-双旋

分析处理：

1. 如果父亲是祖父的左孩子，孩子是父亲的右孩子，父亲此时进行左单旋，孩子再进行右单旋。

2. 如果父亲是祖父的右孩子，孩子是父亲的左孩子，父亲此时进行右单旋，孩子再进行左单旋。

3. 双旋之后，cur变为黑色，p和g为红色。

   
   旋转代码如下：

void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		// 1.先让把subR的左边（可能为空也可能不为空）作为parent的右边
		parent->_right = subRL;
		// 2.如果subRL不为空，就让subRL的父指针指向parent
		if (subRL)
			subRL->_parent = parent;
		// 3.先记录parent的父节点的位置，然后把parent作为subR的左边 
		Node* ppNode = parent->_parent;
		subR->_left = parent;
		// 4.parent的父指针指向subR
		parent->_parent = subR;
		// 5.如果ppNode为空==>说明subR现在是根节点，就让subR的父指针指向nullptr
		//不是根节点就把subR的父指针指向parent的父节点，parent的父节点（左或右）指向subR
		if (parent == _root)
		{
			// 更新根节点
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			// 判断parent是ppNode的左还是右
			if (parent == ppNode->_left)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}

			subR->_parent = ppNode;
		}
		// 6.把parent和subR的平衡因子更新为0
		subR->_bf = parent->_bf = 0;
	}
	
	void RotateR(Node* parent)
{
	//让不平衡的结点parent的左子树变为其原本左子树subL的右节点subLR
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	// 1.先让把subL的右边（可能为空也可能不为空）作为parent的左边
	parent->_left = subLR;
	// 2.如果subLR存在，就让subLR的父指针指向parent
	if (subLR)
		subLR->_parent = parent;
	// 3.先记录parent的父节点的位置，然后把parent作为subL的右边
	Node* ppNode = parent->_parent;
	subL->_right = parent;
	// 4.parent的父指针指向subL
	parent->_parent = subL;
	// 5.如果parent为根节点，则让subL成为新的根节点
	if (parent == _root)
	{
		// 更新根节点
		_root = subL;
		_root->_parent = nullptr;
	}
	//如果不是根节点，则改变subL与其祖父节点的指向关系
	else
	{
		// 判断parent是ppNode的左还是右
		if (ppNode->_left == parent)
		{
			ppNode->_left = subL;
		}
		else
		{
			ppNode->_right = subL;
		}
		subL->_parent = ppNode;
	}
	// 6.把parent和subL的平衡因子更新为0
	subL->_bf = parent->_bf = 0;
}

插入代码如下：

bool Insert(const pair<K, V>& kv)
{
  // 1、搜索树的规则插入
  // 2、看是否违反平衡规则，如果违反就需要处理：旋转
  按照二叉搜索树的规则先找到位置
  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* grandfater = parent->_parent;
    assert(grandfater);
	//如果父节点为祖父的左子树
    if (grandfater->_left == parent)
    {
      此时判断叔叔节点的状态，红黑树状态取决于叔叔
      Node* uncle = grandfater->_right;
      // 情况一：如果叔叔节点存在且为红，则直接把父亲和叔叔变黑，祖父节点边红即可。然后再从祖父的位置继续往上调整
      if (uncle && uncle->_col == RED)
      {
        // 变色
        parent->_col = uncle->_col = BLACK;
        grandfater->_col = RED;

        // 继续往上处理
        cur = grandfater;
        parent = cur->_parent;
      }
      /*
      		  叔叔节点为黑或者不存在，此时有两种情况
				情况二：cur为父节点的左子树，即直线状态， 右单旋，改p和g颜色。
				情况三：cur为父节点的右子树，即折线状态，左单旋回到情况二。
      */
      else 
      {
        if (cur == parent->_left) // 右单旋
        {
          //     g
          //   p
          // c
          RotateR(grandfater);
          parent->_col = BLACK;
          grandfater->_col = RED;
        }
        else // 双旋-左右
        {
          //     g
          //   p
          //     c 
          RotateL(parent);
          RotateR(grandfater);
          cur->_col = BLACK;
          grandfater->_col = RED;
        }

        break;
      }
    }
    //父亲在右边，叔叔在左边
    else 
    {
      Node* uncle = grandfater->_left;
      // 情况一：如果叔叔节点存在且为红，则直接把父亲和叔叔变黑，祖父节点边红即可。然后再从祖父的位置继续往上调整
      if (uncle && uncle->_col == RED)
      {
        // 变色
        parent->_col = uncle->_col = BLACK;
        grandfater->_col = RED;

        // 继续往上处理
        cur = grandfater;
        parent = cur->_parent;
      }
      /*
      		  叔叔节点为黑或者不存在，此时有两种情况
				情况二：cur为父节点的左子树，即直线状态， 左单旋，改p和g颜色。
				情况三：cur为父节点的右子树，即折线状态，右单旋回到情况二。
      */
      else
      {
        if (cur == parent->_right)//左单旋
        {
          // g
          //   p
          //     c 
          RotateL(grandfater);
          parent->_col = BLACK;
          grandfater->_col = RED;
        }
        else // 双旋-右左
        {
          // g
          //   p
          // c
          RotateR(parent);
          RotateL(grandfater);
          cur->_col = BLACK;
          grandfater->_col = RED;
        }

        break;
      }
    }
  }
  //强制转换把根变成黑
  _root->_col = BLACK;

  return true;
}

💎五、红黑树验证

🏆1.计算最小最大高度判断

两者区别，把大于号改成小于号，返回小的那个子树的高度+1。只要最大长度小于最小长度的2倍，那么基本规则就是没有破坏的

//最大长度
int _maxHeight(Node* root)
{
  if (root == nullptr)
    return 0;

  int lh = _maxHeight(root->_left);
  int rh = _maxHeight(root->_right);

  return lh > rh ? lh + 1 : rh + 1;
}
//最小长度
int _minHeight(Node* root)
{
  if (root == nullptr)
    return 0;

  int lh = _minHeight(root->_left);
  int rh = _minHeight(root->_right);

  return lh < rh ? lh + 1 : rh + 1;
}

🏆2.通过检查红黑树性质判断

1. 根节点一定是黑色
2. 不存在连续的红节点
3. 每一个到叶子（空节点NIL）的支路上黑节点数量相同

bool IsBalanceTree()
{
  // 检查红黑树几条规则
  Node* pRoot = _root;
  // 空树也是红黑树
  if (nullptr == pRoot)
    return true;

  // 检测根节点是否满足情况1，根节点是黑色
  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);
}
//检测是否为RB树
bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
{
  //先计算一条路径的黑色结点数量，然后遍历其他各条路径，对比黑色结点的数量，若不相等，则返回false。
  // 走到空就判断该条路径的黑节点是否等于blackCount
  if (nullptr == pRoot)
  {
    if (k != blackCount)
    {
      cout << "违反性质三：每条路径中黑色节点的个数必须相同" << endl;
      return false;
    }
    return true;
  }

  // 统计黑色节点的个数
  if (BLACK == pRoot->_col)
    k++;
  // 检测当前节点与其双亲是否都为红色
  //判断红色结点的父亲是否为红色，这样就可以简化代码及操作
  if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
  {
    cout << "违反性质二：存在连在一起的红色节点" << endl;
    return false;
  }

  return _IsValidRBTree(pRoot->_left, k, blackCount) &&
    _IsValidRBTree(pRoot->_right, k, blackCount);
}

💎六、红黑树查找

和二叉搜索树一样

	//因为kvl树我们需要修改value，所以返回节点的指针
	Node* _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return nullptr;

		if (root->_kv.first < key)
		{
			return _FindR(root->_right, key);
		}
		else if (root->_kv.first > key)
		{
			return _FindR(root->_left, key);
		}
		else
		{
			return root;
		}
	}
	//查找是通过key来进行的
	Node* FindR(const K& key)
	{
		return _FindR(_root, key);
	}

💎七、红黑树与AVL树比较

• AVL树是严格平衡的，而红黑树是近似平衡的
• AVL树和红黑树的查找时间复杂度都是O(logN)
• 由于红黑树旋转次数更少，因此在增删过程中性能较优，AVL更适合查找数据

💎八、红黑树应用

最为经典的便是map和set这两个容器，它们便使用了红黑树作为底层逻辑

---