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: