Проблема с перебалансировкой красно-черного дерева?

ProgramBox

Проблема с перебалансировкой красно-черного дерева?

Post author:admin
Запись опубликована:11 мая, 2023
Post category:Вопросы по программированию

#java #collections

#java #Коллекции

Вопрос:

Существует ли какое-либо ограничение на метод compareTo, который упорядочивает объекты, помещаемые в стандартный набор деревьев Java (т. Е. коллекцию, реализованную в виде красно-черного дерева)? У меня есть

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

В результате не удается найти и удалить объект, который находится в дереве. Верна ли моя интуиция?

1. Другим условием является «временная согласованность», т. е. результат сравнения двух объектов не должен меняться до тех пор, пока они используются в качестве ключей в TreeMap. Это означает, что ваши ключи не должны меняться по существу.

2. Это может быть ключом (каламбур)! Я выполняю преобразование (заменяю правила) на месте. Ага, при использовании ярлыка всегда возникает проблема…

3. Что происходит, когда this.head == null , но src.head != null ? Я думаю, вы получили бы исключение NullPointerException при переключении точки зрения. Кроме того, вы могли бы подумать о том, чтобы не вызывать rhs[i].compareTo(src.rhs[i]) дважды. (Это всего лишь оптимизация, а не причина вашей проблемы, которую я действительно не понимаю.) Помимо этого (и того, что здесь следует использовать дженерики), ваш метод compareTo выглядит нормально.

4. Чтобы избежать проблемы согласованности: удалите правило из набора / карты, измените его, добавьте снова.

5. Я отредактировал сообщение, поскольку проблема с null не была актуальной. После устранения проблемы с мутацией, как предложил Пауло, код, похоже, работает нормально.

Ответ №1:

Другим (часто упускаемым из виду) условием для компаратора и Comparable является «временная согласованность», т. Е. результат сравнения двух объектов не должен изменяться до тех пор, пока они используются в качестве ключей в TreeMap (или любой другой структуре, где вы используете Comparator / Comparable, например, сортированный массив, используемый для Collections.BinarySearch, или PriorityQueue, реализованный минимальной кучей — даже для Arrays.sort вы не должны изменять элементы до завершения сортировки).

По сути, это означает, что ваши ключи не должны меняться, по крайней мере, не таким образом, чтобы менялся порядок.

Причина в том, что древовидная карта предполагает, что узлы двоичного дерева всегда находятся в правильном порядке — только из-за этого она может работать в 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 метод, используя здесь два добавления для каждого оператора.