C++ 红黑树的学习

目录

1.红黑树的规则

1.1红黑树的效率

1.2红黑树的结构

2.红黑树的插入

2.1只需变色

2.2单旋+变色

2.3双旋+变色

3.红黑树代码实现

3.1插入函数

3.2检验红黑树平衡

和AVL树一样，红黑树也是一种平衡二叉树，只不过保持平衡的方法不一样，通过节点的颜色来控制，红黑树顾名思义就是节点的颜色只有红色和黑色

1.红黑树的规则

红黑树的底层依旧遵循二叉搜索树的原则，也就是对于某节点来说，左子树的值均小于当前值，右子树的值均大于当前值

1.每个节点不是黑色就是红色

2.根节点一定是黑色的

3.任意一条路径上不会出现连续的红色节点

4.以每个节点为起点，到NULL节点的路径上，黑色节点的个数相同

那么对于这条规则，是如何保证这是一棵平衡二叉树的呢，我们先假设从根节点开始每条路径上存在N个黑色节点，那么要满足规则三，如果要插入红色节点，最多插入N个，且前提是每条路径上黑色节点个数相同，也就是说现在像插入节点使得路径变长只能插入红色节点，所以最长路径的长度为2N，最短路径不插入红色节点的长度为N

综上可以得出，红黑树的相对于AVL树没有那么的平衡，它的最长路径可以为最短路径的两倍，但是这样也可以得出红黑树控制平衡没那么严格，旋转次数就会少

1.1红黑树的效率

对于红黑树来说，假设总结点个数为N，最短路径的长度为h，因为最长路径最大为2h，那么先假设全部路径均为h，那么N=2^h-1，假设所有路径长度均为2h，那么N=2^2h-1，但是最起码会存在一条最短路径，所以N<2^2h-1

可以得出N的范围在[2^h-1,2^2h-1]之间，计算可得h约等于logN，所以查找的路径最短为logN，最长路径为2*logN，那么时间复杂度就是O(logN)

1.2红黑树的结构

每个节点的结构和AVL树很类似，只不过把平衡因子换成了颜色，因为红黑树通过颜色来控制树的平衡，因为只有红色和黑色，单独将颜色枚举出来，颜色的类型就是Colour

//枚举红黑树的颜色，方便控制 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) {} };

2.红黑树的插入

对于红黑树，仍然需要符合搜索二叉树的规则，所以对于一个新插入的值，我们先按照规则查找插入的位置，然后进行调整，使得整棵树仍然符合红黑树的规则

1.如果整棵树为空，插入节点时直接给黑色节点，如果原本存在节点，那么新插入的节点一定是红色，因为规则4说了每条路径上的黑色节点都是相同的，虽然规则3说明不可以存在连续的红色节点，但是规则4破坏了更加难以调整，所以选择先保证规则4的实现，规则3怎么实现后文会讲，这里先知道，插入新节点一定选择红色节点

2.当插入红色节点后，如果父亲节点是黑色，就不需要调整，否则要处理

那么对于要处理的情况来说，就是连续插入了两个红色节点，并且原来的树是符合规则的，以插入节点为当前节点，那么父亲节点是红色和爷爷节点是黑色，这两个节点的颜色已经确定，那么我们就需要讨论叔叔节点，也就是爷爷节点的另一个孩子节点，根据叔叔节点的颜色和是否存在进行调整

ps-1：讲解以下情况时，只会讲节点插入在某一侧的情况，例如只讲右旋的情况，左旋只要对照右旋的逻辑推理可得，并不是只有右旋的操作

ps-2：以下情况都是针对某棵子树，所以要先记录该子树的父亲节点，方便调整完子树和父亲节点进行连接

2.1只需变色

X是新插入节点，当叔叔节点存在并且为红色时，此时我们只需要将父亲节点和叔叔节点均变为黑色，爷爷节点变为红色即可，这样子树就是符合红黑树规则的，然后以爷爷节点作为新的“插入节点”，继续向上调整，假设调整到根节点，因为根节点一定要是黑色，直接将根节点调整为黑色即可，因为每条路径的第一个都是根节点，那么根节点调整为黑色不会影响规则2和4

以下是调整完的子树

2.2单旋+变色

当叔叔节点不存在或者叔叔节点为黑色，需要进行一次单旋并变色

例如下面这种情况，叔叔节点不存在，那么要先进行一次右旋，然后父亲节点变黑色，爷爷节点变成红色，这样才能保证每条路径黑色节点个数不变，如果只有变色的话黑色节点个数会不一致，所以要先进行旋转，左图是调整前，右图是调整后，这是叔叔节点为空的情况

继续讲叔叔节点为黑色的情况，同样需要进行单旋和变色，例如下面这样，此时X不可能是新插入的节点，应当是底下的子树调整时使得X节点变色变成了红色，因为如果是新插入节点，也就是几个矩形表示的子树都删掉，此时每条路径的黑色节点个数显然不相同，所以只能是变色的原节点，然后矩形中的N和N+1是黑色节点的个数

