09 树的进阶 ​

1 private class Node<Key,Value>{
2      //存储键
3      public Key key;
4      //存储值
5      private Value value;
6      //记录左子结点
7      public Node left;
8      //记录右子结点
9      public Node right;
10      //由其父结点指向它的链接的颜色
11      public boolean color;
12
13      public Node(Key key, Value value, Node left,Node right,boolean color) {
14          this.key = key;
15          this.value = value;
16          this.left = left;
17          this.right = right;

18          this.color = color;
19      }
20  }

1 //红黑树代码
2 public class RedBlackTree<Key extends Comparable<Key>, Value> {

3     //根节点
4     private Node root;
5     //记录树中元素的个数
6     private int N;
7     //红色链接
8     private static final boolean RED = true;
9     //黑色链接
10     private static final boolean BLACK = false;
11
12
13     /**
14      * 判断当前节点的父指向链接是否为红色
15      *
16      * @param x
17      * @return
18      */
19     private boolean isRed(Node x) {
20         //空结点默认是黑色链接
21         if (x == null) {
22             return false;
23         }
24         //非空结点需要判断结点color属性的值
25         return x.color == RED;
26     }
27
28     /**
29      * 左旋转
30      *
31      * @param h
32      * @return
33      */
34     private Node rotateLeft(Node h) {
35         //找出当前结点h的右子结点
36         Node hRight = h.right;
37         //找出右子结点的左子结点
38         Node lhRight = hRight.left;
39         //让当前结点h的右子结点的左子结点成为当前结点的右子结点
40         h.right = lhRight;
41         //让当前结点h称为右子结点的左子结点
42         hRight.left = h;
43         //让当前结点h的color编程右子结点的color
44         hRight.color = h.color;
45         //让当前结点h的color变为RED
46         h.color = RED;
47         //返回当前结点的右子结点
48         return hRight;
49     }
50
51     /**
52      * 右旋
53      *
54      * @param h
55      * @return

56      */
57     private Node rotateRight(Node h) {
58         //找出当前结点h的左子结点
59         Node hLeft = h.left;
60         //找出当前结点h的左子结点的右子结点
61         Node rHleft = hLeft.right;
62         //让当前结点h的左子结点的右子结点称为当前结点的左子结点
63         h.left = rHleft;
64         //让当前结点称为左子结点的右子结点
65         hLeft.right = h;
66         //让当前结点h的color值称为左子结点的color值
67         hLeft.color = h.color;
68         //让当前结点h的color变为RED
69         h.color = RED;
70         //返回当前结点的左子结点
71         return hLeft;
72     }
73
74     /**
75      * 颜色反转,相当于完成拆分4-节点
76      *
77      * @param h
78      */
79     private void flipColors(Node h) {
80         //当前结点的color属性值变为RED；
81         h.color = RED;
82         //当前结点的左右子结点的color属性值都变为黑色
83         h.left.color = BLACK;
84         h.right.color = BLACK;
85     }
86
87     /**
88      * 在整个树上完成插入操作
89      *
90      * @param key
91      * @param val
92      */
93     public void put(Key key, Value val) {
94         //在root整个树上插入key-val
95         root = put(root, key, val);
96         //让根结点的颜色变为BLACK
97         root.color = BLACK;
98     }
99
100     /**
101      * 在指定树中，完成插入操作,并返回添加元素后新的树
102      *
103      * @param h
104      * @param key
105      * @param val
106      */
107     private Node put(Node h, Key key, Value val) {
108         if (h == null) {

109             //标准的插入操作，和父结点用红链接相连
110             N++;
111             return new Node(key, val, null, null, RED);
112         }
113
114         //比较要插入的键和当前结点的键
115         int cmp = key.compareTo(h.key);
116         if (cmp < 0) {
117             //继续寻找左子树插入
118             h.left = put(h.left, key, val);
119         } else if (cmp > 0) {
120             //继续寻找右子树插入
121             h.right = put(h.right, key, val);
122         } else {
123             //已经有相同的结点存在，修改节点的值；
124             h.value = val;
125         }
126
127         //如果当前结点的右链接是红色，左链接是黑色，需要左旋
128         if (isRed(h.right) && !isRed(h.left)) {
129             h=rotateLeft(h);
130         }
131
132         //如果当前结点的左子结点和左子结点的左子结点都是红色链接，则需要右旋
133         if (isRed(h.left) && isRed(h.left.left)) {
134             h=rotateRight(h);
135         }
136
137         //如果当前结点的左链接和右链接都是红色，需要颜色变换
138         if (isRed(h.left) && isRed(h.right)) {
139             flipColors(h);
140         }
141         //返回当前结点
142         return h;
143     }
144
145     //根据key，从树中找出对应的值
146     public Value get(Key key) {
147         return get(root, key);
148     }
149
150     //从指定的树x中，查找key对应的值
151     public Value get(Node x, Key key) {
152         //如果当前结点为空，则没有找到,返回null
153         if (x == null) {
154             return null;
155         }
156
157         //比较当前结点的键和key
158         int cmp = key.compareTo(x.key);
159         if (cmp < 0) {
160             //如果要查询的key小于当前结点的key，则继续找当前结点的左子结点；
161             return get(x.left, key);

162         } else if (cmp > 0) {
163             //如果要查询的key大于当前结点的key，则继续找当前结点的右子结点；
164             return get(x.right, key);
165         } else {
166             //如果要查询的key等于当前结点的key，则树中返回当前结点的value。
167             return x.value;
168         }
169
170     }
171
172     //获取树中元素的个数
173     public int size() {
174         return N;
175     }
176
177     //结点类
178     private class Node {
179         //存储键
180         public Key key;
181         //存储值
182         private Value value;
183         //记录左子结点
184         public Node left;
185         //记录右子结点
186         public Node right;
187         //由其父结点指向它的链接的颜色
188         public boolean color;
189
190         public Node(Key key, Value value, Node left, Node right, boolean color) {
191             this.key = key;
192             this.value = value;
193             this.left = left;
194             this.right = right;
195             this.color = color;
196         }
197     }
198 }
199
200 //测试代码
201 public class Test {
202     public static void main(String[] args) throws Exception {
203         RedBlackTree<Integer, String> bt = new RedBlackTree<>();
204         bt.put(4, "二哈");
205         bt.put(1, "张三");
206         bt.put(3, "李四");
207         bt.put(5, "王五");
208         System.out.println(bt.size());
209         bt.put(1,"老三");
210         System.out.println(bt.get(1));
211         System.out.println(bt.size());
212     }
213 }