首页 > > 程序设计 > Java技术 >

数据结构 -- 红黑树精解

2019-01-16 05:50:55来源：博客园阅读 ()

普通二叉查找树

我们知道查找二叉树有着比较好的时间复杂度, 在二叉树接近平衡的时候查找一个元素, 其时间复杂度可以达到nlog(n), 然而...如果插入的元素接近有序呢?

如图

此时这颗二叉查找树的平衡结构遭到了严重的破环, 其查找效率已经接近链表, 那么我们能不能使二叉树变得平衡呢?

当然有: 本篇的主角红黑树是一个自平衡查找二叉树, 红黑树能保证二叉树的左右节点之差不会超过一倍, 这样就能保证其查找二叉树的效率啦

红黑树

红黑树通过几个规定保证二叉树的平衡:

节点是红色或者黑色的
根节点是黑色的
每个叶子节点是黑色的(红黑树的叶子节点指的是null节点)
红色节点的两个子节点都是黑色的(红色节点不能连续)
任意节点到其子节点的路径上的黑色节点都相等

为什么有了这些条件, 红黑树就能保证二叉树的左右节点之差不会超过一倍呢?

由条件4和5知道任一节点到其叶子节点的路径上的黑色节点都相同, 而红色节点的两个子节点颜色都为黑色, 所以红黑树的最短路径为全是黑色, 令其高度为n, 则最长路径为n个黑色节点+n-1个红色节点,所以红黑树能保证二叉树左右节点之差不会超过一倍

如图

创建节点

　　创建一个节点类, 与普通查找二叉树不同, 该节点添加了一个颜色字段

 1 /**
 2  * 红黑树节点
 3  */
 4 class Node {
 5 
 6     /** 节点颜色 */
 7     public Color color;
 8     /** 存储值 */
 9     public Integer val;
10     /** 父节点 */
11     public Node parent;
12     /** 左节点 */
13     public Node left;
14     /** 右节点 */
15     public Node right;
16 
17 }

为了方便后续操作,对节点类进行一些改进

红黑树的叶子节点是null节点, 为了方便判断叶子节点的颜色(黑色), 创建一个特殊节点代替null节点
为节点类添加相应构造方法
为节点类创建两个辅助性方法为当前节点插入左节点: appendLeft(Node) 为当前节点插入右节点: appendRight(Node)
重写toString方法方便显示节点中的属性值

 1 /**
 2  * 红黑树节点
 3  */
 4 class Node {
 5 
 6     /** 创建一个特殊节点代替null节点 方便给他附上颜色 */
 7     public static Node NIL = new Node(Color.BlACK, null, null, null, null);
 8 
 9     /** 节点颜色 */
10     public Color color;
11     /** 存储值 */
12     public Integer val;
13     /** 父节点 */
14     public Node parent;
15     /** 左节点 */
16     public Node left;
17     /** 右节点 */
18     public Node right;
19 
20     public Node() {
21     }
22 
23     public Node(Integer val) {
24         this(Color.RED, val, NIL, NIL, NIL);
25         this.val = val;
26     }
27 
28     public Node(Color color, Integer val, Node parent, Node left, Node right) {
29         super();
30         this.color = color;
31         this.val = val;
32         this.parent = parent;
33         this.left = left;
34         this.right = right;
35     }
36 
37     /** 工具:插入左节点 */
38     public boolean appendLeft(Node node) {
39 
40         if (node == NIL) {
41             System.err.println("添加节点不能为null");
42             return false;
43         }
44         if (this.left != NIL) {
45             System.err.print(this.toString() + " 左子节点已经存在元素 " + this.left.toString());
46             System.err.print(" 不能再插入 " + node.toString() + "\n");
47             return false;
48         }
49         this.left = node;
50         node.parent = this;
51         return true;
52     }
53 
54     /** 工具:插入右节点 */
55     public boolean appendRight(Node node) {
56 
57         if (node == NIL) {
58             System.err.println("添加节点不能为null");
59             return false;
60         }
61         if (this.right != NIL) {
62             System.err.print(this.toString() + " 右子节点已经存在元素 " + this.right.toString());
63             System.err.print(" 不能再插入 " + node.toString() + "\n");
64             return false;
65         }
66         this.right = node;
67         node.parent = this;
68         return true;
69     }
70 
71     @Override
72     public String toString() {
73         return "Node [color=" + color + ", val=" + val + "]";
74     }
75 
76 }

