目录

一.红黑树概述

二.红黑树的性质

​编辑 三.构建红黑树模拟实现

插入新节点情况分析

情况一、cur为红色，parent为红色，grandfather为黑色，uncle存在且为红

情况二、cur为红色，parent为红色，grandfather为黑色，uncle不存在

单旋的解决方案

双旋的解决方案 

情况三、cur为红色，parent为红色，grandfather，uncle存在且为黑色

单旋的解决方案 

双旋的解决方案

完整插入节点和调整的代码

四、红黑树检测

---

一.红黑树概述

红黑树也是一种二叉搜索树，在二叉搜索树的基础上它也定义了一些规则来使平衡树相对平衡。AVL树是通过左右高度差（平衡因子）来控制搜索树的平衡，构建出来是非常接近完全二叉树和满二叉树的树。而红黑树是一种相对平衡，最长路径不超过最短路径的两倍就可以了，红黑树在每个结点上增加一个存储位表示节点的颜色，可以是红色也可以是黑色，通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑色树确保没有一条路径会比其他路径长出两倍，从而达到相对平衡。相同之处在于红黑树也要用到旋转来调整节点，但是旋转的次数要少一点（因为触发旋转的条件放松了）

二.红黑树的性质

（1）、每个节点不是黑色就是红色

（2）、根节点是黑色的

（3）、如果一个节点是红色的，则它的两个孩子节点必须是黑色的（不能有连续的红色节点）

（4）、对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点（每条路径上的黑色节点数量相同）

（5）、每个叶子节点都是黑色的（此处的叶子节点指空节点）

为什么从这五条性质就可以限制了最长路径中的节点个数不会超过最短路径节点个数的两倍

首先最短路径节点个数是可以算红色节点也可以算黑色节点个数的，但是因为第四条性质限制了黑色节点数量，如果这棵树限制了黑色节点只能有两个，那么无疑两个都是黑色节点就是最短节点（此时最短路径节点个数是2）。如果非要加入红色节点，那么要么是在两个黑色节点后面加上红节点（因为要保证必须有两个黑色节点，但是此时节点个数变为3了，远不如只有两个黑色节点的情况），要么就得为了保证最短路径的情况下减去一个黑色节点，改为加上红色节点（此时该条路径的节点个数也为2，正好持平两个黑色节点的情况），但是这样就不足必须两个黑色节点的数量的限制。所以最短路径只能是整条路径都是黑色节点

最长路径只能是一黑一红间隔了，性质三限制了不能有连续的红色节点，而性质四限制了如果连续黑色节点肯定不能是最长节点，所以黑色间隔红色节点才是最合适的

 三.构建红黑树模拟实现

 首先要明确的是新插入节点的颜色一定是先是红色的，虽然父节点可能也是红色的（破坏了性质三），但是新节点是红色的只会影响到从根节点到新插入节点的这一条路径的节点，所以只需要调整这一条路径就可以了。但是如果新插入节点颜色是黑色，那么因为性质四限制了所有路径的黑色节点数量相同，而此时在这条路径上加了一个黑色节点意味着所有路径都要想办法加一个黑色节点，这样代价就非常大了

插入新节点情况分析

情况一、cur为红色，parent为红色，grandfather为黑色，uncle存在且为红

如果d、e为空，那么就意味着a、b、c一定为空，cur一定是新插入节点，因为只有这样才能黑色节点数量相等

但是此时cur和parent都为红，破坏了性质三不能有连续的红节点，解决办法就是parent和uncle都直接变黑，grandfather变为红。为什么grandfather要变为红而不是黑呢，因为当前这种解决方法实际上是grandfather的所有孩子路径都加了一个黑色节点，但是grandfather又不一定是根节点，此时是破坏了性质四，所以要往上处理把其余路径的黑色节点数量做一个调整。如果grandfather就是根节点的话，那就不需要往上更新了，因为所有的路径相当于已经都加了一个黑色节点了

 如果d、e有一个黑色节点，那么说明a、b、c、d必定也有一个黑色节点，此时cur不是新增节点，而是通过上面那种情况变换而来的grandfather节点，也就是说此时是上面那种grandfather节点不是根节点还需往上处理的情况。此时uncle还是存在而且为红色，处理方法也是parent和uncle节点都变黑，grandfather节点变红，继续往上处理

 

所以总结一下，如果cur存在且为红，parent也为红，grandfather为黑，uncle节点存在且为黑，那么解决办法都是parent和uncle变为黑色，grandfather节点变为红色，往上接着处理 

情况二、cur为红色，parent为红色，grandfather为黑色，uncle不存在

