备案网站建设方案书范文,江门做网站,做外贸相关的网站,淘宝客推广有效果吗文章目录 一、红黑树的概念二、红黑树的性质三、红黑树和AVL树对比四、红黑树的插入1. 红黑树的结点定义2. 父亲的颜色3. 叔叔的颜色为红色4. 叔叔不存在5. 叔叔存在且为黑6. 插入的抽象图 五、红黑树的验证1. 检查平衡2. 计算高度与旋转次数3. 验证 六、 红黑树与AVL树的比较 … 文章目录 一、红黑树的概念二、红黑树的性质三、红黑树和AVL树对比四、红黑树的插入1. 红黑树的结点定义2. 父亲的颜色3. 叔叔的颜色为红色4. 叔叔不存在5. 叔叔存在且为黑6. 插入的抽象图 五、红黑树的验证1. 检查平衡2. 计算高度与旋转次数3. 验证 六、 红黑树与AVL树的比较 一、红黑树的概念 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍即最长路径不超过最短路径的两倍近似平衡因而是接近平衡的。 二、红黑树的性质 每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的则它的两个孩子结点必须是黑色的即任何路径没有连续的红色结点对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点每条路径上的黑色结点个数相同这里的路径包括空结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点已经不在是传统的叶子结点了图中的NIL结点就是空结点 这里对第四点做一补充说明
对于下面这棵树有11条路径而不是5条路径因为空结点也包括在内 如果不清楚上面的这一点如果遇到下面这棵树可能会误以为他是红黑树实际上它不是红黑树。
如果我们不看每个空结点的话它看上去有四条路径且每条路径都只有两个黑色结点看上去好像是红黑树。但是实际上要包括空结点且空结点是黑色的。所以一共有九条路径最左边的一条路径只有两个黑色结点其他路径都有三个黑色结点。 第四点中说的虽然是每个结点的每条路径上的黑色结点个数相同但是由于每个结点的祖先的路径是唯一确定的所以我们只需要判断从根节点到每个空结点上的路径中黑色结点个数是否相同即可 那么为什么上面的性质可以保证最长路径不超过最长路径的两倍呢 如下图所示 最长路径就是黑红相间的情况最短路径就是全黑的情况。其他路径都是在这两者之间的此时我们也不难看出最长路径不超过最短路径的两倍。如果最短路径为N那么最长路径就是2N-1因为根节点一定是黑色的最终的叶子结点也一定是黑色的。 三、红黑树和AVL树对比
既然有了AVL树那么为什么要有红黑树呢其实是因为AVL树太严格了。它要控制平衡就需要付出代价。而红黑树要求并不严格综合来看红黑树的综合性能其实更优
AVL树红黑树高度对比高度差不超过一最长路径不超过最短路径的两倍插入1000个值logN----102*logN----20插入10亿个值logN----302*logN----60
我们可以看到虽然他们的高度有点差异但是他们的效率都是同一个量级的而且cpu的速度是非常快的这点效率对于cpu几乎没有任何区别
性能是同一量级的但是AVL树控制严格平衡是需要付出代价的插入和删除需要大量的旋转。
四、红黑树的插入
1. 红黑树的结点定义
如下所示 由于红黑树有红色结点和黑色结点两种颜色。所以不妨我们使用一个枚举类型来进行表示。红黑树里面我们需要有一个pair类型来进行存储key和value类型的数据。然后我们定义三个指针分别指向父亲左孩子右孩子。最后定义其的颜色。在构造函数中我们将其的颜色默认设置为红色。
设置为红色是比较有讲究的。那是因为我们大多数场景下都是去创建一个新节点去插入的。如果我们插入的这个新结点是黑色的话那么造成的后果就是违反了规则4即每条路径上的黑色结点个数相同显然这种情况要进行补救的话是十分麻烦的。还不如去插入红色结点如果插入的是红色结点的话仅仅有可能会违反规则3也就是红色结点的孩子必须是黑色结点。这一点的话我们还有的补救因为仅仅影响本条路径。
enum Color
{RED,BLACK
};templateclass K , class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Color _color;RBTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_color(RED) // 插入红色结点违反规则3只影响一条路径甚至可能不影响。如果插入黑色结点违反规则4影响所有路径{}
};2. 父亲的颜色
因为我们要插入的结点是红色的那么在我们插入的位置它的父亲要么是红色的要么是黑色的。如果是黑色的那么就是如下的情况 我们可以看到似乎并未影响整棵树的结构不违反任何一条规则。最短路径仍然不超过最长路径的两倍。每条路径上的黑色结点个数仍然相等。所以如果插入一个新节点以后如果此处它的父亲是黑色的完美不需要做出任何修改即可。如果父亲甚至都不存在那么这个结点就是这颗树了。我们只需要将这个结点变为黑色即可。如果父亲是红色的话那么就比较麻烦了。
如下图所示就是插入的时候父亲为红色显然已经违反了规则3了此时我们需要对这颗树进行处理了。 3. 叔叔的颜色为红色
如果我们插入了一个结点以后此时父亲结点为红色且有父亲的兄弟即叔叔且叔叔的颜色是红色。
即如下的情况uncle存在且为红 这样的话我们可以将parent和uncle都变黑然后让grandfather变红即如下的情形 这样的话在黑色结点数量不变的条件下使得连续红色结点的问题暂时解决了。现在原本cur为红色的问题转换为了grandfather为红色的问题。
此时的话如果这个grandfather如果没有父亲了那么根据规则1我们只需要让他变为黑色即可。此时仅仅只是所有的路径多了一个黑色结点。如果grandfather有父亲那么我们只需要让grandfather变为cur继续向上处理即可 在这里继续向上处理的时候又分为以下几种情况 grandfather没有父亲那么直接让grandfather变黑即可grandfather有父亲且父亲为黑色那么由于前面的树本身就是满足红黑树规则这里改变了之后仍然满足红黑树规则那么不处理即可grandfather有父亲且父亲为红色这样的情况下父亲为红色就隐含了必然存在grandfather的grandfather因为原来的树也要满足红黑树的规则这样一来就是类似的问题继续往处理即可。 然后由于此时恰好uncle存在且为红那么我们只需要按照前面的逻辑进行处理即可即uncle和parent均变黑然后grandfather变为红 然后又为了满足根节点为红所以grandfather变为黑即可 4. 叔叔不存在
如下图所示当叔叔不存在的时候我们还插入了一个新节点以后我们发现最长路径已经超过了最短路径的两倍了。这时候单纯的进行变色已经无法解决问题了。我们需要旋转了。 所以我们就需要进行旋转变色了。 对于变色与前面的情况类似即本来parent和uncle都为红色的话就把他们两个变为黑色然后把grandfather变为红色就可以了。不过现在uncle不存在了。那我们就先不管它了将parent变为黑色grandfather变为红色就可以了。对于旋转这个就需要我们进行具体的分析了看看究竟是左旋还是右旋还是双旋。具体判断规则与AVL基本是一致的如果是直线那么就是单旋我们只需要分析谁高就可以了。如果是折线就是双旋我们还是分析哪边高就可以了。 如上图所示的情形就是右单旋就可以了 5. 叔叔存在且为黑
我们接着前面的图我们继续插入一个新的结点 那么此时的uncle存在且为红我们进行相应的处理后变为如下的情况 这时候我们遇到了新的情况uncle存在且为黑
那么此时的处理情形就和前面的uncle不存在是一样的直接旋转加变色。这里的如何旋转和变色统一结论后面详细讨论 总结 红黑树的插入主要看uncle uncle存在且为红变色继续往上更新 uncle不存在或uncle存在且为黑旋转变色 6. 插入的抽象图
如下是第一种情况当cur为红p为红g为黑,u存在且为红的条件下。 在这种情况下我们可以p和u改为黑色g改为红然后把g当成cur,继续向上调整。 上面是我们的抽象图我们如果要具体细化每一种情况的下是非常之麻烦的
比如说当a、b、c、d、e均为空即cur是新增结点的时候如下所示 当a,b不为空且cur是黑色结点。那么cde都是含有一个结点的子树那么cde的每个样子都有四种情况如下所示 由于它可以在a,b这两个红色结点任意处进行插入也就是说可以在四个位置插入。 那么这种变换的情况就复杂很多有4*4*4*4共256种情况
如果cde有两个黑节点的话那么情况将更加复杂画图已经很难表示出来了 显然我们如果用具象图的话那么红黑树有无数种情况所以我们只能使用抽象图来表示这种情况。
所以根据前面的分析我们就可以写出如下的代码了。下面只是处理颜色的部分。 //开始处理颜色while (parent parent-_color RED){Node* grandfather parent-_parent;if (grandfather-_left parent){Node* uncle grandfather-_right;if (uncle uncle-_color RED){parent-_color BLACK;uncle-_color BLACK;grandfather-_color RED;cur grandfather;parent grandfather-_parent;}else if (uncle nullptr || uncle-_color BLACK){}}else{Node* uncle grandfather-_left;if (uncle uncle-_color RED){parent-_color BLACK;uncle-_color BLACK;grandfather-_color RED;cur grandfather;parent grandfather-_parent;}else if (uncle nullptr || uncle-_color BLACK){}}}接下来我们讨论第二种情况即cur为红p为红g为黑u不存在/u存在且为黑 首先来分析uncle不存在的情况下即如下的情况。此时我们可以注意到由于uncle不存在那么cur必然就是新插入的结点。此时我们就根据当前的cur与p的关系来确定是单旋还是双旋。旋转之后进行变色。在这里的变色中如果是单旋就是g和p变色即可。如果是双旋那么就是cur和g变色 p为g的左孩子cur为p的左孩子则进行右单旋转相反p为g的右孩子cur为p的右孩子则进行左单旋转 p、g变色—p变黑g变红 p为g的左孩子cur为p的右孩子则针对p做左单旋转相反p为g的右孩子cur为p的左孩子则针对p做右单旋转此时转化了为了第一步的情况
再来看一下uncle存在且为黑的情况下。由于uncle存在且为黑所以cur之前必然为黑色的因为为了满足每条路径上的黑色结点个数相同就代表着cur必须为先前向上处理后的在向上处理过程中cur变为了红色。 当uncle存在且为黑的情况下他的变色以及旋转规则都是与uncle不存在是一模一样的 p为g的左孩子cur为p的左孩子则进行右单旋转相反p为g的右孩子cur为p的右孩子则进行左单旋转 p、g变色—p变黑g变红 p为g的左孩子cur为p的右孩子则针对p做左单旋转相反p为g的右孩子cur为p的左孩子则针对p做右单旋转此时转化了为了第一步的情况
所以最终插入的完整代码为 bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_color BLACK; //根节点必须是黑色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); //插入红色结点if (parent-_kv.first kv.first){parent-_right cur;}else if (parent-_kv.first kv.first){parent-_left cur;}cur-_parent parent;//开始处理颜色while (parent parent-_color RED){Node* grandfather parent-_parent;if (grandfather-_left parent){Node* uncle grandfather-_right;if (uncle uncle-_color RED){parent-_color BLACK;uncle-_color BLACK;grandfather-_color RED;cur grandfather;parent grandfather-_parent;}else if (uncle nullptr || uncle-_color BLACK){if (parent-_left cur){RotateR(grandfather);parent-_color BLACK;grandfather-_color RED;break;}else{RotateL(parent);RotateR(grandfather);cur-_color BLACK;grandfather-_color RED;break;}}}else{Node* uncle grandfather-_left;if (uncle uncle-_color RED){parent-_color BLACK;uncle-_color BLACK;grandfather-_color RED;cur grandfather;parent grandfather-_parent;}else if (uncle nullptr || uncle-_color BLACK){if (parent-_right cur){RotateL(grandfather);grandfather-_color RED;parent-_color BLACK;break;}else{RotateR(parent);RotateL(grandfather);cur-_color BLACK;grandfather-_color RED;break;}}}}_root-_color BLACK;return true;}void RotateL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;Node* ppnode parent-_parent;//改变parentparent-_right curleft;parent-_parent cur;//改变curleftif (curleft ! nullptr){curleft-_parent parent;}//改变curcur-_left parent;cur-_parent ppnode;//改变ppnodeif (ppnode nullptr){_root cur;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}}}void RotateR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;Node* ppnode parent-_parent;//改变parentparent-_left curright;parent-_parent cur;//改变currightif (curright ! nullptr){curright-_parent parent;}//改变curcur-_right parent;cur-_parent ppnode;//改变ppnodeif (ppnode nullptr){_root cur;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}}}五、红黑树的验证
当我们写完一个比较复杂的程序的时候我们最好去写一个辅助代码去验证它
1. 检查平衡
如下代码所示可以去检测我们实现的红黑树当插入数据以后是否会出现不平衡的现象。检查利用的就是每条路径上黑色结点个数相同与不能出现连续的两个红色结点这两条规则。 bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root nullptr){return true;}if (root-_color RED){return false;}int benchmark 0;Node* cur root;while (cur){if (cur-_color BLACK){benchmark;}cur cur-_left;}return CheckColor(root, 0, benchmark);}bool CheckColor(Node* root, int blacknum, int benchmark){//检查每条路径的黑色结点数量是否相等if (root nullptr){if (blacknum ! benchmark){return false;}return true;}if (root-_color BLACK){blacknum;}//检查颜色if (root-_color RED root-_parent root-_parent-_color RED){cout root-_kv.first : 出现两个连续的红色结点 endl;return false;}return CheckColor(root-_left, blacknum, benchmark) CheckColor(root-_right, blacknum, benchmark);}2. 计算高度与旋转次数
高度的代码很简单如下所示 int Height(){return Height(_root);}int Height(Node* root){if (root nullptr){return 0;}int leftheight Height(root-_left);int rightheight Height(root-_right);return leftheight rightheight ? 1 leftheight : 1 rightheight;}对于旋转次数我们可以直接设置一个变量专门计数。每旋转一次这个值加一次 int Getrotatecount(){return _rotatecount;}3. 验证
int main()
{RBTreeint, int rb;srand(time(0));for (int i 0; i 10000; i){int tmp rand();rb.Insert(make_pair(tmp, tmp));//rb.Insert(make_pair(i, i));//cout rb.IsBalance() endl;//cout i : tmp endl;}cout height: rb.Height() endl;cout rotatecount: rb.Getrotatecount() endl;cout rb.IsBalance() endl;return 0;
}我们使用上面的随机数来进行测试
运行结果如下所示 六、 红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是logN红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数,所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
从源代码中我们也可以看出来其实map与set的底层都是红黑树而且是kv结构的红黑树
