目录一、红黑树的概念和性质最长路径不超过最短路径的2倍二、红黑树的实现2.1 红黑树的结构2.2 红黑树的插入2.2.1 大致插入2.2.2 插入分析1.u存在且为红1.1 u在右子树上1.2 u在左子树上2.u存在且为黑2.1 u在右子树上2.2 u在左子树上3.不存在3.1 u在右子树上3.2 u在左子树上2.2.3 完整代码2.3 红黑树的查询2.4 红黑树的验证一、红黑树的概念和性质最长路径不超过最短路径的2倍概念红黑树是⼀棵⼆叉搜索树他的每个结点增加⼀个存储位来表示结点的颜色可以是红色或者黑色。通过对任何⼀条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有⼀条路径会比其他路径长出2倍因而是接近平衡的。性质1.每个结点不是红色就是黑色2.根结点是黑色的3.如果⼀个结点是红色的则它的两个孩子结点必须是黑色的意思是红色结点不能连续4.对于任意⼀个结点从该结点到其所有NULL结点的简单路径上均包含相同数量的黑色结点关于最长路径不超过最短路径的2倍这里主要是由红黑树中2个规则决定的一个是所有到空结点的简单路径的黑色结点数量是相同的还有一个是红色结点不能连续存在这两个规则就决定了红黑树最长路径不超过最短路径的2倍这就是为什么能保持平衡的原因。二、红黑树的实现2.1 红黑树的结构根据我们对红黑树的理解平衡树这里的结构主要是需要插颜色结点。//颜色枚举 enum Color { Red, Black }; //红黑树结点 templateclass K, class V struct RBTNode { pairK, V _kv; Color _col Red; RBTNodeK, V* _parent; RBTNodeK, V* _left; RBTNodeK, V* _right; //初始化 RBTNode(pairK, V kv) :_kv(kv) , _parent(nullptr) , _left(nullptr) , _right(nullptr) { } }; //红黑树结构 templateclass K, class V class RBTree { typedef RBTNodeK, V Node; public: //初始化 RBTree(Node* root) :_root(root) {} private: Node* _root; };2.2 红黑树的插入2.2.1 大致插入因为这里我们很难控制黑色结点所以我们这里插入红色结点会很好控制黑色结点数量然后我们根据红色结点的规则去慢慢修改父节点/插入结点的颜色。bool insert(const pairK, V kv) { //判断根是否为空 if (_root nullptr) { _root new Node(kv); return true; } Node* cur _root; Node* parent nullptr; while (cur) { //比cur大往右棵树走 if (cur-_kv.first kv.first) { parent cur; cur cur-_right; } //比cur小往左课树走 else if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } //相同 else { return false; } } //找到空位置了 Node* node new Node(kv); //判断和父节点的大小 if (parent-_kv.first kv.first) { parent-_right node; } else { parent-_left node; } //更新父节点 Node* child node; child-_parent parent; //更改颜色维持平衡 }2.2.2 插入分析这里g表示爷爷结点u表示叔叔结点p表示父节点c表示插入结点/移动后的孩子结点如果一个结点是红色的则它的两个孩子结点必须是黑色的也就是说任意一条路径不会有连续的红色结点。黑色结点难控制插入黑色结点违反规则取解决就很难处理每条路径黑色结点数量相同情况所以这里用红色结点插入较为合适违反规则后向上进行调整黑色结点会更容易。非空树插入后新增结点必须红色结点如果父亲结点是红色的则违反性质3。进一步分析c是红色p为红g必为黑这三个颜色都固定了关键的变化看u的情况需要根据u分为以下几种情况分别处理。1.u存在且为红1.1 u在右子树上u在右子树上的第一种对于第一种情况我们无需任何处理因为此时满足红黑树性质。u在右子树上的第二种对于第二种我们就需要对p和u的颜色修改为黑色为了根结点到每个null结点的黑色结点相同这里还需要把g变为红。if (uncle uncle-_col Red) { parent-_col Black; uncle-_col Black; grandfather-_col Red;//为了平衡根结点到null的黑色结点数量 //继续往上修改 child parent; parent parent-_parent; }1.2 u在左子树上和u在右子树上的大致逻辑是一样的只需要改变p和u的颜色为黑g改为红就好了。2.u存在且为黑2.1 u在右子树上u在右子树上的第三种对于第三种情况对应的u存在且为黑情况此时g为红不需要做任何处理此时g为红p和u必须为黑c为红满足红黑树的性质。u在右子树上的第四种对于第四种情况对应的u存在且为黑g也为黑p为红p为黑也不用考虑和第三种情况一样这时候修改颜色就不行了BH表示黑色结点的高度这个时候就需要结合右单转来解决问题。u在右子树上的第五种第五种情况也是属于第四种情况一样不能通过直接改变颜色来解决问题这需要通过旋转来旋平衡这里和第四种旋转方式和改变颜色方式就不一样了需要右左双旋然后再把child变为黑色把grandfather变为红色维持平衡。//2.uncle存在且为黑 else if (uncle uncle-_col Black) { //右单旋 // g(黑) 右单旋 p(黑) // p(红) u(黑) ----- c(红) g(红) // c u(黑) if (parent-_left child) { RotateR(grandfather); //变色 parent-_col Black; grandfather-_col Red; } //左右双旋 // g(黑) 左单旋 g(黑) 右单旋 c(黑) // p(红) u(黑) ---- c(红) u(黑) --- p(红) g(红) // c p(红) u(黑) else { RotateL(parent); RotateR(grandfather); child-_col Black; grandfather-_col Red; } }2.2 u在左子树上u在左子树上的第三种u在左子树中的第三种通过左单旋然后改变p为黑g为红就能平衡了和u在右子树是一样的旋转方式不一样。u在左子树上的第四种不需要变化u在左子树上的第五种对于这种情况就和我们在u存在且为黑的第五种情况类似都是双旋只不过双旋顺序不一样这里是先右单旋然后再左单旋改变颜色顺序也是一样的修改child为黑色grandfather为红色。//2.uncle存在且为黑 else if (uncle uncle-_col Black) { //左单旋 // g(黑) 左单旋变色 p(黑) // u(黑) p(红) ----- c(红) g(红) // c u(黑) if (parent-_right child) { RotateL(grandfather); //变色 parent-_col Black; grandfather-_col Red; } //右左双旋 // g(黑) 右单旋 g(黑) 左单旋变色 c(黑) // u(黑) p(红) ---- u(黑) c(红) --- g(红) p(红) // c p(红) u(黑) else { RotateR(parent); RotateL(grandfather); child-_col Black; grandfather-_col Red; } }3.不存在3.1 u在右子树上6和7这些情况u不存在和u存在且为黑旋转变色是一样的所以这里我们可以把他们综合在一起。3.2 u在左子树上同理也和u存在且为黑的旋转变色相同。2.2.3 完整代码bool insert(const pairK, V kv) { //判断根是否为空 if (_root nullptr) { _root new Node(kv); _root-_col Black; return true; } Node* cur _root; Node* parent nullptr; while (cur) { //比cur大往右棵树走 if (cur-_kv.first kv.first) { parent cur; cur cur-_right; } //比cur小往左课树走 else if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } //相同 else { return false; } } //找到空位置了 Node* node new Node(kv); //判断和父节点的大小 if (parent-_kv.first kv.first) { parent-_right node; } else { parent-_left node; } //更新父节点 Node* child node; child-_parent parent; //更改颜色维持平衡 while (parent parent-_parent parent-_col Red)//parent颜色为黑就不需要改变了因为黑色可以连续后面也有可能把parent变为红的情况但是都是旋转旋转后都会跳出循环因为已经平衡了 { //判断uncle是grand的左/右结点 Node* grandfather parent-_parent; if (grandfather-_left parent)//说明右子树是uncle { Node* uncle grandfather-_right; //1.uncle存在且为红 // g // p u // c if (uncle uncle-_col Red) { parent-_col Black; uncle-_col Black; grandfather-_col Red;//为了平衡根结点到null的黑色结点数量 //继续往上修改 child grandfather parent child-_parent; } //2.uncle存在且为黑 else if (uncle nullptr || uncle-_col Black) { //右单旋 // g(黑) 右单旋变色 p(黑) // p(红) u(黑) ----- c(红) g(红) // c u(黑) if (parent-_left child) { RotateR(grandfather); //变色 parent-_col Black; grandfather-_col Red; } //左右双旋 // g(黑) 左单旋 g(黑) 右单旋变色 c(黑) // p(红) u(黑) ---- c(红) u(黑) --- p(红) g(红) // c p(红) u(黑) else { RotateL(parent); RotateR(grandfather); child-_col Black; grandfather-_col Red; } break; } } else//左子树是uncle { Node* uncle grandfather-_left; //1.uncle存在且为红 // g // p u // c if (uncle uncle-_col Red) { parent-_col Black; uncle-_col Black; grandfather-_col Red;//为了平衡根结点到null的黑色结点数量 //继续往上修改 child grandfather; parent child-_parent; } //2.uncle存在且为黑 else if (uncle nullptr || uncle-_col Black) { //左单旋 // g(黑) 左单旋变色 p(黑) // u(黑) p(红) ----- c(红) g(红) // c u(黑) if (parent-_right child) { RotateL(grandfather); //变色 parent-_col Black; grandfather-_col Red; } //右左双旋 // g(黑) 右单旋 g(黑) 左单旋变色 c(黑) // u(黑) p(红) ---- u(黑) c(红) --- g(红) p(红) // c p(红) u(黑) else { RotateR(parent); RotateL(grandfather); child-_col Black; grandfather-_col Red; } break; } } } _root-_col Black; return true; } //左单旋 void RotateL(Node* parent) { Node* Rchild parent-_right; //右孩子 Node* parentparent parent-_parent; //父节点的父节点 Node* RchildLchild Rchild-_left; //Rchild左孩子 //先处理parent与RchildLchild连接关系 if (RchildLchild)//可能为空导致空指针解引用问题 RchildLchild-_parent parent; parent-_right RchildLchild; //处理Rchild与parent的关系 Rchild-_left parent; parent-_parent Rchild; //然后处理parentparent与Rchild的连接关系 //判断是否为根节点 if (parent _root) { _root Rchild; Rchild-_parent nullptr;//可读性明确为空 } else { //衔接Rchild与parentparent的关系 //判断Rchild是parentparent的左右孩子 if (parentparent-_left parent) { parentparent-_left Rchild; } else { parentparent-_right Rchild; } Rchild-_parent parentparent;//最后更新Rchild的父节点 } } //右单旋 void RotateR(Node* parent) { Node* Lchild parent-_left; Node* LchildRchild Lchild-_right; Node* parentparent parent-_parent; //先连接与parent与LchildRchild的连接关系 if (LchildRchild)//可能为空避免空指针解引用 LchildRchild-_parent parent; parent-_left LchildRchild; //再连接parent与Lchild的连接关系 Lchild-_right parent; parent-_parent Lchild; //最后连接parentparent与Lchild的关系 if (parent _root)//为根 { _root Lchild; Lchild-_parent nullptr;//明确为空 } else//不为根 { //判断是parentparent的左右孩子 if (parentparent-_left parent) { parentparent-_left Lchild; } else { parentparent-_right Lchild; } Lchild-_parent parentparent; } }2.3 红黑树的查询查询也和AVL树一样//查询 Node* Find(const K key) { Node* cur _root; while (cur) { if (cur-_kv.first key) { cur cur-_left; } else if (cur-_kv.first key) { cur cur-right; } else { return cur; } return nullptr; } }2.4 红黑树的验证这里我们需要验证左右到null路径的黑色结点数量相同、红色结点不能连续存在这两个难啃的规则就行了根结点为黑可以直接判断。针对判断黑色结点数量是否相同我们这里可以用递归判断结点黑色结点数量而对于红色结点也是如此。bool IsBalance() { if (_root nullptr) { return true; } //判断根结点是否为黑色结点 if (_root-_col Red) { return false; } Node* leftMost _root; int Blacknum 0; while (leftMost) { //统计根结点左棵树黑色结点,并以参考判断根结点到各个null空指针的简单路径相同 if (leftMost-_col Black) { Blacknum; } leftMost leftMost-_left; } return Check(_root,Blacknum,0); } bool Check(Node* cur, int Blacknum, int num) { //递归结束条件 if (cur nullptr) { if (Blacknum ! num) { return false; cout 黑色结点数量异常 cur-_kv.first endl; } return true; } //判断红色结点是否连续 if (cur-_col Red cur-_parent cur-_parent-_col Red) { cout 红色结点连续 cur-_kv.first endl; return false; } //累加黑色结点 if (cur-_col Black) { num; } return Check(cur-_left, Blacknum, num) Check(cur-_right, Blacknum, num); }