创建一个颜色枚举

1 enum Color {
2     RED, BlACK
3 }

树的旋转

如果我们插入了一颗破坏了红黑树结构的红色节点, 红黑树又是通过怎样的方法, 实现她的自平衡呢?

在介绍平衡方法之前, 先介绍一个基本概念, 树的旋转, 什么是树的旋转? 很简单, 就是一个草根节点逆袭, 替换其父节点的故事, 旋转分为左旋转与右旋转, 其是根据草根节点的位置来的, 草根节点在左边, 则通过右旋操作, 替换掉原父节点的位置, 而原父节点则变为草根节点的左子节点, 左旋操作与之相反

使用一个分解图来详细描述一个左旋操作

注意: 树的旋转并不是特别难以理解, 其中需要稍微注意的有两点

　　1. 需要注意判断祖父节点(pp)与子节点(CL/CR)是否为NIL节点

　　2. 图解中的例子父节点都是祖父节点的左节点, 在设置父节点的引用时, 需要注意判断一下

左旋转

 1     /** 
 2      * 左旋操作
 3      *         pp                              |         pp
 4      *        /                                |         /
 5      *       p                                 |       x(旋转后节点)
 6      *     /   \                               |     /   \
 7      *    L     x(待旋转节点)        == >         |    p     CR
 8      *         / \                             |   /  \
 9      *        CL  CR                           |  L    CL
10      *                                         |
11      *  */
12     private void rotateLeft(Node node) {
13 
14         /* 如果不是根节点 父节点就不是NIL */
15         if (node != root) {
16 
17             Node parent = node.parent;
18             parent.right = node.left;
19             node.left = parent;
20             /* 原节点的父节点指向原父节点的父节点 */
21             node.parent = parent.parent;
22             /* 原节点的父节点指向原父节点 */
23             parent.parent = node;
24             /* 原父节点的父节点的子节点指向自己 */
25             if(node.parent != Node.NIL) {
26                 
27                 /* 原父节点在原祖父节点的左边 */
28                 if(node.parent.left == parent) {
29                     node.parent.left = node;
30                 }
31                 
32                 else {
33                     node.parent.right = node;
34                 }
35             }
36             /* 将原左子节点的父节点指向 原父节点 */
37             if(parent.right != Node.NIL) {
38                 parent.right.parent=parent;
39             }
40         }
41     }

右旋转

 1     /** 
 2      * 右旋操作
 3      *         pp                              |         pp
 4      *        /                                |         /
 5      *       p                                 |       x(旋转后节点)
 6      *     /   \                               |      /  \
 7      *    x     R                == >          |     CL    p
 8      * (待旋转节点)                              |         /  \     
 9      *   / \                                   |        CR   R  
10      * CL   CR                                 |
11      *                                         |
12      *  */
13     private void rotateRight(Node node) {
14 
15         /* 如果不是根节点 父节点就不熟NIL */
16         if (node != root) {
17 
18             Node parent = node.parent;
19             parent.left = node.right;
20             node.right = parent;
21             /* 原节点的父节点指向原祖父节点 */
22             node.parent = parent.parent;
23             /*  */
24             parent.parent = node;
25             /* 原父节点的父节点的子节点指向自己 */
26             if(node.parent != Node.NIL) {
27                 
28                 /* 原父节点在原祖父节点的左边 */
29                 if(node.parent.left == parent) {
30                     node.parent.left = node;
31                 }
32                 
33                 else {
34                     node.parent.right = node;
35                 }
36             }
37             /* 将原右子节点的父节点指向 原父节点 */
38             if(parent.left != Node.NIL) {
39                 parent.left.parent=parent;
40             }
41         }
42     }

