469の一方爬行资料

本文主要介绍469の一方爬行资料 方法和在新技术下所面对的“挑战”,方便大家深入理解469の一方爬行资料 过程。本文也将分享469の一方爬行资料 所遇到的问题和应对策略,怎么解决怎么做的问题。
通过深入本文可以理解代码原理,进行代码文档的下载,也可以查看相应 Demo 部署效果。

在阅读其他博主关于红黑树增删实现的时候,博主们大多直接使用文字图片描述,对整个增删整体的流程突出的不太明显(当然dalao们写得还是很棒得,不然我也写不出这篇文章)。 所以我特意花了2天时间用CAD制作了 一张插入操作的流程图和一张删除操作的流程图(删除见下篇)并手撕了代码(手撕红黑树233). 本文则试图通过流程图,让大家换一个角度来了解整个插入操作的实现过程。

在阅读其他博主关于红黑树增删实现的时候,博主们大多直接使用文字图片描述,对整个增删整体的流程突出的不太明显(当然dalao们写得还是很棒得,不然我也写不出这篇文章),所以我特意花了2天时间用CAD制作了 一张插入操作的流程图和一张删除操作的流程图(删除见下篇)并手撕代码(好吧,其实大部分时间在调试代码,毕竟talk is easy,show me the code.)。

废话不多说了,进入正题吧。

红黑树是一种常见而又有点复杂的数据结构,它的应用场景有很多,比如经典的JAVA的HashMap,当slot中元素大于8时就会树化为红黑树。

和AVL树一样,红黑树也是一种二叉搜索树(BST)。但与AVL树不同的是,红黑树通过稍微牺牲其平衡性(即弱化了查找效率),并配合其特殊的规则(下面会说)以实现在增删上的效率提升。即相比AVL树,增删一个节点最多只用旋转三次。【红黑树:没有什么是两次旋转不能解决的,如果有就三次469の一方爬行

 

下面介绍以下红黑树的五个规则:

0、树中节点不是红色就是黑色;

1、根节点必为黑色;

2、红色节点的父子不能也是红色(或者说,由根至叶子的每一条路径上不能有连续的红节点);

3、每个叶子节点(NIL节点)是黑色的

4、任意节点到其下方的NIL节点的每一条路径上经过的黑色节点相同(或者说,除去红色节点,黑色节点就是是一个AVL树);

5、在维护红黑树性质之前,对于新插入的节点,我们把它涂红。【这其实只是一个经验,另外,五条规则有六个不是常识么?】

 

接下来我们就用流程图来梳理一下红黑树的插入操作:

但在此之前我们先规定下图中一些代号节点的含义以及旋转的操作:

C节点(Curent,当前要操作节点的指针)

P节点(Parent,当前C节点的父节点)

G节点(Grandparent,当前C节点的爷爷节点)

U节点(Uncle,当前C节点的叔叔节点,即P节点的兄弟节点)   

【注意P、G、U节点应当随着C的更新而更新】

旋转: 以P为支点进行右旋为例——C顶替P的位置,P变为C的有右孩子,C原来的右孩子变为P的左孩子。左旋反向即可。

另外图中白圈节点指代黑节点(毕竟CAD背景色是黑的嘛QAQ),红圈节点就是红节点。

469の一方爬行

 

