红黑树（Red-Black Tree）实现原理详解

目录一、红黑树简介二、红黑树的性质规则1规则2规则3规则4红黑树的平衡原因红黑树的效率三、红黑树的实现四、红黑树插入原理1、普通BST插入2、新结点颜色空树插入非空树插入插入后的调整情况一叔叔存在且为红变色情况二单旋 变色情况三双旋 变色代码实现一、红黑树简介红黑树Red-Black Tree是一种特殊的平衡二叉搜索树Balanced Binary Search Tree它在普通二叉搜索树的基础上增加了颜色属性通过颜色约束保证树始终保持近似平衡状态。相比AVL树红黑树对平衡要求没有那么严格因此插入和删除时旋转次数更少在实际工程中应用更加广泛。例如C STL中的map、setJava中的TreeMap、TreeSetLinux内核中的进程调度器底层都采用了红黑树结构。二、红黑树的性质红黑树中的每个结点都有一个颜色属性红色RED)或者黑色BLACK红黑树必须满足以下4条规则规则1每个结点不是红色就是黑色。规则2根结点必须是黑色。规则3如果一个结点是红色则它的两个孩子结点必须是黑色。即不允许出现连续的红色结点。例如这种情况是不允许的。规则4从任意结点到其所有NULL叶子结点的路径中黑色结点数量必须相同。例如每条路径上的黑色结点数都相同。红黑树的平衡原因红黑树并不是严格平衡树而是近似平衡树。由规则4可知从根到NULL结点的每条路径都有相同数量的⿊⾊结点所以极端场景下最短路径就是全是黑色结点的路径假设最短路径长度为bh(black height)由规则2和规则3可知任意⼀条路径不会有连续的红色结点所以极端场景下最长的路径就是一黑一红间隔组成那么最长路径的长度为2*bh。综合红⿊树的4点规则⽽⾔理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为x那么bhx2*bh。即最长路径不会超过最短路径的2倍。这就是红黑树保持平衡的核心原理。红黑树的效率假设N是红⿊树树中结点数量h是最短路径的⻓度那么2^h−1 N 2^(2h)−1 ,由此推出h≈logN也就是意味着红⿊树增删查改最坏也就是走最长路径2∗logN那么时间复杂度还是O(logN)。三、红黑树的实现enum Colour { RED, BLACK }; templateclass K, class V struct RBTreeNode { // 这里更新控制平衡也要加入parent指针 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) {} }; templateclass K, class V class RBTree { typedef RBTreeNodeK, V Node; public: //红黑树逻辑 private: Node* _root nullptr; }红黑树的结构跟AVL树的结构是相似的四、红黑树插入原理红黑树的插入跟AVL树的插入也是相似的1、普通BST插入首先按照二叉搜索树规则找到插入位置。2、新结点颜色空树插入直接作为根颜色设置为黑非空树插入新结点统一插入为颜色为红色原因如果插入黑色结点会破坏规则4。插入后的调整设当前结点 ccur父亲 pparent祖父 ggrandfather叔叔 uuncle情况一叔叔存在且为红变色c为红p为红g为黑u存在且为红则将p和u变黑g变红。再把g当做新的c继续往上更新。分析因为p和u都是红色g是黑色把p和u变黑左边子树路径各增加一个黑色结点g再变红相当于保持g所在子树的黑色结点的数量不变同时解决了c和p连续红色结点的问题需要继续往上更新是因为g是红色如果g的父亲还是红色那么就还需要继续处理如果g的父亲是黑色则处理结束了如果g就是整棵树的根再把g变回黑色。情况1只变色不旋转。所以无论c是p的左还是右p是g的左还是右都是上面的变色处理方式。图0跟 AVL 树类似图 0 我们展示了一种具体情况但实际中需要这样处理的情况有很多种。图 1 将以上类似的处理进行了抽象表达d / e / f 代表每条路径拥有 hb 个黑色结点的子树a / b 代表每条路径拥有 hb − 1 个黑色结点、且根为红的子树其中 hb ≥ 0。图 2 / 图 3 / 图 4 分别展示了 hb 0、hb 1、hb 2 的具体组合分析。当 hb 2 时这里的组合情况可达上百亿种。这些样例的作用是帮助我们理解不论情况有多少种、多么复杂处理方式都是一样的——变色后再继续往上处理即可。因此我们只需要看抽象图即可。图1图2图3图4情况二单旋 变色c 为红p 为红g 为黑u 不存在或者 u 存在且为黑。若 u 不存在则 c 一定是新增结点若 u 存在且为黑则 c 一定不是新增结点c 之前是黑色的是在 c 的子树中插入符合情况 1通过变色将 c 从黑色变成红色再向上更新。分析​p 必须变黑才能解决连续红色结点的问题。由于 u 不存在或者是黑色这里单纯的变色无法解决问题需要旋转 变色。如果 p 是 g 的左孩子c 是 p 的左孩子以 g 为旋转点进行右单旋再把 p 变黑g 变红即可。p 变成这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点且不需要再往上更新因为 p 的父亲是黑色、红色或者为空都不违反规则。如果 p 是 g 的右孩子c 是 p 的右孩子以 g 为旋转点进行左单旋再把 p 变黑g 变红即可。p 变成这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点且不需要再往上更新因为 p 的父亲是黑色、红色或者为空都不违反规则。情况三双旋 变色c 为红p 为红g 为黑u 不存在或者 u 存在且为黑。若 u 不存在则 c 一定是新增结点若 u 存在且为黑则 c 一定不是新增结点c 之前是黑色的是在 c 的子树中插入符合情况 1通过变色将 c 从黑色变成红色再向上更新。分析​p 必须变黑才能解决连续红色结点的问题。由于 u 不存在或者是黑色这里单纯的变色无法解决问题需要旋转 变色。如果 p 是 g 的左孩子c 是 p 的右孩子先以 p 为旋转点进行左单旋再以 g 为旋转点进行右单旋然后把 c 变黑g 变红即可。c 变成这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点且不需要再往上更新因为 c 的父亲是黑色、红色或者为空都不违反规则。如果 p 是 g 的右孩子c 是 p 的左孩子先以 p 为旋转点进行右单旋再以 g 为旋转点进行左单旋然后把 c 变黑g 变红即可。c 变成这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点且不需要再往上更新因为 c 的父亲是黑色、红色或者为空都不违反规则。代码实现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-_right; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } else { return false; } } cur new Node(kv); cur-_col RED; if (parent-_kv.first kv.first) { parent-_right cur; } else { parent-_left cur; } // 链接父亲 cur-_parent parent; // 父亲是红色出现连续的红色节点需要处理 while (parent parent-_col RED) { Node* grandfather parent-_parent; if (parent grandfather-_left) { // g // p u Node* uncle grandfather-_right; if (uncle uncle-_col RED) { // 变色 parent-_col uncle-_col BLACK; grandfather-_col RED; // 继续往上处理 cur grandfather; parent cur-_parent; } else { 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; // 叔叔存在且为红-》变色即可 if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfather-_col RED; // 继续往上处理 cur grandfather; parent cur-_parent; } else // 叔叔不存在或者存在且为黑 { // 情况二叔叔不存在或者存在且为黑 // 旋转变色 // g // u p // c if (cur parent-_right) { RotateL(grandfather); parent-_col BLACK; grandfather-_col RED; } else { RotateR(parent); RotateL(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } } _root-_col BLACK; return true; }左单旋右单旋的原理可以查看AVL树中的旋转原理AVL树详解与实现