紅黑樹重新平衡的問題？

Question

對compareTo方法有任何約束，它將對象放入標準java TreeSet（即實現爲紅黑樹的集合）？我有

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; 
    } 
    ... 
} 

我假定任何方法映射對象成線性順序是細的，只要它滿足偏序的標準：自反，不對稱，和傳遞性。其中只有傳遞性不是立即顯而易見的，但在我看來，如果通過分級標準比較對象，則傳遞性會隨之而來。 （我首先比較標題，如果相同，則比較rhs的長度，如果相同，則比較數組的元素。）

顯然，RuleTuple.compareTo（）方法不一致，因爲刪除「test：test [22 ，33）」，它遍歷樹以下順序：

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) 
     ... 

作爲它未能找到並刪除一個對象，它是有在樹的結果。我的直覺是否正確？

Answer 1

Comparator和Comparable的另一個（經常被忽略的）條件是「臨時一致性」，即比較兩個對象的結果只要在TreeMap中使用它們作爲鍵（或者你使用的任何其他結構Comparator/Comparable類似於用於Collections.binarySearch的排序數組，或者是由最小堆實現的PriorityQueue - 即使對於Arrays.sort，也不應在排序完成之前更改元素）。

這基本上意味着你的鑰匙不應該改變，至少不會改變訂單。

原因是TreeMap假定二叉樹的節點始終處於正確的順序 - 只是因爲它可以在O(log(n))而不是O(n)中查找和更改。

如果您必須更改某個鍵，您應該先將其從結構中刪除，然後進行更改，然後重新添加。

（這同樣適用於equals和像HashMap的基於散列的結構鍵hashCode，順便說一句。）

---

作爲一個額外的好處，這裏是你的代碼的泛型使用變種：

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; 
    } 
    ... 
} 

我也改變StringBuffer來StringBuilder的（更有效的一點這裏不使用同步）和僅一個compareTo在循環使用。您還可以通過在此處爲每個+運算符使用兩個附加點來更好地優化toString方法。