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那么N2^h-1假设所有路径长度均为2h那么N2^2h-1但是最起码会存在一条最短路径所以N2^2h-1可以得出N的范围在[2^h-1,2^2h-1]之间计算可得h约等于logN所以查找的路径最短为logN最长路径为2*logN那么时间复杂度就是O(logN)1.2红黑树的结构每个节点的结构和AVL树很类似只不过把平衡因子换成了颜色因为红黑树通过颜色来控制树的平衡因为只有红色和黑色单独将颜色枚举出来颜色的类型就是Colour//枚举红黑树的颜色方便控制 enum Colour { RED, BLACK }; //红黑树的每个节点用一个结构体标表示 templateclass K,class V struct RBTreeNode { pairK, V _kv; RBTreeNodeK, V* _left; RBTreeNodeK, V* _right; RBTreeNodeK, V* _parent; Colour _col; RBTreeNode(const pairK,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和N1是黑色节点的个数然后同样的进行一个右旋的操作然后将G变成红色P变成黑色即可以下是调整完毕的子树2.3双旋变色例如这种情况如果叔叔节点不存在的话就只剩下GPX三个节点因为在X插入前如果P还有左子树那么左子树至少会存在一个节点如果这个节点是红色不满足规则3如果这个节点是黑色不满足规则4所以这棵子树只有G和P两个节点然后先进行一次左旋然后进行一次右旋将X变为黑色将G变为红色即可最终结果是X成为子树新的根节点P和G作为它的左右节点然后继续观察叔叔节点存在且为黑的情况操作是一样的只不过现在的X肯定不是新插入的节点一定是子树向上调整时变色导致的因为如果不是变色的连续红色节点不符合红黑树规则这棵树就是不合理的以下是旋转变色完成之后的结果3.红黑树代码实现3.1插入函数关于旋转部分的代码可以复用上一篇文章讲过的AVL树中的旋转代码后续的几个函数都会放在这个类中templateclass K,class V class RBTree { typedef RBTreeNodeK, V Node; public: //插入节点 bool Insert(const pairK, 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* curint 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); }