【算法】手撕红黑树(上)—— 基本性质以及插入实现(附带代码实现)

移动端点击事件延迟的诞生消亡史

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

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

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

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

 

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

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),红圈节点就是红节点。

 

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

  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,补上:

 

 

 

 

最后,本文如有纰漏还请dalao们指正。(点击这里阅读下篇

 

【算法】手撕红黑树(上)—— 基本性质以及插入实现(附带代码实现)
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

CSS帧动画