Какой дополнительный поворот требуется для удаления из Верхнего -Вниз 2 -3 -4 Влево -наклоненного Красного Черного дерева?

Я реализовал пакет LLRB, который должен иметь возможность работать в любом из двух режимов: нижний -верхний 2 -3 или верхний -нижний 2 -3 -4 , описанный Седжвик(код-улучшенный код, хотя он имеет дело только с 2 -3 деревьями здесь , спасибо RS за указатель ).

Седжвик дает очень четкое описание операций с деревом для режима 2 -3, хотя он тратит много времени на обсуждение режима 2 -3 -4. Он также показывает, как простое изменение порядка переключения цветов во время вставки может изменить поведение дерева (: оно либо расщепляется при спуске на 2 -3 -4, либо расщепляется на пути вверх на 2 -3):

private Node insert(Node h, Key key, Value value)
{
    if (h == null)
        return new Node(key, value);

    // Include this for 2-3-4 trees
    if (isRed(h.left) && isRed(h.right)) colorFlip(h);

    int cmp = key.compareTo(h.key);

    if (cmp == 0)     h.val = value;
    else if (cmp < 0) h.left = insert(h.left, key, value);
    else              h.right = insert(h.right, key, value);

    if (isRed(h.right) && !isRed(h.left))    h = rotateLeft(h);
    if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);

    // Include this for 2-3 trees
    if (isRed(h.left) && isRed(h.right)) colorFlip(h);

    return h;
}

Однако он замалчивает делецию в 2 -3 -4 LLRB со следующим:

The code on the next page is a full implementation of delete() for LLRB 2-3 trees. It is based on the reverse of the approach used for insert in top-down 2-3-4 trees: we perform rotations and color flips on the way down the search path to ensure that the search does not end on a 2-node, so that we can just delete the node at the bottom. We use the method fixUp() to share the code for the color flip and rotations following the recursive calls in the insert() code. With fixUp(), we can leave right-leaning red links and unbalanced 4-nodes along the search path, secure that these conditions will be fixed on the way up the tree. (The approach is also effective 2-3-4 trees, but requires an extra rotation when the right node off the search path is a 4-node.)

Его функция удаления ():

private Node delete(Node h, Key key)
{
    if (key.compareTo(h.key) < 0)
        {
            if (!isRed(h.left) && !isRed(h.left.left))
            h = moveRedLeft(h);
            h.left = delete(h.left, key);
        }
    else
        {
            if (isRed(h.left))
                h = rotateRight(h);
            if (key.compareTo(h.key) == 0 && (h.right == null))
                return null;
            if (!isRed(h.right) && !isRed(h.right.left))
                h = moveRedRight(h);
            if (key.compareTo(h.key) == 0)
                {
                    h.val = get(h.right, min(h.right).key);
                    h.key = min(h.right).key;
                    h.right = deleteMin(h.right);
                }
            else h.right = delete(h.right, key);
        }
    return fixUp(h);
}

Моя реализация правильно поддерживает инварианты LLRB 2 -3 для всех операций с деревьями на 2 -3 деревьях, но терпит неудачу для подкласса правосторонних -удалений на 2 -3 -4 деревьях (этих неудачные удаления приводят к наклону вправо красных узлов, но к дисбалансу снежного кома к дереву и, наконец, к разыменованию нулевого указателя ). Из обзора примера кода, который обсуждает деревья LLRB и включает варианты построения деревьев в любом режиме, кажется, что ни один из них правильно не реализует удаление из 2 -3 -4 LLRB (, т. е. ни один из них не имеет дополнительного вращения упоминается, напр. Ява Седжвика выше и здесь).

Мне трудно понять, что именно он имеет в виду под «дополнительным вращением, когда правый узел вне пути поиска — это узел 4 -»; предположительно это поворот влево, но где и когда?

Если я поверну влево, пройдя вверх мимо 4 -узла, эквивалентного (, т. е. узла RR )или наклоненного вправо 3 -узла, эквивалентного (узла BR ), либо перед вызовом fixUp (), либо в в конце функции fixUp я все еще получаю то же инвариантное противоречие.

Вот состояния дерева наименьших неудачных примеров, которые я нашел (, сгенерированных последовательной вставкой элементов от 0 до соответствующего максимального значения ).

Первая пара деревьев показывает переход от инвариантного -конформного состояния до удаления элемента 15 к явно нарушенному состоянию после.

Второй по существу такой же, как и выше, но с удалением 16 из 0..16 (удаление 15 приводит к той же топологии ). Обратите внимание, что инвариантному противоречию удается пересечь корневой узел.

Ключом будет понимание того, как отменить нарушения, сгенерированные во время обхода дерева к целевому узлу. Следующие два дерева показывают, как первое дерево выше выглядит после обхода слева и справа соответственно (без удаления и перед возвратом вверх с помощью fixUp ()).

После попытки удалить '-1' без fixUp:

После попытки удалить '16' без fixUp:

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

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

Любые идеи?

Для справки, моя реализация доступна здесь(Нет, это не Java ).

Следуйте -вверх:

Частично я заинтересовался этим, чтобы подтвердить утверждение многих, что 2 -3 дерева LLRB более эффективны, чем 2 -3 -4 дерева LLRB. Мой бенчмаркинг подтвердил, что вставка и удаление (2 -3 примерно на 9% быстрее ), но я обнаружил, что извлечение немного быстрее для 2 -3 -4 деревьев.

Следующие значения времени являются репрезентативными и одинаковыми для всех прогонов:

BU23:
BenchmarkInsert        1000000        1546 ns/op
BenchmarkDelete        1000000        1974 ns/op
BenchmarkGet           5000000         770 ns/op

TD234:
BenchmarkInsert        1000000        1689 ns/op
BenchmarkDelete        1000000        2133 ns/op
BenchmarkGet           5000000         753 ns/op

Первая колонка — название стенда, вторая — количество операций, третья — результат. Бенчмарк на i5M 2.27.

Я взглянул на длины ветвей для 2 -3 деревьев и 2 -3 -4 деревьев, и это мало что объясняет разницу в извлечении (среднего расстояния от корня до узла и С.Д. из 1000 деревьев по 10000 случайных вставок в каждом):

Means:
TD234 leafs  BU23 leafs 
 12.88940     12.84681 
TD234 all    BU23 all 
 11.79274     11.79163 

StdDev:
TD234 leafs  BU23 leafs 
 1.222458     1.257344 
TD234 all    BU23 all 
 1.874335     1.885204