1:import java.util.*; 2:public class RedBlackTree<T extends Comparable<T>> { 3: /* 4: Red/Black tree implementation based on Java 5: Algorithms in C++, Sedgewick 6: Introduction To Algorithms Cormen, Thomas H. / Leiserson, Charl es E . / Rivest, Ronald L . The MIT Press 07/1990 7: NOTE : LOOK AT END OF FILE TO SEE DIFFERENCES IN TRAVERSAL IDIOMS 8: */ 9: Java 10: public static final int red = 0; 11: public static final int black = 1; 12: 13: // use the python instance variable naming convention for convenience in comparing 14: private int __color; Java 15: private T __val; 16: private RedBlackTree<T> __left; 17: private RedBlackTree<T> __right; 18: 19: private RedBlackTree(RedBlackTree<T> b) { Java 20: __val = b.__val; 21: __left = b.__left; 22: __right = b.__right; 23: __color = red; 24: } Java 25: 26: private void copy(RedBlackTree<T> x) { 27: __val = x.__val; 28: __left = x.__left; 29: __right = x.__right; Java 30: __color = x.__color; 31: } 32: 33: private RedBlackTree<T> RBinsertLeft(T k,int sw) { 34: RedBlackTree<T> l; Java 35: RedBlackTree<T> b; 36: 37: l = __left; 38: if (l == null) { 39: __left = b = new RedBlackTree<T>(k); Java 40: } 41: else { 42: b = l.RBinsert(k,sw); 43: } 44: return b; Java 45: } 46: 47: private RedBlackTree<T> RBinsertRight(T k,int sw) { 48: RedBlackTree<T> r; 49: RedBlackTree<T> b; Java 50: 51: r = __right; 52: if (r == null) { 53: __right = b = new RedBlackTree<T>(k 54: ); Java 55: } 56: else { 57: b = r.RBinsert(k,sw); 58: } 59: return b; Java 60: } 61: 62: private RedBlackTree<T> rotLeft() 63: { 64: RedBlackTree<T> x; Java 65: RedBlackTree<T> me; 66: 67: if (__right == null) return null; 68: // make the changes in a copy of current node __self 69: // on return, the caller will copy in 'me' to current node Java 70: me = new RedBlackTree<T>(this); 71: x = me.__right; 72: me.__right = x.__left; 73: x.__left = me; 74: return x; Java 75: } 76: 77: private RedBlackTree<T> rotRight() 78: { 79: RedBlackTree<T> x; Java 80: RedBlackTree<T> me; 81: 82: if (__left == null) return null; 83: 84: // make the changes in a copy of current node __self Java 85: // on return, the caller will copy in 'me' to current node 86: me = new RedBlackTree<T>(this); 87: x = me.__left; 88: me.__left = x.__right; 89: x.__right = me; Java 90: return x; 91: } 92: 93: private RedBlackTree<T> RBinsert(T k,int sw) { 94: RedBlackTree<T> b = null; Java 95: RedBlackTree<T> x; 96: RedBlackTree<T> l; 97: RedBlackTree<T> ll; 98: RedBlackTree<T> r; 99: RedBlackTree<T> rr; Java 100: 101: // if current node is a 4 node, split it by flipping its colors 102: // if both children of this node are red, change this one to red 103: // and the children to black 104: l = __left; Java 105: r = __right; 106: if ((l != null)&&(l.__color==red)&&(r != null)&&(r.__color==red)) { 107: __color = red; 108: l.__color = black; 109: r.__color = black; Java 110: } 111: 112: // go left or right depending on key relationship 113: if (k.compareTo(__val) < 0) { 114: // recursively insert Java 115: b = RBinsertLeft(k,0); 116: 117: // on the way back up check if a rotation is needed 118: // if search path has two red links with same orientation 119: // do a single rotation and flip the color bits Java 120: l = __left; 121: if ((__color == red)&&(l != null)&&(l.__color == red)&&(sw == 1)) { 122: x = rotRight(); 123: if (x != null) { 124: // copy returned node to 'this' Java 125: copy(x); 126: } 127: } 128: 129: // flip the color bits Java 130: l = __left; 131: if (l != null) { 132: ll = l.__left; 133: if (ll != null) { 134: if ((l.__color == red)&&(ll.__color == red)) { Java 135: x = rotRight(); 136: if (x != null) { 137: copy(x); 138: } 139: __color = black; Java 140: r = __right; 141: if (r != null) { 142: r.__color = red; 143: } 144: } Java 145: } 146: } 147: } 148: else { 149: b = RBinsertRight(k,1); Java 150: 151: // on the way back up check if a rotation is needed 152: // if search path has two red links with same orientation 153: // do a single rotation and flip the color bits 154: r = __right; Java 155: if ((__color == red)&&(r != null)&&(r.__color == red)&&(sw == 0)) { 156: x = rotLeft(); 157: if (x != null) { 158: // copy returned node to 'this' 159: copy(x); Java 160: } 161: } 162: 163: // flip the color bits 164: r = __right; Java 165: if (r != null) { 166: rr = r.__right; 167: if (rr != null) { 168: if ((r.__color == red)&&(rr.__color == red)) { 169: x = rotLeft(); Java 170: if (x != null) { 171: // copy returned node to 'this' 172: copy(x); 173: } 174: __color = black; Java 175: l = __left; 176: if (l != null) { 177: l.__color = red; 178: } 179: } Java 180: } 181: } 182: } 183: 184: return b; Java 185: } 186: 187:// ================================================== 188:// PUBLIC METHODS 189:// ================================================== Java 190: public RedBlackTree(T x) { 191: __val = x; 192: __left = null; 193: __right = null; 194: __color = red; Java 195: } 196: 197: public String toString() { 198: String s = ""; 199: s = "[" + __val + "," + __color + "]"; Java 200: return s; 201: } 202: 203: public T val() { 204: return __val; Java 205: } 206: 207: public int color() { 208: return __color; 209: } Java 210: 211: public RedBlackTree<T> find(T key) { 212: RedBlackTree<T> result = null; 213: if (key == __val) { 214: result = this; Java 215: } 216: else if (key.compareTo(__val) < 0) { 217: if (__left != null) { 218: result = __left.find(key); 219: } Java 220: } 221: else { 222: if (__right != null) { 223: result = __right.find(key); 224: } Java 225: } 226: return result; 227: } 228: 229: public void inorder(NodeVisitor visitor,int depth) { Java 230: if (__left != null) { 231: __left.inorder(visitor,depth+1); 232: } 233: visitor.visit(this,depth); 234: if (__right != null) { Java 235: __right.inorder(visitor,depth+1); 236: } 237: } 238: 239: public RedBlackTree<T> insert(T k) { Java 240: RedBlackTree<T> b; 241: b = RBinsert(k,0); 242: __color = black; 243: return b; 244: } Java 245: 246:/* NODE VISITOR interface from 'NodeVisitor.java' 247: 248:public interface NodeVisitor { 249: public void visit(RedBlackTree node,int depth); Java 250:} 251: 252:*/ 253: 254:// ================================== Java 255:// test program 256:// ================================== 257: public static void main(String[] args) { 258: int[] nodelist = {11,4,8,14,17,6,9,7,16,15,13,5,19,18,12,10,3,20,1}; 259: NodeVisitor v; Java 260: 261: // insert all the data into the tree 262: RedBlackTree<Integer> root = new RedBlackTree<Integer>(2); 263: for(int n:nodelist) { 264: root.insert(n); Java 265: } 266: 267: // anonymous class implementing the NodeVisitor interface 268: v = new NodeVisitor() { 269: public void visit(RedBlackTree node,int depth) { Java 270: if (node.val() != null) { 271: System.out.print("(" + node.val().toString() + ":" + node.color() + ":" + depth + "), "); 272: } 273: } 274: }; Java 275: System.out.print("Java = "); 276: root.inorder(v,0); 277: System.out.println(); 278: 279: RedBlackTree<Integer> x = root.find(16); Java 280: System.out.println(x.toString()); 281: } 282:} 283: