1 package Tree;  2   3 import org.junit.Test;  4   5 class RedBlackTreeNode {  6   7     int key = 0;  8     RedBlackTreeNode left = null;  9     RedBlackTreeNode right = null; 10     RedBlackTreeNode parent = null; 11     // 色域,0表示黑色,1表示红色 12     int color; 13  14     public RedBlackTreeNode(int key) { 15         this.key = key; 16     } 17 } 18  19 /** 20  * 红黑树的四条性质 1,树中的结点要么是红结点要么是黑结点 2,根结点以及叶子结点都是黑结点 3,红结点的父亲结点一定是黑结点 21  * 4,同一层上的结点到叶子结点所经过的路径,黑高度相同,也就是路径上的黑结点个数相同 22  *  23  * @author jinfeng 24  *  25  */ 26 public class RedBlackTree { 27  28     public RedBlackTreeNode nil = new RedBlackTreeNode(-1); 29  30     // 红黑树的查找功能,返回结点的引用 31     public RedBlackTreeNode redBlackTreeSearch(RedBlackTreeNode T, int number) { 32  33         if (T == nil || T.key == number) 34             return T; 35         if (number < T.key) 36             return redBlackTreeSearch(T.left, number); 37         else 38             return redBlackTreeSearch(T.right, number); 39  40     } 41  42     // 在红黑树T中对结点x进行左旋转 43     // 假设结点x的右结点不空 44     public RedBlackTreeNode leftRatation(RedBlackTreeNode T, RedBlackTreeNode x) { 45         // 1,将x的右结点的左子树y.left链接到x的右子树上 46         RedBlackTreeNode y = x.right; 47         x.right = y.left; 48         if (y.left != nil) 49             y.left.parent = x; 50         // 说明x结点是根结点 51         // 2,修改y结点的父指针以及左子树的指针 52         y.parent = x.parent; 53         if (x.parent == nil) { 54             T = y; 55             y.parent = nil; 56         } else if (x.parent.left == x) 57             x.parent.left = y; 58         else 59             x.parent.right = y; 60         y.left = x; 61         // 3,修改x结点的父指针 62         x.parent = y; 63         return T; 64     } 65  66     // 在红黑树T中对结点x进行右旋转 67     // 假设结点x的左结点不空 68     public RedBlackTreeNode rightRatation(RedBlackTreeNode T, RedBlackTreeNode x) { 69         // 1,将x的左结点的右子树y.right链接到x的左子树上 70         RedBlackTreeNode y = x.left; 71         x.left = y.right; 72         if (y.right != nil) 73             y.right.parent = x; 74         // 说明x结点是根结点 75         // 2,修改y结点的父指针以及右子树的指针 76         y.parent = x.parent; 77         if (x.parent == nil) { 78             T = y; 79             y.parent = nil; 80         } else if (x.parent.right == x) 81             x.parent.right = y; 82         else 83             x.parent.left = y; 84         y.right = x; 85         // 3,修改x结点的父指针 86         x.parent = y; 87         return T; 88     } 89  90     // 将结点z插入到红黑树T中 91     public RedBlackTreeNode redBlackTreeInsert(RedBlackTreeNode T, 92             RedBlackTreeNode z) { 93         // 树为空的情况 94         if (T == null) { 95             T = z; 96             T.parent = nil; 97             T.left = nil; 98             T.right = nil; 99             T.color = 0;100             return T;101         }102         // 树非空的情况,假设所有节点都不相同,y始终记录x的父节点103         RedBlackTreeNode y = null, x = T;104         while (x != nil) {105             y = x;106             if (z.key < x.key)107                 x = x.left;108             else109                 x = x.right;110         }111         if (z.key < y.key)112             y.left = z;113         else114             y.right = z;115         z.parent = y;116         z.left = nil;117         z.right = nil;118         z.color = 1;119         return redBlackTreeInsertFixup(T, z);120     }121 122     // 重新上色,以及进行旋转操作,以满足红黑树的性质123     public RedBlackTreeNode redBlackTreeInsertFixup(RedBlackTreeNode T,124             RedBlackTreeNode z) {125         // y用来记录x结点的叔结点的位置126         RedBlackTreeNode y = null;127         while (z.parent.color == 1 && z != T) {128             // 第一大类 ： z的父亲结点是祖父结点的左孩子129             if (z.parent == z.parent.parent.left) {130                 y = z.parent.parent.right;131                 // case 1: z的叔结点y颜色是红色的132                 if (y.color == 1) {133                     z.parent.color = 0;134                     y.color = 0;135                     z.parent.parent.color = 1;136                     z = z.parent.parent;137                 }138                 // case 2: z的叔结点y的颜色是黑色的,同时z是z的父亲的右孩子139                 // 注意: 从case 2可以转化到case 3,这两种情况并不是完全独立的140                 else {141                     if (z.parent.right == z) {142                         z = z.parent;143                         T = leftRatation(T, z);144                     }145                     // case 3: z的叔结点y的颜色是黑色的,同时z是z的父亲的左孩子146                     z.parent.color = 0;147                     z.parent.parent.color = 1;148                     T = rightRatation(T, z.parent.parent);149                 }150             }151             // 第二大类 ： z的父亲结点是祖父结点的右孩子152             else {153                 y = z.parent.parent.left;154                 // case 1: z的叔结点y颜色是红色的155                 if (y.color == 1) {156                     z.parent.color = 0;157                     y.color = 0;158                     z.parent.parent.color = 1;159                     z = z.parent.parent;160                 }161                 // case 2: z的叔结点y的颜色是黑色的,同时z是z的父亲的左孩子162                 // 注意: 从case 2可以转化到case 3,这两种情况并不是完全独立的163                 else {164                     if (z.parent.left == z) {165                         z = z.parent;166                         T = rightRatation(T, z);167                     }168                     // case 3: z的叔结点y的颜色是黑色的,同时z是z的父亲的右孩子169                     z.parent.color = 0;170                     z.parent.parent.color = 1;171                     T = leftRatation(T, z.parent.parent);172                 }173             }174         }175         // 根结点的颜色可能会被赋值为红色,所以这里重新设置颜色176         T.color = 0;177         return T;178     }179 180     // 中序遍历红黑树T181     public void inOrderRedBlackTree(RedBlackTreeNode T) {182         if (T == nil)183             return;184         inOrderRedBlackTree(T.left);185 186         System.out.println("key : " + T.key + " color : " + T.color187                 + ": parent " + T.parent.key + ", left " + T.left.key188                 + ", right " + T.right.key);189         inOrderRedBlackTree(T.right);190     }191 192     @Test193     public void test() {194         // 在函数体内修改红黑树的头结点对象引用,必须同时将其返回,java语法195         RedBlackTreeNode T = null;196         RedBlackTreeNode treeNode = null;197         int[] array = { 1, 2, 5, 7, 8, 11, 14, 15 };198         // 模拟叶子结点,也就是哨兵199         nil.color = 0;200         for (int i = 0; i < array.length; ++i) {201             treeNode = new RedBlackTreeNode(array[i]);202             T = redBlackTreeInsert(T, treeNode);203         }204         inOrderRedBlackTree(T);205         System.out.print(T.key);206 207     }208 209 }