然后同样的，进行一个右旋的操作，然后将G变成红色，P变成黑色即可

以下是调整完毕的子树

2.3双旋+变色

例如这种情况，如果叔叔节点不存在的话，就只剩下G，P，X三个节点，因为在X插入前，如果P还有左子树，那么左子树至少会存在一个节点，如果这个节点是红色，不满足规则3，如果这个节点是黑色，不满足规则4，所以这棵子树只有G和P两个节点，然后先进行一次左旋，然后进行一次右旋，将X变为黑色，将G变为红色即可，最终结果是X成为子树新的根节点，P和G作为它的左右节点

然后继续观察叔叔节点存在且为黑的情况，操作是一样的，只不过现在的X肯定不是新插入的节点，一定是子树向上调整时变色导致的，因为如果不是变色的，连续红色节点不符合红黑树规则，这棵树就是不合理的

以下是旋转变色完成之后的结果

3.红黑树代码实现

3.1插入函数

关于旋转部分的代码，可以复用上一篇文章讲过的AVL树中的旋转代码

后续的几个函数都会放在这个类中

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->_left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else return false; } //新插入节点的时候，默认颜色为红色 //因为插入黑色节点会破坏所有路径黑色节点个数相同这一条规则 //这一条规则比较难维护，所以选择插入红色节点 cur = new Node(kv); cur->_col = RED; if (cur->_kv.first < parent->_kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; //此时需要判断是否需要旋转树 //如果父亲节点是黑色，那么直接插入红色节点不影响 //那么如果父亲节点也是红色，就需要调整 while (parent && parent->_col == RED) { //找到爷爷节点，然后找到叔叔节点 Node* grandfather = parent->_parent; //如果父亲节点是爷爷节点的左节点 if (grandfather->_left == parent) { Node* uncle = grandfather->_right; //如果叔叔节点存在且为红，进行变色 //叔叔和父亲变为黑色，爷爷节点变为红 //这样不影响这两条路径的黑色节点个数 if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; //然后往上一层处理 //每次都只看局部的三个节点 cur = grandfather; parent = cur->_parent; } //当叔叔节点不存在，或者叔叔存在但是为黑色 //此时要进行旋转的操作 else { //此时前置条件为父亲节点是爷爷节点的左节点 //判断cur在左还是在右，进行相应的旋转 if (cur == parent->_left) { //右旋 RotateR(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else { //进行左右双旋 RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; //进行了旋转之后，不用往上继续调整了 } } //此时父亲节点是爷爷节点的右节点 else { Node* uncle = grandfather->_left; //如果叔叔节点存在且为红，进行变色 //叔叔和父亲变为黑色，爷爷节点变为红 //这样不影响这两条路径的黑色节点个数 if (uncle && uncle->_col == RED) { parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; //然后往上一层处理 //每次都只看局部的三个节点 cur = grandfather; parent = cur->_parent; } //当叔叔节点不存在，或者叔叔存在但是为黑色 //此时要进行旋转的操作 else { //此时前置条件为父亲节点是爷爷节点的右节点 //判断cur在左还是在右，进行相应的旋转 if (cur == parent->_right) { //左旋 RotateL(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else { //进行右左双旋 RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; //进行了旋转之后，不用往上继续调整了 } } } } private: Node* _root = nullptr; };

3.2检验红黑树平衡

通过红黑树的规则进行检验，如果出现连续节点那么就返回false，或者某条路径黑色节点和其他路径不一样也会返回false

//检查是否颜色正确 bool Check(Node* cur，int BlackNum, const int BlackNumSum) { if (cur == nullptr) { if (BlackNum != BlackNumSum) { cout << "黑色节点个数不对" << endl; return false; } return true; } //如果出现连续的红色也是错误 if (cur->_col == RED && cur->_parent && cur->_parent->_col == RED) { cout << cur->_kv.first << "->" << "出现连续红色节点" << endl; return false; } if (cur->_col == BLACK) { BlackNum++; } return Check(cur->_left, BlackNum.BlackNumSum) && Check(cur->_right, BlackNum.BlackNumSum); }

因为每条路径上的黑色节点个数相同，所以可以先走完一条路径算出一条路径的黑色节点数，作为参数传入函数中，用于判断红黑树是否合理

外面再嵌套一个函数，进行红黑树是否平衡的代码实现

bool IsBanlance(Node* root) { if (_root == nullptr) { return true; } if (_root->_col == RED) { return false; } Node* cur = _root; int BlackNumSum = 0; while (cur) { if (cur->_col == BLACK) { BlackNumSum++; } cur = cur->_left; } return Check(_root, 0, BlackNumSum); }