4 package org.adblocktv.tagsserver.utils.rbtree;
6 import java.util.Iterator;
14 public class RedBlackTree<K
extends Comparable, V> implements java.io.Serializable {
16 private static final int BLACK = 0;
17 private static final int RED = 1;
22 protected class Node
implements java.io.Serializable {
45 protected Node(K key, V value) {
125 public String toString() {
126 return "{ " + key.toString() +
" " + color +
" "
127 + (left != nil ? left.toString() :
"{ null }")
128 + (right != nil ? right.toString() :
"{ null }")
136 private class RedBlackTreeIterator
implements Iterator<Node> {
138 private Node nextNode;
140 private RedBlackTreeIterator() {
141 nextNode = root != nil ? minimum(root) : nil;
145 public boolean hasNext() {
146 return nextNode != nil;
151 Node lastNode = nextNode;
152 nextNode = successor(lastNode);
157 public void remove() {
163 private Node nil =
new Node();
167 private Node root = nil;
171 private int treeSize = 0;
176 private void leftRotate(Node x) {
183 if (x.parent == nil) {
185 }
else if (x == x.parent.left) {
199 private void rightRotate(Node x) {
202 if (y.right != nil) {
206 if (x.parent == nil) {
208 }
else if (x == x.parent.right) {
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;
229 z.parent.parent.color = RED;
232 if (z == z.parent.right) {
236 z.parent.color = BLACK;
237 z.parent.parent.color = RED;
238 rightRotate(z.parent.parent);
241 Node y = z.parent.parent.left;
242 if (y.color == RED) {
243 z.parent.color = BLACK;
245 z.parent.parent.color = RED;
248 if (z == z.parent.left) {
252 z.parent.color = BLACK;
253 z.parent.parent.color = RED;
254 leftRotate(z.parent.parent);
264 private void transplant(Node u, Node v) {
265 if (u.parent == nil) {
267 }
else if (u == u.parent.left) {
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) {
284 x.parent.color = RED;
285 leftRotate(x.parent);
288 if (w.left.color == BLACK && w.right.color == BLACK) {
292 if (w.right.color == BLACK) {
293 w.left.color = BLACK;
298 w.color = x.parent.color;
299 x.parent.color = BLACK;
300 w.right.color = BLACK;
301 leftRotate(x.parent);
305 Node w = x.parent.left;
306 if (w.color == RED) {
308 x.parent.color = RED;
309 rightRotate(x.parent);
312 if (w.right.color == BLACK && w.left.color == BLACK) {
316 if (w.left.color == BLACK) {
317 w.right.color = BLACK;
322 w.color = x.parent.color;
323 x.parent.color = BLACK;
324 w.left.color = BLACK;
325 rightRotate(x.parent);
353 protected void add(Node z) {
358 if (z.key.compareTo(x.key) < 0) {
367 }
else if (z.key.compareTo(y.key) < 0) {
383 while (x.left != nil) {
395 if (x.right != nil) {
396 return minimum(x.right);
399 while (y != nil && x == y.right) {
411 protected void remove(Node z) {
413 int yOrigColor = y.color;
417 transplant(z, z.right);
418 z.parent.updatePath();
419 }
else if (z.right == nil) {
421 transplant(z, z.left);
422 z.parent.updatePath();
424 y = minimum(z.right);
425 yOrigColor = y.color;
430 transplant(y, y.right);
438 x.parent.updatePath();
440 if (yOrigColor == BLACK) {
453 while (x != nil && !x.key.equals(key)) {
454 if (key.compareTo(x.key) < 0) {
468 return new RedBlackTreeIterator();
480 public String toString() {
482 return "RedBlackTree " + root.toString();
484 return "RedBlackTree { null }";