Red-black tree
 All Classes Functions
RedBlackTree.java
1 /*
2  * Created by: Karol Sobczak (napewnotrafi@gmail.com)
3  */
4 package org.adblocktv.tagsserver.utils.rbtree;
5 
6 import java.util.Iterator;
7 
8 /**
9  * A minimalist implementation of a red black tree.
10  * @param K a type of nodes keys
11  * @param V a type of nodes values
12  * @author Karol Sobczak
13  */
14 public class RedBlackTree<K extends Comparable, V> implements java.io.Serializable {
15 
16  private static final int BLACK = 0;
17  private static final int RED = 1;
18 
19  /**
20  * A Red Black tree node class.
21  */
22  protected class Node implements java.io.Serializable {
23 
24  private K key;
25  private V value;
26  private int color;
27  private Node left;
28  private Node right;
29  private Node parent;
30 
31  /**
32  * Initializes a nil node.
33  */
34  private Node() {
35  color = BLACK;
36  left = this;
37  right = this;
38  }
39 
40  /**
41  * Initializes an internal tree node.
42  * @param key a key
43  * @param value a stored value
44  */
45  protected Node(K key, V value) {
46  this.key = key;
47  this.value = value;
48  this.color = RED;
49  this.left = nil;
50  this.right = nil;
51  }
52 
53  /**
54  * Returns a key.
55  * @return a key
56  */
57  protected K getKey() {
58  return key;
59  }
60 
61  /**
62  * Returns a stored value.
63  * @return a stored value
64  */
65  protected V getInternalValue() {
66  return value;
67  }
68 
69  /**
70  * Sets a stored value.
71  * @param value a new stored value
72  */
73  protected void setInternalValue(V value) {
74  this.value = value;
75  }
76 
77  /**
78  * Returns a left child node.
79  * @return a left child node
80  */
81  protected Node getLeftChild() {
82  return left;
83  }
84 
85  /**
86  * Returns a right child node.
87  * @return a right child node
88  */
89  protected Node getRightChild() {
90  return right;
91  }
92 
93  /**
94  * Returns a parent node.
95  * @return a parent node
96  */
97  protected Node getParent() {
98  return parent;
99  }
100 
101  /**
102  * A method called when a tree structure has changed and the node
103  * has been affected. All nodes up to a root of the tree should be updated.
104  */
105  protected void updatePath() {
106  }
107 
108  /**
109  * A method called when a tree structure has changed and the node
110  * has been affected. Only this node should be updated.
111  */
112  protected void updateSingle() {
113  }
114 
115  /**
116  * A method called when a tree structure has changed because of nodes
117  * rotation and the node has been affected. At least this node should
118  * be updated. Depending on a data structure all nodes on a path
119  * to a root of the tree might also need to be updated.
120  */
121  protected void rotateUpdate() {
122  }
123 
124  @Override
125  public String toString() {
126  return "{ " + key.toString() + " " + color + " "
127  + (left != nil ? left.toString() : "{ null }")
128  + (right != nil ? right.toString() : "{ null }")
129  + " }";
130  }
131  }
132 
133  /**
134  * An iterator implementation for red-black tree.
135  */
136  private class RedBlackTreeIterator implements Iterator<Node> {
137 
138  private Node nextNode;
139 
140  private RedBlackTreeIterator() {
141  nextNode = root != nil ? minimum(root) : nil;
142  }
143 
144  @Override
145  public boolean hasNext() {
146  return nextNode != nil;
147  }
148 
149  @Override
150  public Node next() {
151  Node lastNode = nextNode;
152  nextNode = successor(lastNode);
153  return lastNode;
154  }
155 
156  @Override
157  public void remove() {
158  }
159  }
160  /**
161  * A nil node.
162  */
163  private Node nil = new Node();
164  /**
165  * A root node.
166  */
167  private Node root = nil;
168  /**
169  * A current size of the red-black tree.
170  */
171  private int treeSize = 0;
172 
173  /**
174  * Makes a node left child of its current right child.
175  */
176  private void leftRotate(Node x) {
177  Node y = x.right;
178  x.right = y.left;
179  if (y.left != nil) {
180  y.left.parent = x;
181  }
182  y.parent = x.parent;
183  if (x.parent == nil) {
184  root = y;
185  } else if (x == x.parent.left) {
186  x.parent.left = y;
187  } else {
188  x.parent.right = y;
189  }
190  y.left = x;
191  x.parent = y;
192  x.updateSingle();
193  y.rotateUpdate();
194  }
195 
196  /**
197  * Makes a node right child of its current left child.
198  */
199  private void rightRotate(Node x) {
200  Node y = x.left;
201  x.left = y.right;
202  if (y.right != nil) {
203  y.right.parent = x;
204  }
205  y.parent = x.parent;
206  if (x.parent == nil) {
207  root = y;
208  } else if (x == x.parent.right) {
209  x.parent.right = y;
210  } else {
211  x.parent.left = y;
212  }
213  y.right = x;
214  x.parent = y;
215  x.updateSingle();
216  y.rotateUpdate();
217  }
218 
219  /**
220  * Fixes the red-black tree after an addition operation.
221  */
222  private void addFixup(Node z) {
223  while (z.parent.color == RED) {
224  if (z.parent == z.parent.parent.left) {
225  Node y = z.parent.parent.right;
226  if (y.color == RED) {
227  z.parent.color = BLACK;
228  y.color = BLACK;
229  z.parent.parent.color = RED;
230  z = z.parent.parent;
231  } else {
232  if (z == z.parent.right) {
233  z = z.parent;
234  leftRotate(z);
235  }
236  z.parent.color = BLACK;
237  z.parent.parent.color = RED;
238  rightRotate(z.parent.parent);
239  }
240  } else { //left <-> right symmetry
241  Node y = z.parent.parent.left;
242  if (y.color == RED) {
243  z.parent.color = BLACK;
244  y.color = BLACK;
245  z.parent.parent.color = RED;
246  z = z.parent.parent;
247  } else {
248  if (z == z.parent.left) {
249  z = z.parent;
250  rightRotate(z);
251  }
252  z.parent.color = BLACK;
253  z.parent.parent.color = RED;
254  leftRotate(z.parent.parent);
255  }
256  }
257  }
258  root.color = BLACK;
259  }
260 
261  /**
262  * Replaces a subtree with root u with a subtree with root v.
263  */
264  private void transplant(Node u, Node v) {
265  if (u.parent == nil) {
266  root = v;
267  } else if (u == u.parent.left) {
268  u.parent.left = v;
269  } else {
270  u.parent.right = v;
271  }
272  v.parent = u.parent;
273  }
274 
275  /**
276  * Fixes the red-black tree after a removal operation.
277  */
278  private void removeFixup(Node x) {
279  while (x != root && x.color == BLACK) {
280  if (x == x.parent.left) {
281  Node w = x.parent.right;
282  if (w.color == RED) {
283  w.color = BLACK;
284  x.parent.color = RED;
285  leftRotate(x.parent);
286  w = x.parent.right;
287  }
288  if (w.left.color == BLACK && w.right.color == BLACK) {
289  w.color = RED;
290  x = x.parent;
291  } else {
292  if (w.right.color == BLACK) {
293  w.left.color = BLACK;
294  w.color = RED;
295  rightRotate(w);
296  w = x.parent.right;
297  }
298  w.color = x.parent.color;
299  x.parent.color = BLACK;
300  w.right.color = BLACK;
301  leftRotate(x.parent);
302  x = root;
303  }
304  } else { //left <-> right symmetry
305  Node w = x.parent.left;
306  if (w.color == RED) {
307  w.color = BLACK;
308  x.parent.color = RED;
309  rightRotate(x.parent);
310  w = x.parent.left;
311  }
312  if (w.right.color == BLACK && w.left.color == BLACK) {
313  w.color = RED;
314  x = x.parent;
315  } else {
316  if (w.left.color == BLACK) {
317  w.right.color = BLACK;
318  w.color = RED;
319  leftRotate(w);
320  w = x.parent.left;
321  }
322  w.color = x.parent.color;
323  x.parent.color = BLACK;
324  w.left.color = BLACK;
325  rightRotate(x.parent);
326  x = root;
327  }
328  }
329  }
330  x.color = BLACK;
331  }
332 
333  /**
334  * Returns a nil node.
335  * @return a nil node
336  */
337  protected Node getNilNode() {
338  return nil;
339  }
340 
341  /**
342  * Returns a root node.
343  * @return a root node
344  */
345  protected Node getRootNode() {
346  return root;
347  }
348 
349  /**
350  * Adds a new node into the red-black tree.
351  * @param z a new node
352  */
353  protected void add(Node z) {
354  Node y = nil;
355  Node x = root;
356  while (x != nil) {
357  y = x;
358  if (z.key.compareTo(x.key) < 0) {
359  x = x.left;
360  } else {
361  x = x.right;
362  }
363  }
364  z.parent = y;
365  if (y == nil) {
366  root = z;
367  } else if (z.key.compareTo(y.key) < 0) {
368  y.left = z;
369  } else {
370  y.right = z;
371  }
372  z.updatePath();
373  addFixup(z);
374  treeSize++;
375  }
376 
377  /**
378  * Returns a node with a minimum value for a subtree.
379  * @param x a root of a subtree
380  * @return a node with a minimum value
381  */
382  protected Node minimum(Node x) {
383  while (x.left != nil) {
384  x = x.left;
385  }
386  return x;
387  }
388 
389  /**
390  * Returns a node successor.
391  * @param x a node for which a successor should be found
392  * @return a successor for a node x or nil if such node does not exists
393  */
394  protected Node successor(Node x) {
395  if (x.right != nil) {
396  return minimum(x.right);
397  } else {
398  Node y = x.parent;
399  while (y != nil && x == y.right) {
400  x = y;
401  y = y.parent;
402  }
403  return y;
404  }
405  }
406 
407  /**
408  * Removes a node from a tree.
409  * @param z a node to be removed
410  */
411  protected void remove(Node z) {
412  Node y = z;
413  int yOrigColor = y.color;
414  Node x;
415  if (z.left == nil) {
416  x = z.right;
417  transplant(z, z.right);
418  z.parent.updatePath();
419  } else if (z.right == nil) {
420  x = z.left;
421  transplant(z, z.left);
422  z.parent.updatePath();
423  } else {
424  y = minimum(z.right);
425  yOrigColor = y.color;
426  x = y.right;
427  if (y.parent == z) {
428  x.parent = y;
429  } else {
430  transplant(y, y.right);
431  y.right = z.right;
432  y.right.parent = y;
433  }
434  transplant(z, y);
435  y.left = z.left;
436  y.left.parent = y;
437  y.color = z.color;
438  x.parent.updatePath();
439  }
440  if (yOrigColor == BLACK) {
441  removeFixup(x);
442  }
443  treeSize--;
444  }
445 
446  /**
447  * Searches for a node containing a given key.
448  * @param key a key to be found
449  * @return a node containing a given key or nil if such node does not exist
450  */
451  protected Node search(K key) {
452  Node x = root;
453  while (x != nil && !x.key.equals(key)) {
454  if (key.compareTo(x.key) < 0) {
455  x = x.left;
456  } else {
457  x = x.right;
458  }
459  }
460  return x;
461  }
462 
463  /**
464  * Returns an iterator for the red-black tree nodes (in ascending order).
465  * @return an iterator for the red-black tree nodes (in ascending order)
466  */
467  protected Iterator<Node> nodesIterator() {
468  return new RedBlackTreeIterator();
469  }
470 
471  /**
472  * Returns a current red-black tree size.
473  * @return a current red-black tree size
474  */
475  public int size() {
476  return treeSize;
477  }
478 
479  @Override
480  public String toString() {
481  if (root != nil) {
482  return "RedBlackTree " + root.toString();
483  } else {
484  return "RedBlackTree { null }";
485  }
486  }
487 }