阅读量:0
目录
点击跳转至上一篇文章： 【C++】：AVL树的深度解析及其实现
点击跳转至文章：【C++】：二叉树进阶 — 搜索二叉树
💡前言
上一篇文章介绍了什么是AVL树和AVL树的实现，AVL树也有它的缺点：就是太过追求绝对平衡，比如在插入时要维护其绝对平衡，旋转次数太多，在删除时甚至有可能要一直旋转到根位置，使之性能低下。
本篇文章介绍的红黑树也是一种平衡树，是通过改变节点颜色以及旋转操作，使之接近平衡。
红黑树比AVL树的用途更加广泛，在一些方面效率甚至要优于AVL树，并且 map/set 的底层封装用的也是红黑树。
一，红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
二，红黑树的性质
(1) 每个结点不是红色就是黑色 ；
(2) 根节点是黑色的 ；
(3) 如果一个节点是红色的，则它的两个孩子结点是黑色的（重点）；
(4) 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（重点） ；
(5) 每个叶子结点都是黑色的(此处的叶子结点指的是空结点，这条性质可有可无，平时不关注)。
三，红黑树节点的定义
红黑树的节点结构与AVL树的大致相同，只是AVL树中有节点的颜色，没有平衡因子。
//枚举颜色 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(BLACK) {} }; 四，红黑树的插入操作
首先我们要思考一个问题，插入节点时，到底是插入红色节点还是黑色节点？为什么？
答案：插入红色节点。
因为我们知道红黑树最重要的两条性质是第(3)(4)条，通过维护这两条规则使之成为红黑树，而当新插入一个节点时，必定会破坏两条规则之一。
假设插入节点为黑色节点，则所有路径的黑色节点数量均不相同，如何让它们相同将是一个巨大的难题，而插入红色节点(此时一定是作为孩子节点)，就破坏规则(3)，但是只要根据其父亲和叔叔节点进行适当的变色就可以继续恢复规则(3)。
显而易见，规则(3)(4)就好比"慈父严母"，非要选择得罪其中一人，那当然是"慈父"了。
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
4.1 第一步
按照二叉搜索的树规则插入新节点：
bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* cur = _root; Node* parent = nullptr; while (cur) { if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else return false; } cur = new Node(kv); //新增节点，颜色为红色 cur->_col = RED; //链接时要判断链接在parent的左还是右 if (parent->_kv.first > kv.first) parent->_left = cur; else parent->_right = cur; cur->_parent = parent; //检测新节点插入后，红黑树的性质是否造到破坏 //…… } 4.2 第二步
检测新节点插入后，红黑树的性质是否造到破坏：
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
约定：
(1) cur 为当前节点，p为父节点，g为祖父节点，u为叔叔节点
(2) 下面的抽象图中，a/b/c/d/e 表示具有 n 个节点的红黑树，n >=0。
(一) 情况一: cur为红，p为红，g为黑，u存在且为红：
解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。
(二) 情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑
下面我们根据 u 的情况用具象图分别解释单旋与双旋操作：
(1) u 不存在，a/b/c/d/e都是空，cur 是新增：
p为g的左孩子，cur为p的左孩子，则进行右单旋转，再 p 变黑，g 变红：
相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转，再 p 变黑，g 变红：
p为g的左孩子，cur为p的右孩子，先针对p做左单旋转，再针对 g 做右单旋，cur 变黑，g 变红：
(2) u 存在且为黑
单旋情况：
双旋情况：
4.3 插入操作的完整代码
bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* cur = _root; Node* parent = nullptr; while (cur) { if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else return false; } cur = new Node(kv); //新增节点，颜色为红色 cur->_col = RED; //链接时要判断链接在parent的左还是右 if (parent->_kv.first > kv.first) parent->_left = cur; else parent->_right = cur; cur->_parent = parent; while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; // g // p u if (parent == grandfather->_left) { //找到u的位置 Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { //u存在且为红,把p/u变黑，g变红,继续向上调整 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { //u不存在或存在且为黑 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 { // g // u p Node* uncle = grandfather->_left; //u存在且为红,把p/u变黑，g变红,继续向上调整 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { //u不存在或存在且为黑 if (cur == parent->_right) { // g // u p // c //单旋 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)。
检测性质(3)：只要判断当前节点与其父亲节点是否为连续的红色节点；
检测性质(4)：先计算出任意一条路径上的黑色节点作为参考值，再用这个参考值与其他路径上的黑色节点数量比较。
private: //中序遍历 void InOrder() { _Inorder(_root); cout << endl; } //判断是否平衡 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; } //blackNum表示：根节点到当前节点的路径上黑色节点的数量 if (root->_col == BLACK) blackNum++; return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum); } 六，实现红黑树的完整代码
RBTree.h
#pragma once #include <iostream> #include <assert.h> using namespace std; //枚举颜色 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(BLACK) {} }; template <class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; public: Node* Find(const pair<K, V>& kv) { Node* cur = _root; while (cur) { if (cur->_kv.first > kv.first) cur = cur->_left; else if (cur->_kv.first < kv.first) cur = cur->_right; else return cur; } return nullptr; } bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* cur = _root; Node* parent = nullptr; while (cur) { if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else return false; } cur = new Node(kv); //新增节点，颜色为红色 cur->_col = RED; //链接时要判断链接在parent的左还是右 if (parent->_kv.first > kv.first) parent->_left = cur; else parent->_right = cur; cur->_parent = parent; while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; // g // p u if (parent == grandfather->_left) { //找到u的位置 Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { //u存在且为红,把p/u变黑，g变红,继续向上调整 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { //u不存在或存在且为黑 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 { // g // u p Node* uncle = grandfather->_left; //u存在且为红,把p/u变黑，g变红,继续向上调整 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { //u不存在或存在且为黑 if (cur == parent->_right) { // g // u p // c //单旋 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; } //中序遍历 void InOrder() { _Inorder(_root); cout << endl; } //判断是否平衡 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: //每个节点的位置记录一个值blackNum //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); } //右单旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; if (subLR) subLR->_parent = parent; parent->_left = subLR; subL->_right = parent; //改变之前记录 Node* ppNode = parent->_parent; parent->_parent = subL; //parent为根 if (parent == _root) { _root = subL; _root->_parent = nullptr; } else { //parent为一颗子树 if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; subL->_parent = ppNode; } } //左单旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; if (subRL) subRL->_parent = parent; parent->_right = subRL; subR->_left = parent; Node* ppNode = parent->_parent; parent->_parent = subR; //parent为根 if (parent == _root) { _root = subR; _root->_parent = nullptr; } else { //parent为一颗子树 if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; subR->_parent = ppNode; } } void _Inorder(Node* root) { if (root == nullptr) return; _Inorder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _Inorder(root->_right); } private: Node* _root = nullptr; }; //测试代码 void Test1() { //int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 }; int a[] = { 16,3,7,11,9,26,18,14,15 }; RBTree<int, int> t; for (auto e : a) t.Insert({ e ,e }); t.InOrder(); cout << t.IsBalance() << endl; } Test.cpp
#include "RBTree.h" int main() { Test1(); return 0; } 运行结果如下：
中序遍历是有序的，说明是搜索二叉树，返回1，说明满足红黑树的性质，是平衡树。
五，红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
