树--10---红黑树

提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档文章目录红黑树Red-Black Tree2-3树红黑树----基本思想红链接,黑链接红黑树的定义定义 1特点:下面是红黑树与2-3树的对应关系定义 2:特点分析:应用红黑树实现逻辑结点API根结点的颜色总是黑色平衡化1. 左旋前提左旋过程2. 右旋前提右旋过程3. 颜色反转插入1. 向单个2-结点中插入新键**如果新键小于当前结点的键**如果新键大于当前结点的键2. 向底部的2-结点插入新键用红链接将新结点和它的父结点相连3. 向一棵双键树(即一个3-结点)中插入新键3.1 新键大于原树中的两个键3.2 新键小于原树中的两个键3.3 新键介于原数中两个键之间4. 向树底部的3-结点插入新键红黑树代码实现API设计代码测试红黑树Red-Black Tree2-3树我们前面介绍了2-3树可以看到2-3树能保证在插入元素之后树依然保持平衡状态它的最坏情况下所有子结点都是2-结点树的高度为lgN,相比于我们普通的二叉查找树最坏情况下树的高度为N确实保证了最坏情况下的时间复杂度但是2-3树实现起来过于复杂所以我们介绍一种2-3树思想的简单实现红黑树。红黑树----基本思想红黑树主要是对2-3树进行编码红黑树背后的基本思想是用标准的二叉查找树(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示2-3树。红链接,黑链接我们将树中的链接分为两种类型红链接将两个2-结点连接起来构成一个3-结点黑链接则是2-3树中的普通链接。确切的说我们将3-结点表示为由由一条左斜的红色链接(两个2-结点其中之一是另一个的左子结点)相连的两个2-结点。这种表示法的一个优点是我们无需修改就可以直接使用标准的二叉查找树的get方法。红黑树的定义定义 1特点:红黑树是含有红黑链接并满足下列条件的二叉查找树红链接均为左链接没有任何一个结点同时和两条红链接相连该树是完美黑色平衡的即任意空链接到根结点的路径上的黑链接数量相同下面是红黑树与2-3树的对应关系定义 2:红黑树Red Black Tree 是一种自平衡二叉搜索树是在计算机科学中用到的一种数据结构典型的用途是实现关联数组.红黑树是一种特化的AVL树平衡二叉树都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡从而获得较高的查找性能.特点节点是红色或黑色性质2. 根节点是黑色所有叶子都是黑色。叶子是NUIL节点每个红色节点的两个子节点都是黑色。从每个叶子到根的所有路径上不能有两个连续的红色节点从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点分析:红黑树会主动平衡树的结构,使树两边数据尽量达到平衡.始终保证左子节点数 父节点数 右子节点数的规则。但 红黑树 在大数据场景下面,树的高度不可控,那么存在叶子节点的数据,查找起来效率不会特别高.会多次IO读取磁盘中的数据(索引一般保存在磁盘当中).应用广泛用于C的STL中,map和set都是用红黑树实现的.著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间.IO多路复用epoll的实现采用红黑树组织管理sockfd以支持快速的增删改查.ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.java中TreeMap的实现.红黑树实现逻辑结点API因为每个结点都只会有一条指向自己的链接从它的父结点指向它我们可以在之前的Node结点中添加一个布尔类型的变量color来表示链接的颜色。如果指向它的链接是红色的那么该变量的值为true如果链接是黑色的那么该变量的值为false。//结点类privateclassNode{//存储键publicKeykey;//存储值privateValuevalue;//记录左子结点publicNodeleft;//记录右子结点publicNoderight;//由其父结点指向它的链接的颜色publicbooleancolor;publicNode(Keykey,Valuevalue,Nodeleft,Noderight,booleancolor){this.keykey;this.valuevalue;this.leftleft;this.rightright;this.colorcolor;}}根结点的颜色总是黑色之前我们介绍结点API的时候在结点Node对象中color属性表示的是父结点指向当前结点的连接的颜色由于根结点不存在父结点所以每次插入操作后我们都需要把根结点的颜色设置为黑色。平衡化在对红黑树进行一些增删改查的操作后很有可能会出现红色的右链接或者两条连续红色的链接而这些都不满足红黑树的定义所以我们需要对这些情况通过旋转进行修复让红黑树保持平衡。1. 左旋当某个结点的左子结点为黑色右子结点为红色此时需要左旋。前提当前结点为h它的右子结点为x左旋过程让x的左子结点变为h的右子结点h.rightx.left;让h成为x的左子结点x.lefth;让h的color属性变为x的color属性值x.colorh.color;让h的color属性变为REDh.colortrue;2. 右旋当某个结点的左子结点是红色且左子结点的左子结点也是红色需要右旋前提当前结点为h它的左子结点为x右旋过程让x的右子结点成为h的左子结点h.left x.right;让h成为x的右子结点x.righth;让x的color变为h的color属性值x.color h.color;让h的color为RED3. 颜色反转当一个结点的左子结点和右子结点的color都为RED时也就是出现了临时的4-结点此时只需要把左子结点和右子结点的颜色变为BLACK同时让当前结点的颜色变为RED即可。插入1. 向单个2-结点中插入新键一棵只含有一个键的红黑树只含有一个2-结点。插入另一个键后我们马上就需要将他们旋转。如果新键小于当前结点的键我们只需要新增一个红色结点即可新的红黑树和单个3-结点完全等价。如果新键大于当前结点的键那么新增的红色结点将会产生一条红色的右链接此时我们需要通过左旋把红色右链接变成左链接插入操作才算完成。形成的新的红黑树依然和3-结点等价其中含有两个键一条红色链接。2. 向底部的2-结点插入新键用红链接将新结点和它的父结点相连用和二叉查找树相同的方式向一棵红黑树中插入一个新键会在树的底部新增一个结点可以保证有序性唯一区别的地方是我们会用红链接将新结点和它的父结点相连。如果它的父结点是一个2-结点那么刚才讨论的两种方式仍然适用。3. 向一棵双键树(即一个3-结点)中插入新键这种情况有可以分为三种子情况3.1 新键大于原树中的两个键3.2 新键小于原树中的两个键3.3 新键介于原数中两个键之间4. 向树底部的3-结点插入新键假设在树的底部的一个3-结点下加入一个新的结点。前面我们所讲的3种情况都会出现。指向新结点的链接可能是3-结点的右链接此时我们只需要转换颜色即可或是左链接(此时我们需要进行右旋转然后再转换)或是中链接(此时需要先左旋转然后再右旋转最后转换颜色)。颜色转换会使中间结点的颜色变红相当于将它送入了父结点。这意味着父结点中继续插入一个新键我们只需要使用相同的方法解决即可直到遇到一个2-结点或者根结点为止。红黑树代码实现API设计代码packagemain.java.Algorithms.tree;publicclassRedBlackTreeKeyextendsComparableKey,Value{//根节点privateNoderoot;//记录树中元素的个数privateintN;//红色链接privatestaticfinalbooleanREDtrue;//黑色链接privatestaticfinalbooleanBLACKfalse;//结点类privateclassNode{//存储键publicKeykey;//存储值privateValuevalue;//记录左子结点publicNodeleft;//记录右子结点publicNoderight;//由其父结点指向它的链接的颜色publicbooleancolor;publicNode(Keykey,Valuevalue,Nodeleft,Noderight,booleancolor){this.keykey;this.valuevalue;this.leftleft;this.rightright;this.colorcolor;}}//获取树中元素的个数publicintsize(){returnN;}/** * 判断当前节点的父指向链接是否为红色 * * param x * return */privatebooleanisRed(Nodex){if(xnull){returnfalse;}returnx.colorRED;}/** * 左旋转 * * param h * return */privateNoderotateLeft(Nodeh){//找出当前结点h的右子结点NodehRighth.right;//找出右子结点的左子结点NodelhRighthRight.left;//让当前结点h的右子结点的左子结点成为当前结点的右子结点h.rightlhRight;//让当前结点h称为右子结点的左子结点hRight.lefth;//让当前结点h的color编程右子结点的colorhRight.colorh.color;//让当前结点h的color变为REDh.colorRED;//返回当前结点的右子结点returnhRight;}/** * 右旋 * * param h * return */privateNoderotateRight(Nodeh){//找出当前结点h的左子结点NodehLefth.left;//找出当前结点h的左子结点的右子结点NoderHlefthLeft.right;//让当前结点h的左子结点的右子结点称为当前结点的左子结点h.leftrHleft;//让当前结点称为左子结点的右子结点hLeft.righth;//让当前结点h的color值称为左子结点的color值hLeft.colorh.color;//让当前结点h的color变为REDh.colorRED;//返回当前结点的左子结点returnhLeft;}/** * 颜色反转,相当于完成拆分4-节点 * * param h */privatevoidflipColors(Nodeh){//当前结点变为红色h.colorRED;//左子结点和右子结点变为黑色h.left.colorBLACK;h.right.colorBLACK;}/** * 在整个树上完成插入操作 * * param key * param val */publicvoidput(Keykey,Valueval){rootput(root,key,val);//根结点的颜色总是黑色root.colorBLACK;}/** * 在指定树中完成插入操作,并返回添加元素后新的树 * * param h * param key * param val */privateNodeput(Nodeh,Keykey,Valueval){//判断h是否为空如果为空则直接返回一个红色的结点就可以了if(hnull){//数量1N;returnnewNode(key,val,null,null,RED);}//比较要插入的键和当前结点的键intcmpkey.compareTo(h.key);if(cmp0){//继续寻找左子树插入h.leftput(h.left,key,val);}elseif(cmp0){//继续寻找右子树插入h.rightput(h.right,key,val);}else{//已经有相同的结点存在修改节点的值h.valueval;}//如果当前结点的右链接是红色左链接是黑色需要左旋if(isRed(h.right)!isRed(h.left)){hrotateLeft(h);}//如果当前结点的左子结点和左子结点的左子结点都是红色链接则需要右旋if(isRed(h.left)isRed(h.left.left)){hrotateRight(h);}//如果当前结点的左链接和右链接都是红色需要颜色变换if(isRed(h.left)isRed(h.right)){flipColors(h);}//返回当前结点returnh;}//根据key从树中找出对应的值publicValueget(Keykey){returnget(root,key);}//从指定的树x中查找key对应的值publicValueget(Nodex,Keykey){if(xnull){returnnull;}//比较x结点的键和key的大小intcmpkey.compareTo(x.key);if(cmp0){returnget(x.left,key);}elseif(cmp0){returnget(x.right,key);}else{returnx.value;}}}测试packagemain.java.Algorithms.tree;publicclassRedBlackTreeTest{publicstaticvoidmain(String[]args)throwsException{RedBlackTreeInteger,StringbtnewRedBlackTree();bt.put(4,二哈);bt.put(1,张三);bt.put(3,李四);bt.put(5,王五);System.out.println(bt.size());bt.put(1,老三);System.out.println(bt.get(1));System.out.println(bt.get(2));System.out.println(bt.get(3));System.out.println(bt.get(4));System.out.println(bt.get(5));System.out.println(bt.size());}}