节点的插入

　　　插入红黑树节点与插入普通二叉树节点并无太大差别, 注意的是需要设插入节点的颜色应该为红色, 主要代码在于红黑树的调整(insertFixup)

　　　　插入节点的颜色为什么需要设置为红色: 如果插入一个节点, 可能会破坏其规则(主要是规则4和5)，如果插入的节点是黑色则肯定会导致树中黑色节点的个数不平衡，而如果设置其默认颜色为红色, 那么规则5并没有被破坏, 并且不一定会破坏规则5，而是当违反条件时再调整

 1     public boolean insert(Node node) {
 2 
 3         if (node == null || node == Node.NIL || node.val == null) {
 4             System.err.println("插入 节点/值 不能为空");
 5             return false;
 6         }
 7 
 8         /*
 9          * 如果根节点是null 则将节点插入根节点 性质2: 根节点的颜色为黑色
10          */
11         if (this.root == Node.NIL) {
12             node.color = Color.BlACK;
13             this.root = node;
14             return true;
15         }
16 
17         /*
18          * 根据二叉查找树的特性 寻找新节点合适位置 插入节点颜色初始值为红色    */
19         node = new Node(node.val);
20         Node tmp = root;
21         while (true) {
22 
23             /* 如果node.val < tmp.val */
24             if (node.val.compareTo(tmp.val) < 0) {
25                 if (tmp.left == Node.NIL) {
26                     tmp.appendLeft(node);/* 插入节点 */
27                     break;
28                 }
29 
30                 tmp = tmp.left;
31             }
32 
33             /* 如果node.val > tmp.val */
34             else if (node.val.compareTo(tmp.val) > 0) {
35                 if (tmp.right == Node.NIL) {
36                     tmp.appendRight(node);/* 插入节点 */
37                     break;
38                 }
39 
40                 tmp = tmp.right;
41             }
42 
43             /* 否侧 node.val == tmp.val 插入失败 */
44             else {
45                 System.err.println("[ " + node.val + " ] 该值已存在");
46                 return false;
47             }
48         }
49 
50         /* 对插入的元素进行调整 */
51         this.insertFixup(node);
52 
53         return true;
54     }

红黑树的自平衡操作

　　红黑树的节点调整有很多种情况, 但稍微复杂的情况只有2种

1. 当插入节点为根节点时, 根据规则2我们只需要将根节点涂黑就可以了

2. 插入节点的父节点是黑色的, 那么我们不会破坏任何规则, 直接插入就好了

3. 父节点是红色的, 因为插入节点和父节点都是红色的, 所以破坏了规则4, 两个红色节点不能连续, 此时我们看叔叔节点的颜色, 如果叔叔节点是也是红色的, 那么我们只需要将祖父节点涂黑, 将父节点与叔叔节点图红就行了

如果父亲节点或叔叔节点是红色的则祖父节点的颜色必然是黑色的, 由上图看到, 我们将颜色变换以后, 该只二叉树已经变成了一棵正常的红黑树, 但是! 但是! 但是! 祖父节点并非一定是根节点, 我们将祖父节点变为红色后, 当然也有可能导致祖父节点与祖父节点的父节点同时为红色而破坏了性质4, 所以此时我们需要将祖父节点当成插入节点,继续处理该问题

4. 如果父节点是红色, 叔叔节点是黑色时, 此时需要判断新插入节点在父节点的左边还是右边

1. 新插入节点在父节点的右边, 父节点也在祖父节点的右边

如上图, 新插入节点与父节点同在上一级的右边, 此时便不能再用变色的法子使树变的正常了, 需要先将父节点左旋, 然后变色使其恢复红黑树性质

2. 新插入节点在父节点的左, 父节点在祖父节点的右边

对于这种情况, 我们只需要将新插节点进行右旋操作, 看到旋转后的图形是不是似曾相识呢! 没错, 只要我们将原父节点当作新插节点, 此时情况就变的和 4.1的情况一摸一样了

