Красно-Черное дерево, проблема с балансом?

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 и hashCode ключей в основанных на хэше структурах, таких как HashMap.)

---

В качестве дополнительного бонуса представлен вариант вашего кода с использованием обобщений:

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, используя два добавления для каждого оператора +.