最后附上代码(由于增删方法我是一起写的,所以代码中写了删除方法的实现,删除方法的具体流程请参阅下篇):

  1 /**   2  * 手撕红黑树   3  * By 469の瘸子 (意义不明的口胡:现在应该是420の的瘸子233)   4  * **/   5     public class RedBlackTree<E extends Comparable<E> & PrintToDOS> {   6    7         public static final boolean black = true;   8         public static final boolean red = false;   9         public Node root;  10   11         class Node {//节点类  12             public Node parent;  13             public Node left;  14             public Node right;  15             public E element;  16             public boolean color;  17   18             public Node (E element){//构造方法,默认新节点为红色  19                 this.element = element;  20                 this.color =red;  21             }  22   23             //打印的红黑树的时候,会调用每个节点的打印方法  24             public void print(){  25                 //先打印颜色  26                 if (this.color) {  27                     System.out.print("  black:");  28                 }else {  29                     System.out.print("  red:");  30                 }  31                 //再打印值  32                 element.print();  33                 //最后打印父节并换行  34                 if(parent==null){  35                     System.out.println("  this is root");  36                 }else {  37                     System.out.print("  parent is:");  38                     parent.element.println();  39                 }  40             }  41   42         }  43   44         //插入方法,会调用insert方法和fixAfterInsertion方法  45         public void insert(E element){  46             //case1:树中无元素,直接将elemnt插进去涂黑  47             if (root==null){  48                 root = new Node(element);  49                 root.color = black;  50             }else{//case2:树非空,先按二叉搜索树的方式确定元素位置,再视父元素颜色分类处理  51                 //先把节点插进去,如果插的元素已经存在会返回null  52                 Node node = insertBST(element);  53                 //再对树进行维护  54                 fixAfterInsertion(node);  55             }  56   57         }  58   59         //该方法只负责将新的节点插进树里,不负责维护红黑树性质  60         private Node insertBST(E element){  61             Node pointer = root;  62             Node pointer_parent = null;  63   64             do{  65                 switch (element.compareTo(pointer.element)){  66                     case 0:  67                         System.out.println("已有当前元素!");  68                         return null;  69                     case 1:  70                         pointer_parent = pointer;  71                         pointer = pointer.right;  72                         break;  73                     case -1:  74                         pointer_parent = pointer;  75                         pointer = pointer.left;  76                         break;  77                     default:  78                         break;  79                 }  80             }while (pointer!=null);  81   82             Node child = new Node(element);  83             child.parent = pointer_parent;  84   85             //compareTo的结果只会是1或-1。不会出现0,是0的话,在上方的switch语句里就return了  86             if(pointer_parent.element.compareTo(element)>0){  87                 pointer_parent.left = child;  88             }else {  89                 pointer_parent.right = child;  90             }  91             return child;  92         }  93   94         //该方法负责插入后的维护工作  95         private void fixAfterInsertion(Node node){  96             Node cur,parent,grandparent,uncle;  97             cur = node;  98             //检查是否需要维护树,cur是null的话说明插的元素已存在,就不用维护了  99             if(cur !=null){ 100                 parent = cur.parent; 101                 //cur.print(); 102                 //case2.1:父节点为黑色或为空,不用维护 103                 if(parent==null||parent.color == black){ 104                     return; 105                 }else{//case2.2:父节点为红色,视叔叔节点颜色分类处理 106  107                     //region 先获取U、G节点的引用(这里G必然非空,因为G空必然P为根且黑,那就不会执行到这里) 108                     grandparent = parent.parent; 109                     if(grandparent.left == parent){ 110                         uncle = grandparent.right; 111                     }else { 112                         uncle = grandparent.left; 113                     } 114                     //endregion 115  116                     //case2.2.1:U节点为黑色(NIL节点也是黑色的)。视C、P、G节点的形态处理 117                     if (uncle==null||uncle.color==black){ 118                         //case2.2.1.1:C、P、G形态为“/”、“”。以G为支点右旋或左旋,P变黑、G变红 119                         if(grandparent.element.compareTo(parent.element)==parent.element.compareTo(cur.element)){ 120                             parent.color=black; 121                             grandparent.color=red; 122                             if(grandparent.element.compareTo(parent.element)>0){//“/”形态,右旋 123                                 rightRotate(grandparent); 124                             }else {//“”形态,左旋 125                                 leftRotate(grandparent); 126                             } 127                         }else {//case2.2.1.2:C、P、G形态为“<”、“>”。先以P为支点左旋或右旋,在以P为支点右旋或左旋 128                             cur.color = black; 129                             grandparent.color =red; 130                             if(grandparent.element.compareTo(parent.element)>0){//“<”形态,P左旋后、G右旋 131                                 leftRotate(parent); 132                                 rightRotate(grandparent); 133                             }else {//“>”形态,P右旋后、G左旋 134                                 rightRotate(parent); 135                                 leftRotate(grandparent); 136                             } 137                         } 138                     }else {//case2.2.2:U节点为红色。将P、G、U节点换色,然后cur指向G节点调用维护函数 139                         grandparent.color=red; 140                         parent.color=black; 141                         uncle.color=black; 142                         fixAfterInsertion(grandparent); 143                     } 144  145                 } 146  147             } 148             root.color=black; 149         } 150  151         //左旋方法 152         private void leftRotate(Node node){ 153             Node parent = node.parent; 154             Node child = node.right; 155             Node childLeft = child==null?null:child.left; 156         //子节点上位 157             if(parent==null){//支点为根节点,parent会是空 158                 child.parent = null; 159                 root = child; 160             }else { 161                 if (parent.left == node){ 162                     parent.left = child; 163                     child.parent = parent; 164                 }else { 165                     parent.right = child; 166                     child.parent = parent; 167                 } 168             } 169         //父节点下位 170             child.left = node; 171             node.parent = child; 172         //子树调整 173             node.right = childLeft; 174             if(childLeft!=null){ 175                 childLeft.parent = node; 176             } 177         } 178         //右旋方法 179         private void rightRotate(Node node){ 180             Node parent = node.parent; 181             Node child = node.left; 182             Node childRight = child==null?null:child.right; 183             //子节点上位 184             if(parent==null){//支点为根节点,parent会是空 185                 child.parent = null; 186                 root = child; 187             }else {//支点不是根节点 188                 if (parent.left == node){ 189                     parent.left = child; 190                     child.parent = parent; 191                 }else { 192                     parent.right = child; 193                     child.parent = parent; 194                 } 195             } 196  197             //父节点下位 198             child.right = node; 199             node.parent = child; 200             //子树调整 201             node.left = childRight; 202             if(childRight!=null){ 203                 childRight.parent = node; 204             } 205         } 206  207         //打印红黑树 208         public void printRBT(Node node){ 209  210             if(node!=null){ 211                 printRBT(node.left); 212                 node.print(); 213                 printRBT(node.right); 214             }else { 215                 return; 216             } 217         } 218  219         public static void main(String[] args) { 220  221             //13,8,5,11,6,22,27,25,14,17 另外一组调试数据 222             int[] nums = {1,2,3,4,5,6,7,8,9,10}; 223             RedBlackTree<Element> redBlackTree = new RedBlackTree<Element> (); 224  225             for (int i: nums){ 226                 Element element = new Element(i); 227                 redBlackTree.insert(element); 228             } 229             //打印红黑树 230             redBlackTree.printRBT(redBlackTree.root); 231              232             //删除操作 233             int value = 3; 234             redBlackTree.remove(new Element(value)); 235             System.out.println("删除节点"+value+"后,打印:"); 236              237             //打印红黑树 238             redBlackTree.printRBT(redBlackTree.root); 239         } 240  241 /**——————————  ——   分割线:以下是删除代码   —————————————**/ 242         //从树中删除一个元素的代码 243         public void remove(E element){ 244             Node pointer = getNodeByElement(element); 245             if(pointer==null){ 246                 System.out.print("树中并没有要删除的元素"); 247                 return; 248             } 249             do { 250                 //case1:要删除的节点仅有一个子树,红黑树性质决定该情况下删除的必然是黑节点,且子节点为红色叶子节点 251                 if ((pointer.left==null)!=(pointer.right==null)) { 252                     //要删除的节点的子树(仅为一个红色叶子节点)顶上来并变色 253                     removeOneBranchNode(pointer); 254                     return; 255                 } else {//case2:删除节点为叶子节点 256                     if ((pointer.left == null)&&(pointer.right == null)) { 257                         removeLeafNode(pointer); 258                         return; 259                     } else {//case3:要删除的节点有两个子树 260                         //指针指向后继节点,后继节点element顶替要删除的element。再do一次以判定新指针的case(此时只会是case2、3) 261                         pointer = changePointer(pointer); 262                     } 263                 } 264  265             }while (true); 266         } 267  268         //获取要删除的元素的Node,若返回为null代表树中没有要删除的元素 269         public Node getNodeByElement(E element){ 270             if(root==null){//树为空,返回null 271                 return  null; 272             } 273  274             Node pointer = root; 275             do{ 276                 if(element.compareTo(pointer.element)>0){//大于,指针指向右孩子 277                     pointer = pointer.right; 278                 }else { 279                     if(element.compareTo(pointer.element)<0){//小于,指针指向左孩子 280                         pointer = pointer.left; 281                     }else {//等于,返回当前的节点 282                         return pointer; 283                     } 284                 } 285             }while (pointer!=null); 286             return null; 287         } 288  289         //指针指向后继节点,并用后继节点的element顶替要删除的element,没有后继节点就返回null 290         public Node changePointer(Node pointer){ 291             //指针备份方便替换时找到引用 292             Node pointer_old = pointer; 293             //寻找后继节点 294             pointer = pointer.right; 295             while (pointer.left!=null){ pointer = pointer.left; } 296             pointer_old.element=pointer.element; 297             return pointer; 298         } 299  300     //删除叶子节点,红色的就直接删,黑色的分情况处理 301         public void removeLeafNode(Node pointer){ 302             Node parent = pointer.parent; 303             Node pointer_old = pointer; 304             //case:2.1叶子节点是根节点 305             if(parent==null){ 306                 root=null; 307                 return; 308             } 309             //case:2.2叶子节点是红色的的话直接删除,黑色的要分类处理 310             if(pointer.color==red){ 311                 if(pointer.parent.left==pointer){ 312                     pointer.parent.left=null; 313                 }else { 314                     pointer.parent.right=null; 315                 } 316             }else { 317                 //case2.3:叶子节点是黑色的,视兄弟点分类处理 318                 while (pointer.parent!=null&&pointer.color==black){ 319                     parent = pointer.parent;//在case2.3.2.2下循环,要更新parent 320                     Node brother; 321                     if(pointer.parent.left==pointer){//左叶子节点处理方式 322                         brother = pointer.parent.right; 323                         //case2.3.1:兄弟节点为红色。那么将其转换为黑色 324                         if(brother.color==red){ 325                             brother.color = black; 326                             parent.color = red; 327                             leftRotate(parent); 328                             brother = parent.right; 329                         } 330                         //case2.3.2:兄弟节点为黑色,侄子节点都是黑色(NIL) 331                         if((brother.left == null)&&(brother.right == null)){ 332                             //case2.3.2.1:父节点为红色 333                             if(parent.color==red){ 334                                 parent.color = black; 335                                 brother.color = red; 336                                 break; 337                             }else {//case2.3.2.2:父节点为黑色 338                                 brother.color = red; 339                                 pointer = parent; 340                                 //继续循环 341                             } 342                         }else { 343                             //case2.3.3:兄弟节点为黑色,左侄子为红色 344                             if((brother.color==black)&&brother.left!=null&&brother.left.color==red){ 345                                 brother.left.color = parent.color; 346                                 parent.color = black; 347                                 rightRotate(brother); 348                                 leftRotate(parent); 349                                 //case2.3.4:兄弟节点为黑色,右侄子为红色 350                             }else if((brother.color==black)&&brother.right!=null&&brother.right.color==red){ 351                                 brother.color = parent.color; 352                                 parent.color = black; 353                                 brother.right.color = black; 354                                 leftRotate(parent); 355                             } 356                             break; 357                         } 358                     }else {//右叶子节点处理方式 359                         brother = pointer.parent.left; 360                         //case2.3.1:兄弟节点为红色。那么将其转换为黑色 361                         if(brother.color==red){ 362                             brother.color = black; 363                             parent.color = red; 364                             rightRotate(parent); 365                             brother = parent.left; 366                         } 367                         //case2.3.2:兄弟节点为黑色,侄子节点都是黑色(NIL) 368                         if((brother.left == null)&&(brother.right == null)){ 369                             //case2.3.2.1:父节点为红色 370                             if(parent.color==red){ 371                                 parent.color = black; 372                                 brother.color = red; 373                                 break; 374                             }else {//case2.3.2.2:父节点为黑色 375                                 brother.color = red; 376                                 pointer = parent; 377                                 //继续循环 378                             } 379  380                         }else { 381                             //case2.3.3:兄弟节点为黑色,右侄子为红色 382                             if((brother.color==black)&&brother.right!=null&&brother.right.color==red){ 383                                 brother.right.color = parent.color; 384                                 parent.color = black; 385                                 leftRotate(brother); 386                                 rightRotate(parent); 387                                 //case2.3.4:兄弟节点为黑色,左侄子为红色 388                             }else if((brother.color==black)&&brother.left!=null&&brother.left.color==red){ 389                                 brother.color = parent.color; 390                                 parent.color = black; 391                                 brother.left.color = black; 392                                 rightRotate(parent); 393                             } 394                             break; 395                         } 396                     } 397                 } 398                 //最后别忘了删掉这个节点 399                 if(pointer_old.parent.left == pointer_old){ 400                     pointer_old.parent.left = null; 401                 }else if((pointer_old.parent.right == pointer_old)){ 402                     pointer_old.parent.right = null; 403                 } 404                 pointer_old.parent = null; 405  406             } 407         } 408  409         //删除单分支节点(此时删除节点必为红色,子树仅为一个叶子节点)。子树(就是一个叶子节点)顶上来涂黑即可。 410         public void removeOneBranchNode(Node pointer){ 411             Node child = pointer.left!=null?pointer.left:pointer.right; 412             if(pointer.parent.left==pointer){ 413                 pointer.parent.left = child; 414             }else { 415                 pointer.parent.right = child; 416             } 417             child.parent = pointer.parent; 418             child.color=black; 419         } 420  421  422  423     }

 

上文中泛型E的测试用类及其打印接口:

 1 public class Element implements Comparable<Element> ,PrintToDOS{  2   3     public Element(int value){  4         this.value = value;  5     }  6   7     public int value;  8   9     @Override 10     public void println() { 11         System.out.println(value); 12     } 13  14     @Override 15     public void print() { System.out.print(value); } 16  17     //this大于element返回1,小于返回-1,相等返回0 18     @Override 19     public int compareTo(Element element) { 20         if (this.value>element.value){ 21             return 1; 22         }else { 23             if(this.value<element.value){ 24                 return  -1; 25             }else { 26                 return  0; 27             } 28         } 29     } 30 }

 

打印接口:

1 public interface PrintToDOS { 2     public void print();  //打印值但不换行 3     public void println();//打印值后换行 4 }

 

初次发布的时候忘了加测试结果了QAQ,补上:

 469の一方爬行

 

 

 

最后,本文如有纰漏还请dalao们指正。

469の一方爬行

 

469の一方爬行资料部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 469の一方爬行资料

提供最优质的资源集合

立即查看 了解详情