红黑树

红黑树介绍Page2目录1、红黑树的简单介绍2、红黑树中插入与删除算法3、着色与旋转操作算法5、在nginx中的应用4、源码实现分析红黑树的简单介绍1Page4红黑树简单介绍•Red-Blacktree,简称RB-Tree•它是在1972年由鲁道夫·贝尔发明的，他称之为“对称二叉B树”，它现代的名字是在LeoJ.Guibas和RobertSedgewick于1978年写的一篇论文中获得的•特点：利用对树中的结点“红黑着色”的要求，降低了平衡性的条件，达到局部平衡，有着良好的最坏情况运行时间，它可以在O(logn)时间内做查找，插入和删除。Page5红黑树简单介绍算法导论对R-BTree的介绍：红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。在一棵二叉查找，随机构造的二叉查找树的高度为lgn，操作的执行时间为O（lgn）但若是一棵具有n个结点的线性链，则此些操作最坏情况运行时间为O（n）。二叉平衡树（AVL-树）执行搜索时间为O（lgn），但执行插入删除算法复杂。Page6红黑树简单介绍一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：1.每个结点要么是红的，要么是黑的。2.根结点是黑的。3.每个叶结点（叶结点即指树尾端NULL指针）是黑的。4.如果一个结点是红的，那么它的俩个儿子都是黑的。5.对于任一结点而言，其到叶结点树尾端NULL指针的每一条路径都包含相同数目的黑结点。插入算法红黑树中插入和删除算法2Page8红黑树中的插入删除算法RB-INSERT(T,z)1y←nil[T]2x←root[T]3whilex≠nil[T]4doy←x5ifkey[z]key[x]6thenx←left[x]7elsex←right[x]8p[z]←y9ify=nil[T]10thenroot[T]←z11elseifkey[z]key[y]12thenleft[y]←z13elseright[y]←z14left[z]←nil[T]15right[z]←nil[T]16color[z]←RED17RB-INSERT-FIXUP(T,z)处理红黑树使满足红黑树性质Y指向z的双亲节点，x为z在树中的位置查找定位x的位置判断z在y的左边还是右边Page9红黑树中的插入删除算法其一、把出现违背红黑树性质的结点向上移，如果能移到根结点，那么很容易就能通过直接修改根结点来恢复红黑树的性质。直接通过修改根结点来恢复红黑树应满足的性质。其二、穷举所有的可能性，之后把能归于同一类方法处理的归为同一类，不能直接处理的化归到下面的几种情况Page10红黑树中的插入删除算法•情况1：插入的是根结点。•情况2：插入的结点的父结点是黑色。•情况3：当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色。•情况4：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右孩子•情况5：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左孩子Page11红黑树中的插入删除算法•情况1：当前节点是红+黑色•情况2：当前节点是黑+黑且是根节点•情况3：当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。•情况4：当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点全为黑色。•情况5：当前节点颜色是黑+黑，兄弟节点是黑色，兄弟的左子是红色，右子是黑色。•情况6：当前节点颜色是黑-黑色，它的兄弟节点是黑色，但是兄弟节点的右子是红色，兄弟节点左子的颜色任意。着色与旋转操作算法3•插入情况1当红黑树中没有节点的时候，新节点直接涂黑就可以了。当树中已有节点，就将新节点涂红，并且底下挂两个黑空节点。考虑新节点的父节点颜色着色与旋转算法Page13•插入情况2当新节点的父亲为黑色，直接插入将新节点可以了，不做调整着色与旋转算法Page14着色与旋转算法•插入情况3当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色。Page15着色与旋转算法对策：将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，从新的当前节点重新开始算法。Page16着色与旋转算法•插入情况4当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子Page17着色与旋转算法对策：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。Page18着色与旋转算法•插入情况5当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子Page19着色与旋转算法解法：父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋Page20着色与旋转算法1、没有儿子，即为叶结点。2、只有一个儿子。3、有两个儿子。在删除节点后，原红黑树的性质可能被改变。•如果删除的是红色节点，那么原红黑树的性质依旧保持，此时不用做修正操作•如果删除的节点是黑色节点，原红黑树的性质可能会被改变，Page21着色与旋转算法Page22着色与旋转算法情况1：当前节点是红+黑顶替节点颜色为红———已经删除节点颜色为黑解法，直接把当前节点染成黑色，结束。此时红黑树性质全部恢复。情况2：当前节点是黑+黑且是根节点解法：什么都不做，结束Page23着色与旋转算法情况3：当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。Page24着色与旋转算法解法：把父节点染成红色，把兄弟结点染成黑色，之后重新进入算法Page25着色与旋转算法情况4：当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点全为黑色。Page26着色与旋转算法解法：把当前节点和兄弟节点中抽取一重黑色追加到父节点上，把父节点当成新的当前节点，重新进入算法。Page27着色与旋转算法情况5：当前节点颜色是黑+黑，兄弟节点是黑色，兄弟的左子是红色，右子是黑色。Page28着色与旋转算法解法：把兄弟结点染红，兄弟左子节点染黑，之后再在兄弟节点为支点解右旋，之后重新进入算法。Page29着色与旋转算法情况6：当前节点颜色是黑-黑色，它的兄弟节点是黑色，但是兄弟节点的右子是红色，兄弟节点左子的颜色任意。Page30着色与旋转算法解法：把兄弟节点染成当前节点父节点的颜色，把当前节点父节点染成黑色，兄弟节点右子染成黑色，之后以当前节点的父节点为支点进行左旋，此时算法结束，红黑树所有性质调整正确。Page31代码分析实现4Page33左旋代码1.//一、左旋代码分析2./*-----------------------------------------------------------3.|noderight4.|//==//5.|arightnodey6.|////7.|byab//左旋8.-----------------------------------------------------------*/9.staticrb_node_t*rb_rotate_left(rb_node_t*node,rb_node_t*root)10.{11.rb_node_t*right=node-right;//指定指针指向right--node-right12.13.if((node-right=right-left))14.{15.right-left-parent=node;//好比上面的注释图，node成为b的父母16.}17.right-left=node;//node成为right的左孩子18.Page34左旋代码1.if((right-parent=node-parent))2.{3.if(node==node-parent-right)4.{5.node-parent-right=right;6.}7.else8.{9.node-parent-left=right;10.}11.}12.else13.{14.root=right;15.}16.node-parent=right;//right成为node的父母17.18.returnroot;19.}红黑树在NGINX中的应用5Page36红黑树在NGINX下的应用Page37红黑树在NGINX下的应用•NGINX调用ngx_eventfind_timer()获取timer，然后传递给epoll模块，做等待时间。•nginx中的timer用红黑树的结构排序。ngx_event_timer_rbtree就是nginx中timer的红黑树。•nginx中的定时功能并没有采用操作系统提供的定时器，而是自己实现了一个模拟定时器的方法——最核心的就是一颗红黑树Page38红黑树在NGINX下的应用•NGINX调用ngx_eventfind_timer()获取timer，然后传递给epoll模块，做等待时间。•nginx中的timer用红黑树的结构排序。ngx_event_timer_rbtree就是nginx中timer的红黑树。Page39红黑树在NGINX下的应用1.src/core/ngx_rbtree.h2.3.typedefstructngx_rbtree_sngx_rbtree_t;4.5.typedefvoid(*ngx_rbtree_insert_pt)(ngx_rbtree_node_t*root,6.ngx_rbtree_node_t*node,ngx_rbtree_node_t*sentinel);7.8.structngx_rbtree_s{9.ngx_rbtree_node_t*root;//根节点10.ngx_rbtree_node_t*sentinel;//哨兵节点11.ngx_rbtree_insert_ptinsert;//插入方法指针12.};Page40红黑树在NGINX下的应用1.structngx_rbtree_node_s{2.ngx_rbtree_key_tkey;3.ngx_rbtree_node_t*left;//左节点4.ngx_rbtree_node_t*right;//右节点5.ngx_rbtree_node_t*parent;//父节点6.u_charcolor;//当前节点颜色7.u_chardata;//当前节点数据8.};Page41红黑树在NGINX下的应用•ngx_msec_t•ngx_event_find_timer(void)•{•ngx_msec_int_ttimer;•ngx_rbtree_node_t*node,*root,*sentinel;•//如果根节点地址等于哨兵将节点地址，返回-1•if(ngx_event_timer_rbtree.root==&ngx_event_timer_sentinel){•returnNGX_TIMER_INFINITE;•}•//对ngx_event_timer_mutex上锁•ngx_mutex_lock(ngx_event_timer_mutex);••root=ngx_event_timer_rbtree.root;•sentinel=ngx_event_timer_rbtree.sentinel;•//获取最小的timer界定•node=ngx_rbtree_min(root,sentinel);•//解锁•ngx_mutex_unlock(ngx_event_timer_mutex);•//用最小值的timer节点的值减去ngx_current_mses值•timer=(ngx_msec_int_t)node-key-(ngx_msec_int_t)ngx_current_msec;••return(ngx_msec_t)(timer0?timer:0);•}Page42红黑树在NGINX下的应用nginx中，当前所有可能被触发的定时器被保存在红黑树这种数据结构中，通过红黑树，你