此时cur一定是新增节点，因为如果不是新增节点，要么cur是之前情况一转变而来变为红色的grandfather节点，而情况一的一个大前提是grandfather节点是黑色的，此时u不存在说明右边一个黑色节点都没有，而左边却多一个黑色节点，这样就破坏性质四了，所以cur一点是新增节点为红色。

那么怎么解决连续的红色呢，此时是一边高，一边低，直接染为黑色是无法解决问题的，所以要用到旋转。而此时判断单旋还是双旋就只是看cur是parent的那个孩子，如果parent是grandfather节点的左孩子，而cur也是parent的左孩子，那么这时候就只是左边高右边低而已，所以直接右单旋就可以了。而如果parent是grandfather的左孩子，但是cur是parent的右孩子的话，此时不是单纯的左边高，所以需要先左单旋使它变为单纯一边高，然后整体进行右单旋。反过来，如果parent是grandfather节点的右孩子，而cur也是parent的右孩子，那么这时候就只是右边高左边低而已，所以直接左单旋就可以了。而如果parent是grandfather的右孩子，但是cur是parent的左孩子的话，此时不是单纯的右边高，所以需要先右单旋使它变为单纯一边高，然后整体进行左单旋。

单旋的解决方案

单旋parent上去当根节点，而grandfather下来当孩子节点，其实就是parent和grandfather换了个位置和颜色，而此时压根就没有加黑色节点，所以不需要往上进行处理节点

双旋的解决方案 

旋转完染色只有cur和grandfather进行染色就可以了，parent可以不用动

情况三、cur为红色，parent为红色，grandfather，uncle存在且为黑色

请注意此时cur为红色是原本是黑色，但是下面的子树里插入新节点导致cur变色变为红色了，而此时parent也是红色，此时有连续的红色节点了，所以必须进行调整处理。情况三的处理方案和情况二的处理方案一样，所以很多人会把情况二三放到一块去讲

 

上图的抽象图里，如果d、e子树都为空的话，c是必须要有一个黑色节点的，a、b可以为空，也可以只为红色节点，但是不能有黑色节点（因为只有这样每条路径上的黑色节点数量相等）。a、b无论哪个新插入节点都会触发情况一，导致cur变红

单旋的解决方案 

单旋与情况二也类似，如果parent是grandfather的左孩子，cur是parent的左孩子，那么就直接右单旋就可以了。如果parent是grandfather的右孩子，而cur是parent的右孩子，那么就需要左单旋。单旋变色只需要parent变为黑色，grandfather变为红色就可以了

双旋的解决方案

 如果parent是grandfather的左孩子，cur是parent的右孩子，那么就需要左右双旋。如果parent是grandfather的右孩子，而cur是parent的左孩子，那么就需要右左单旋。旋转完，grandfather变为红色，cur变为黑色

完整插入节点和调整的代码