第4种情况中的两个小分支是红黑树插入情况中比较复杂的操作, 当然我只讨论了父节点在祖父节点右边的情况, 其父节点在祖父节点左边与其对称

代码

 1     /** 对插入元素进行调整 */
 2     private void insertFixup(Node node) {
 3 
 4         /*
 5          * if 屏蔽的条件 1. 插入节点不为NIL 2. 插入节点为根节点 只需要将颜色转为黑色即可(性质2) 3. 当前节点是黑色节点 4. 插入节点的父节点为黑色节点 直接插入
 6          * 不需要调整    */
 7         while (node != Node.NIL && node != root && node.color != Color.BlACK && node.parent.color != Color.BlACK) {
 8             Node parent = node.parent;
 9 
10             /* [一]、 调整节点在 父节点的左边 */
11             if (parent.left == node) {
12                 /* 获取祖父节点 */
13                 Node pp = parent.parent;
14                 /* 父节点在祖父节点的左边 */
15                 if (pp != Node.NIL && pp.left == parent) {
16 
17                     /*
18                      * 1) 父节点颜色 == 叔叔节点颜色 ==> 红色 此时只需要变换颜色
19                      */
20                     if (pp.left.color == pp.right.color) {
21                         pp.left.color = Color.BlACK;
22                         pp.right.color = Color.BlACK;
23                         pp.color = Color.RED;
24                         
25                         parent = pp;
26                     }
27 
28                     /*
29                      * 2) 父节点颜色 (红) != 如果叔叔节点(黑) 需要对其进行右旋转
30                      */
31                     else {
32                         this.rotateRight(parent);
33                         /* 改变一下颜色 */
34                         pp.color = Color.RED;
35                         parent.color = Color.BlACK;
36                     }
37 
38                 }
39 
40                 /* 3) 如果父节点在祖父节点的右边 先右旋再左旋 */
41                 else if(pp != Node.NIL && pp.right == parent){
42                     this.rotateRight(node);
43                     // 右旋之后节点变成了上面的对称结构 操作与其相似 在下面[二]解决
44                 }
45             }
46             
47             /* [二]、调整节点在 父节点的右边 
48              *  与上面的处理一样(对称) */
49             else {
50                 /* 获取祖父节点 */
51                 Node pp = parent.parent;
52                 /* 父节点在祖父节点的右边
53                  *     同时解决了 3) 的下半部分问题 */
54                 if (pp != Node.NIL && pp.right == parent) {
55 
56                     /*
57                      * 父节点颜色 == 叔叔节点颜色 ==> 红色 此时任然只需要变换颜色
58                      *  与 1) 一摸一样 代码没变
59                      */
60                     if (pp.left.color == pp.right.color) {
61                         pp.left.color = Color.BlACK;
62                         pp.right.color = Color.BlACK;
63                         pp.color = Color.RED;
64                         
65                         parent = pp;
66                     }
67 
68                     /*
69                      * 父节点颜色 (红) != 如果叔叔节点(黑) 需要对其进行左旋转
70                      *  与 2) 一摸一样 == 改变旋转方向
71                      */
72                     else {
73                         this.rotateLeft(parent);
74                         /* 改变一下颜色 */
75                         pp.color = Color.RED;
76                         parent.color = Color.BlACK;
77                     }
78                 }
79                 
80                 /*
81                  * 父节点在祖父节点的左边
82                  */
83                 else if(pp != Node.NIL && pp.left == parent){
84                     this.rotateLeft(node);
85                     // 此时变成了 [一]、的情况
86                 }
87             }
88             
89             /* 处理完当前节点 父节点可能会破化条件 所以处理父节点 */
90             node = parent;
91         }
92         
93         /* 重新赋值根节点 */
94         if(node.parent == Node.NIL) {
95             this.root = node;
96         }
97         /* 将根节点置为黑色 */
98         this.root.color = Color.BlACK;
99     }

