Это вполне разумно ожидать.
Вставки в красное/черное дерево имеют два компонента: базовый компонент Θ (log n) для спуска на лист, чтобы вставить элемент, а затем некоторые дополнительные операции «исправления» для поддержания красного/черного инварианты дерева. Оказывается, этот второй компонент амортизируется O (1), а это означает, что в среднем требуется только постоянное количество работы для исправления, но время от времени работа по исправлению увеличивается.
Если вы видели связь между красными/черными деревьями и 2-3-4 деревьями, это может быть немного легче понять. Вставки в дереве 2-3-4 обычно останавливаются простым добавлением ключа к листовому узлу. Время от времени вы должны разбить 4 узла и развернуть ключ до узла выше в дереве, который обычно останавливается немедленно. Тем не менее, каждый так часто вам придется разделить лист, а затем разбить узел над ним, а затем развернуть ключ двумя слоями вверх. Типичный образец, который вы получите при выполнении таких вставок, - это то, что вы получите серию быстрых операций, затем немного медленнее, затем несколько более быстрых операций, затем немного медленнее, затем несколько более быстрых операций, то, что еще медленнее, чем другие, и т. д. Кажется, вы получаете это в своем заговоре, поэтому я не думаю, что о чем-то беспокоиться.
Надеюсь, это поможет!
Я забыл сказать, что этот сюжет происходит из версии testbench, где время вычисляется, увеличивая счетчик для каждой итерации функции поиска; это делается из-за того, что среда выполнения должна искажать реальное время выполнения, поэтому я уверен, что если существует проблема, то есть в структуру данных/testbench – sscnapoli1926
проверьте, имеет ли дерево минимальные значения для n = 2^k- 1, потому что в этом случае дерево должно быть предварительно сбалансировано, следовательно, будет иметь минимальное время поиска для случайных поисков. когда вы ищете T (n), должно быть в среднем значительным количеством поисковых запросов. –
Да, я уверен, что мое дерево сбалансировано, потому что T (n) вставки довольно близко к логарифмическому поведению. более того, я попытался проверить каждый цикл вставки/поиска, что высота свойства дерева rb <= 2 * соблюдена черная высота, а тест не терпит неудачу. Я также пытаюсь вставить значения интервалов в заказе и искать интервал, который, я уверен, не может существовать (например, Integer.MAX_VALUE, Integer.MAX_VALUE), чтобы заставить алгоритм посещать каждый уровень до тех пор, пока не уйдет, но результаты все те же – sscnapoli1926