bool insert(const T& key){// 如果树为空，则插入新节点作为根节点  if (root == nullptr){root = new Node(key); // 创建新节点  root->col = black;    // 根节点总是黑色  root->_parent = nullptr; // 根节点没有父节点  }// 初始化当前节点和父节点  Node* cur = root;Node* parent = cur->_parent;// 查找插入位置  while (cur){if (key > cur->_key) // 如果新键大于当前节点的键，向右移动  {parent = cur;    // 更新父节点  cur = cur->right; // 切换到右子树  }else if (key < cur->_key) // 如果新键小于当前节点，向左移动  {parent = cur;     // 更新父节点  cur = cur->left; // 切换到左子树  }else // 如果新键等于当前节点的键，则不允许重复插入  {return false; // 插入失败  }}// 创建新节点并插入  cur = new Node(key); // 创建新节点  cur->col = red;      // 新节点初始为红色  // 将新节点链接到父节点  if (cur->_key > parent->_key) // 新节点键大于父节点键，插入右边  {parent->right = cur;   // 将新节点链接到父节点的右子节点  cur->_parent = parent; // 设置新节点的父节点  }else // 新节点键小于父节点键，插入左边  {parent->left = cur;    // 将新节点链接到父节点的左子节点  cur->_parent = parent; // 设置新节点的父节点  }// 根据红黑树性质，调整红黑树  while (parent && parent->col == red) // 检查父节点是否为红色  {Node* grandfather = parent->_parent; // 获取祖父节点  if (parent == grandfather->left) // 如果父节点是祖父节点的左子节点  {Node* uncle = grandfather->right; // 叔叔节点  if (uncle && uncle->col == red) // 再次检查叔叔节点颜色  {// 情况1：叔叔节点也为红色  uncle->col = parent->col = black; // 将父节点和叔叔节点设置为黑色  grandfather->col = red;           // 将祖父节点设置为红色  cur = grandfather;                // 继续向上调整  parent = cur->_parent;            // 更新父节点  }else // 叔叔节点为黑色  {if (cur == parent->left) // 情况2：新插入节点是父节点的左子节点  {RotateR(grandfather); // 旋转祖父节点向右  parent->col = black;  // 设置父节点为黑色  grandfather->col = red; // 设置祖父节点为红色  }else // 情况3：新插入节点是父节点的右子节点  {RotateL(parent);          // 先左旋转父节点  RotateR(grandfather);     // 再右旋转祖父节点  cur->col = black;         // 设置新节点为黑色  grandfather->col = red;   // 设置祖父节点为红色  }break; // 调整完成，退出循环  }}else // 如果父节点是祖父节点的右子节点  {Node* uncle = grandfather->left; // 叔叔节点  if (uncle && uncle->col == red) // 再次检查叔叔节点颜色  {// 情况1：叔叔节点也为红色  uncle->col = parent->col = black; // 将父节点和叔叔节点设置为黑色  grandfather->col = red;           // 将祖父节点设置为红色  cur = grandfather;                // 继续向上调整  parent = cur->_parent;            // 更新父节点  }else // 叔叔节点为黑色  {if (cur == parent->right) // 情况2：新插入节点是父节点的右子节点  {RotateL(grandfather); // 旋转祖父节点向左  parent->col = black;  // 设置父节点为黑色  grandfather->col = cur->col = red; // 设置祖父节点为红色，保持新节点为红色  }else // 情况3：新插入节点是父节点的左子节点  {RotateR(parent);          // 先右旋转父节点  RotateL(grandfather);     // 再左旋转祖父节点  grandfather->col = red;   // 设置祖父节点为红色  cur->col = black;         // 设置新节点为黑色  }break; // 调整完成，退出循环  }}}// 确保根节点始终为黑色  root->col = black;return true; // 插入成功  }

四、红黑树检测

红黑树检测一般是按两方面来进行检测的，一方面检测不能有连续的红节点，但是检查一个节点和自己的两个孩子节点是否是连续红色节点是很难的，所以反过来检测一个节点是否和自己的父节点是否都是红色就可以了。另一方面检测每条路径的黑色节点数量是否相同，首先是先循环走完一条路径查出这条路径的黑色节点的数量num，然后递归查找每一条路径黑色节点数量，每次都与事先存储好的num进行比较，如果有不一样的就说明黑色节点数量不相等

// 递归检查红黑树的性质  bool _isRBtree(const Node* root, int num, int size){// 如果当前节点是空，检查黑色节点数量  if (root == nullptr){// 如果当前黑色节点数量不等于树中应有的数量，则返回失败  if (num != size){cout << "黑色节点数量不对" << endl; // 输出错误信息  return false; // 返回 false，表示不符合红黑树性质  }return true; // 空节点，符合红黑树性质  }// 如果当前节点是黑色，增加黑色节点计数  if (root->col == black){size++; // 增加黑色节点的计数  }// 检查是否有连续的红色节点  if (root->col == red && root->_parent != nullptr && root->_parent->col == red){cout << "有连续的红色节点" << endl; // 输出错误信息  return false; // 返回 false，表示不符合红黑树性质  }// 递归检查左子树和右子树  return _isRBtree(root->left, num, size) && _isRBtree(root->right, num, size);}// 检查整个红黑树的性质  bool isRBtree(){// 根节点必须是黑色  if (root->col == red)return false; // 根节点为红色，返回 false  // 树为空，满足红黑树性质  if (root == nullptr)return true;// 从根节点开始  Node* cur = root;int num = 0; // 用于统计黑色节点数量  // 统计从根节点到最左叶子的路径中的黑色节点数量  while (cur){if (cur->col == black) // 如果当前节点是黑色  num++; // 增加黑色节点计数  cur = cur->left; // 移动到左子节点  }int size = 0; // 用于记录路径上统计到的黑色节点数量  return _isRBtree(root, num, size); // 递归检查树的性质  }

 随机插入一万个数据进行检测一下

五、时间复杂度分析

红黑树的时间复杂度与树的高度有关（也就是和路径的节点个数有关），而红黑色最短的路径可以是logn（接近满二叉树），但是最长的路径是2logn，时间复杂度是2logn。与AVL树相比，时间复杂度看上去差一点，但是2logn和logn都是一个量级的，忽略常数，都是O（logn）

从代码复杂性来看，AVL树要调多次旋转，所以个人认为AVL树复杂一点。红黑树的旋转次数比AVL树，因为它的旋转条件放松一些。但是红黑色是近似平衡，所以同量级下红黑树的高度比AVL要高很多