添加一个打印的辅助方法

 1     public void print(Node node) {
 2 
 3         if (node == Node.NIL) {
 4             return;
 5         }
 6         System.out.println(
 7                 "[ 我是:" + node.val + ", 我的父元素是:" + node.parent + ", 左子节点:" + node.left + ", 右子节点:" + node.right + " ]");
 8         print(node.left);
 9         print(node.right);
10     }

测试一下

 1     public static void main(String[] args) {
 2 
 3         RBTree tree = new RBTree();
 4         for (int i = 0; i < 10; i++) {
 5             /* 产生0-19的 10个 随机数 */
 6             int n=(int) (Math.random() * 20);
 7             System.out.print(n+", ");
 8             tree.insert(new Node(n));
 9         }
10         System.out.println();
11         tree.print(tree.root);
12     }

本章源码

  1 package com.wb.dbpackage;
  2 
  3 
  4 /**
  5  * @author WangBing E-mail:2051143520@qq.com
  6  * @version 创建时间：2019年1月13日 下午8:13:12 类说明 -- 红黑树
  7  */
  8 public class RBTree {
  9 
 10     /** 根节点 */
 11     private Node root = Node.NIL;
 12 
 13     /** 
 14      * 左旋操作
 15      *         pp                              |         pp
 16      *           /                                |         /
 17      *       p                                 |       x(旋转后节点)
 18      *     /   \                               |     /   \
 19      *    L     x(待旋转节点)        == >         |    p     CR
 20      *         / \                             |   /  \
 21      *        CL  CR                           |  L    CL
 22      *                                         |
 23      *  */
 24     private void rotateLeft(Node node) {
 25 
 26         /* 如果不是根节点 父节点就不是NIL */
 27         if (node != root) {
 28 
 29             Node parent = node.parent;
 30             parent.right = node.left;
 31             node.left = parent;
 32             /* 原节点的父节点指向原父节点的父节点 */
 33             node.parent = parent.parent;
 34             /* 原节点的父节点指向原父节点 */
 35             parent.parent = node;
 36             /* 原父节点的父节点的子节点指向自己 */
 37             if(node.parent != Node.NIL) {
 38                 
 39                 /* 原父节点在原祖父节点的左边 */
 40                 if(node.parent.left == parent) {
 41                     node.parent.left = node;
 42                 }
 43                 
 44                 else {
 45                     node.parent.right = node;
 46                 }
 47             }
 48             /* 将原左子节点的父节点指向 原父节点 */
 49             if(parent.right != Node.NIL) {
 50                 parent.right.parent=parent;
 51             }
 52         }
 53     }
 54 
 55     /** 
 56      * 右操作
 57      *         pp                              |         pp
 58      *           /                                |         /
 59      *       p                                 |       x(旋转后节点)
 60      *     /   \                               |      /  \
 61      *    x     R                == >          |     CL    p
 62      * (待旋转节点)                              |         /  \     
 63      *   / \                                   |        CR   R  
 64      * CL   CR                                 |
 65      *                                         |
 66      *  */
 67     private void rotateRight(Node node) {
 68 
 69         /* 如果不是根节点 父节点就不熟NIL */
 70         if (node != root) {
 71 
 72             Node parent = node.parent;
 73             parent.left = node.right;
 74             node.right = parent;
 75             /* 原节点的父节点指向原祖父节点 */
 76             node.parent = parent.parent;
 77             /*  */
 78             parent.parent = node;
 79             /* 原父节点的父节点的子节点指向自己 */
 80             if(node.parent != Node.NIL) {
 81                 
 82                 /* 原父节点在原祖父节点的左边 */
 83                 if(node.parent.left == parent) {
 84                     node.parent.left = node;
 85                 }
 86                 
 87                 else {
 88                     node.parent.right = node;
 89                 }
 90             }
 91             /* 将原右子节点的父节点指向 原父节点 */
 92             if(parent.left != Node.NIL) {
 93                 parent.left.parent=parent;
 94             }
 95         }
 96     }
 97 
 98     public boolean insert(Node node) {
 99 
100         if (node == null || node == Node.NIL || node.val == null) {
101             System.err.println("插入 节点/值 不能为空");
102             return false;
103         }
104 
105         /*
106          * 如果根节点是null 则将节点插入根节点 性质2: 根节点的颜色为黑色
107          */
108         if (this.root == Node.NIL) {
109             node.color = Color.BlACK;
110             this.root = node;
111             return true;
112         }
113 
114         /*
115          * 根据二叉查找树的特性 寻找新节点合适位置 插入节点颜色初始值为红色    */
116         node = new Node(node.val);
117         Node tmp = root;
118         while (true) {
119 
120             /* 如果node.val < tmp.val */
121             if (node.val.compareTo(tmp.val) < 0) {
122                 if (tmp.left == Node.NIL) {
123                     tmp.appendLeft(node);/* 插入节点 */
124                     break;
125                 }
126 
127                 tmp = tmp.left;
128             }
129 
130             /* 如果node.val > tmp.val */
131             else if (node.val.compareTo(tmp.val) > 0) {
132                 if (tmp.right == Node.NIL) {
133                     tmp.appendRight(node);/* 插入节点 */
134                     break;
135                 }
136 
137                 tmp = tmp.right;
138             }
139 
140             /* 否侧 node.val == tmp.val 插入失败 */
141             else {
142                 System.err.println("[ " + node.val + " ] 该值已存在");
143                 return false;
144             }
145         }
146 
147         /* 对插入的元素进行调整 */
148         this.insertFixup(node);
149 
150         return true;
151     }
152 
153     /** 对插入元素进行调整 */
154     private void insertFixup(Node node) {
155 
156         /*
157          * if 屏蔽的条件 1. 插入节点不为NIL 2. 插入节点为根节点 只需要将颜色转为黑色即可(性质2) 3. 插入节点的父节点为黑色节点 直接插入
158          * 不需要调整    */
159         while (node != Node.NIL && node != root && node.color != Color.BlACK && node.parent.color != Color.BlACK) {
160             Node parent = node.parent;
161 
162             /* [一]、 调整节点在 父节点的左边 */
163             if (parent.left == node) {
164                 /* 获取祖父节点 */
165                 Node pp = parent.parent;
166                 /* 父节点在祖父节点的左边 */
167                 if (pp != Node.NIL && pp.left == parent) {
168 
169                     /*
170                      * 1) 父节点颜色 == 叔叔节点颜色 ==> 红色 此时只需要变换颜色
171                      */
172                     if (pp.left.color == pp.right.color) {
173                         pp.left.color = Color.BlACK;
174                         pp.right.color = Color.BlACK;
175                         pp.color = Color.RED;
176                         
177                         parent = pp;
178                     }
179 
180                     /*
181                      * 2) 父节点颜色 (红) != 如果叔叔节点(黑) 需要对其进行右旋转
182                      */
183                     else {
184                         this.rotateRight(parent);
185                         /* 改变一下颜色 */
186                         pp.color = Color.RED;
187                         parent.color = Color.BlACK;
188                     }
189 
190                 }
191 
192                 /* 3) 如果父节点在祖父节点的右边 先右旋再左旋 */
193                 else if(pp != Node.NIL && pp.right == parent){
194                     this.rotateRight(node);
195                     // 右旋之后节点变成了上面的对称结构 操作与其相似 在下面[二]解决
196                 }
197             }
198             
199             /* [二]、调整节点在 父节点的右边 
200              *  与上面的处理一样(对称) */
201             else {
202                 /* 获取祖父节点 */
203                 Node pp = parent.parent;
204                 /* 父节点在祖父节点的右边
205                  *     同时解决了 3) 的下半部分问题 */
206                 if (pp != Node.NIL && pp.right == parent) {
207 
208                     /*
209                      * 父节点颜色 == 叔叔节点颜色 ==> 红色 此时任然只需要变换颜色
210                      *  与 1) 一摸一样 代码没变
211                      */
212                     if (pp.left.color == pp.right.color) {
213                         pp.left.color = Color.BlACK;
214                         pp.right.color = Color.BlACK;
215                         pp.color = Color.RED;
216                         
217                         parent = pp;
218                     }
219 
220                     /*
221                      * 父节点颜色 (红) != 如果叔叔节点(黑) 需要对其进行左旋转
222                      *  与 2) 一摸一样 == 改变旋转方向
223                      */
224                     else {
225                         this.rotateLeft(parent);
226                         /* 改变一下颜色 */
227                         pp.color = Color.RED;
228                         parent.color = Color.BlACK;
229                     }
230                 }
231                 
232                 /*
233                  * 父节点在祖父节点的左边
234                  */
235                 else if(pp != Node.NIL && pp.left == parent){
236                     this.rotateLeft(node);
237                     // 此时变成了 [一]、的情况
238                 }
239             }
240             
241             /* 处理完当前节点 父节点可能会破化条件 所以处理父节点 */
242             node = parent;
243         }
244         
245         /* 重新赋值根节点 */
246         if(node.parent == Node.NIL) {
247             this.root = node;
248         }
249         /* 将根节点置为黑色 */
250         this.root.color = Color.BlACK;
251     }
252 
253     public void print(Node node) {
254 
255         if (node == Node.NIL) {
256             return;
257         }
258         System.out.println("[ 我是:" + node.val + ", 我的父元素是:" + node.parent + ", 左子节点:" + node.left + ", 右子节点:" + node.right + " ]");
259         print(node.left);
260         print(node.right);
261     }
262 
263     public static void main(String[] args) {
264 
265         RBTree tree = new RBTree();
266         /* 产生0-19的 10个 随机数 */
267         for (int i = 0; i < 10; i++) {
268             int n=(int) (Math.random() * 19);
269             System.out.print(n+", ");
270             tree.insert(new Node(n));
271         }
272 
273         tree.print(tree.root);
274     }
275 
276 }
277 
278 /**
279  * 红黑树节点
280  */
281 class Node {
282 
283     /** 创建一个特殊节点代替null节点 方便给他附上颜色 */
284     public static Node NIL = new Node(Color.BlACK, null, null, null, null);
285 
286     /** 节点颜色 */
287     public Color color;
288     /** 存储值 */
289     public Integer val;
290     /** 父节点 */
291     public Node parent;
292     /** 左节点 */
293     public Node left;
294     /** 右节点 */
295     public Node right;
296 
297     public Node() {
298     }
299 
300     public Node(Integer val) {
301         this(Color.RED, val, NIL, NIL, NIL);
302         this.val = val;
303     }
304 
305     public Node(Color color, Integer val, Node parent, Node left, Node right) {
306         super();
307         this.color = color;
308         this.val = val;
309         this.parent = parent;
310         this.left = left;
311         this.right = right;
312     }
313 
314     /** 工具:插入左节点 */
315     public boolean appendLeft(Node node) {
316 
317         if (node == NIL) {
318             System.err.println("添加节点不能为null");
319             return false;
320         }
321         if (this.left != NIL) {
322             System.err.print(this.toString() + " 左子节点已经存在元素 " + this.left.toString());
323             System.err.print(" 不能再插入 " + node.toString() + "\n");
324             return false;
325         }
326         this.left = node;
327         node.parent = this;
328         return true;
329     }
330 
331     /** 工具:插入右节点 */
332     public boolean appendRight(Node node) {
333 
334         if (node == NIL) {
335             System.err.println("添加节点不能为null");
336             return false;
337         }
338         if (this.right != NIL) {
339             System.err.print(this.toString() + " 右子节点已经存在元素 " + this.right.toString());
340             System.err.print(" 不能再插入 " + node.toString() + "\n");
341             return false;
342         }
343         this.right = node;
344         node.parent = this;
345         return true;
346     }
347 
348     @Override
349     public String toString() {
350         return "Node [color=" + color + ", val=" + val + "]";
351     }
352 
353 }
354 
355 enum Color {
356     RED, BlACK
357 }