java - Red-Black tree rebalance problem? -

is there constraint onto compareto method orders objects put standard java treeset (i.e. collection implemented red-black tree)? have

public class ruletuple implements comparable {     string head;     string[] rhs;     public string tostring() {         stringbuffer b = new stringbuffer();         b.append(head+":");          for( string t: rhs )             b.append(" "+t);          return b.tostring();     }     public int compareto(object obj) {         ruletuple src = (ruletuple)obj;         int cmp = head.compareto(src.head);         if( cmp!=0 )             return cmp;         if( rhs.length != src.rhs.length )             return rhs.length - src.rhs.length;         for( int i=0; i<rhs.length; i++ )             if( rhs[i].compareto(src.rhs[i]) != 0 )                 return rhs[i].compareto(src.rhs[i]);         return 0;     }     ... } 

i assumed method mapping object linear order fine, long meets partial order criteria: reflexivity, asymmetry, , transitivity. among transitivity not obvious, seems me if objects compared ranked criteria transitivity follows. (i compare headers first, if identical, compare lengths of rhs, if identical, compare array's elements.)

apparently, ruletuple.compareto() method not consistent, since when deleting "test: test[22,33)" traverses tree in following sequence:

test[22,33): 'having' condition               <-- comparison#1    test: test[4,19) group_by_clause           <-- comparison#2        test: model_clause                     <-- comparison#3            test: group_by_clause               test:               test: test[22,33)            test: group_by_clause test[22,33)  <-- comparison#4; wrong branch!               test: test[4,19)                <-- comparison#5               test: group_by_clause model_clause                   ...        test: test[4,19) group_by_clause model_clause         ...    test[4,19): test[5,8) test[8,11)         ... 

as result fails find , delete object there on tree. intuition correct?

another (often overlooked) condition comparator , comparable "temporary consistence", i.e. result of comparing 2 objects should not change long used keys in treemap (or other structure use comparator/comparable, sorted array used collections.binarysearch, or priorityqueue implemented minimum heap - arrays.sort should not change elements before sorting finished).

this means keys should not change, @ least not in way there order changes.

the reason treemap assumes nodes of binary tree in right order - because of can work in o(log(n)) instead of o(n) lookup , changes.

if have change key, should first remove structure, change it, add again.

(the same valid equals , hashcode of keys in hash-based structures hashmap, way.)

---

as added bonus, here generics-using variant of code:

public class ruletuple implements comparable<ruletuple> {     string head;     string[] rhs;     public string tostring() {         stringbuilder b = new stringbuilder();         b.append(head+":");          for( string t: rhs )             b.append(" "+t);          return b.tostring();     }     public int compareto(ruletuple src) {         int cmp = head.compareto(src.head);         if( cmp!=0 )             return cmp;         if( rhs.length != src.rhs.length )             return rhs.length - src.rhs.length;         for( int i=0; i<rhs.length; i++ ) {             int diff = rhs[i].compareto(src.rhs[i]);             if(diff != 0)                 return diff;         }         return 0;     }     ... } 

i changed stringbuffer stringbuilder (a bit more efficient here not using synchronization) , used 1 compareto in loop. optimize tostring method bit more using 2 appends each + operator here.