Какое дополнительное вращение необходимо для удаления из сверху вниз 2-3-4 левого дерева красного черного дерева?

Question

Я реализую пакет LLRB, который должен работать в любом из двух режимов: Bottom-Up 2-3 или Top-Down 2-3-4 described by Sedgewick (code - улучшенный код, хотя он имеет дело только с 2- 3 дерева here, благодаря RS для указателя).

Sedgewick дает очень четкое описание операций с деревом для режима 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 LLRBs со следующим:

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

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

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 (т. Е. Ни один из них не имеет дополнительной привязки, например, Sedgewick's java выше и here).

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

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

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

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

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

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

После попытки удалить «-1» без FixUp:

После попытки удалить «16» без FixUp:

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

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

Любые идеи?

Для справки, моя реализация доступна here (Нет, это не 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 деревьев, и в этом объясняется мало различий в поиске (среднее расстояние от корня до узла и SD 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 

Answer 1

Обновленные и проверены

ключевое значение для тестирования этого является то, что реализация не поддерживает удаление несуществующего или ранее удаленный узел! Я слишком долго пытался выяснить, почему мое рабочее решение «сломано». Это можно исправить, выполнив предварительный поиск ключа и вернув false, если его нет в дереве вообще, и это решение было использовано в связанном коде внизу.

Не отображается Sedgewick написал удаление для удаления 2-3-4, которое доступно для публики.Его результаты касаются, в частности, 2-3 деревьев (он делает лишь поверхностное упоминание о 2-3-4 деревьях в том, что их средняя длина пути (и, следовательно, стоимость поиска), как и у других красно-черных деревьев, неотличима от 2-3 случая). Никто другой, похоже, тоже не нашел, поэтому вот что я нашел после отладки проблемы:

Для начала возьмите код Sedgewick и исправьте устаревшие биты. В слайдах here (стр. 31) вы можете видеть, что его код по-прежнему использует старое представление из 4 узлов, где это было сделано с двумя красными слева в строке, а не с балансом. Первый бит написать подпрограмму в 2-3-4 удаления, то, чтобы исправить это, так что мы можем сделать проверку вменяемости, которая поможет нам проверить наши исправления позже:

private boolean is234(Node x) 
{   
    if (x == null) 
     return true; 
    // Note the TD234 check is here because we also want this method to verify 2-3 trees 
    if (isRed(x.right)) 
     return species == TD234 && isRed(x.left); 

    if (!isRed(x.right)) 
     return true; 

    return is234(x.left) && is234(x.right); 
} 

После того, как мы это, мы знаю пару вещей. Во-первых, из статьи видно, что 4 узла не должны быть разбиты при использовании дерева 2-3-4. Во-вторых, есть специальный случай для правого 4-узла на пути поиска. Есть третий специальный случай, о котором не упоминается, и именно тогда, когда вы возвращаетесь к дереву, вы можете оказаться там, где у вас есть h.right.left, который будет красным, что оставит вас недействительными, только повернув влево. Это зеркало для случая, описанного для вставки на стр. 4 документа.

Вращение фикс для 4-узла, необходимо следующим образом:

private Node moveRedLeft(Node h) 
    { // Assuming that h is red and both h.left and h.left.left 
     // are black, make h.left or one of its children red. 
     colorFlip(h); 
     if (isRed(h.right.left)) 
     { 
      h.right = rotateRight(h.right); 

      h = rotateLeft(h); 
      colorFlip(h); 

      if (isRed(h.right.right)) 
      h.right = rotateLeft(h.right); 
     } 
     return h; 
    } 

И это снимает расщепление на 2-3-4, а также добавляет исправление для третьего специального случая

private Node fixUp(Node h) 
{ 
    if (isRed(h.right)) 
    {  
     if (species == TD234 && isRed(h.right.left)) 
     h.right = rotateRight(h.right); 
     h = rotateLeft(h); 
    } 

    if (isRed(h.left) && isRed(h.left.left)) 
     h = rotateRight(h); 

    if (species == BU23 && isRed(h.left) && isRed(h.right)) 
     colorFlip(h); 

    return setN(h); 
} 

Наконец, нам нужно проверить это и убедиться, что он работает. Они не должны быть наиболее эффективными, но, как я обнаружил во время отладки, они должны фактически работать с ожидаемым поведением дерева (т. Е. Не вставлять/удалять повторяющиеся данные)! Я сделал это с помощью тестовых вспомогательных методов. Прокомментированные строки были там, когда я отлаживал, я сломал и проверил дерево на очевидный дисбаланс. Я пробовал этот метод с 100000 узлов, и она выполняла безупречно:

public static boolean Test() 
    { 
     return Test(System.nanoTime()); 
    } 
    public static boolean Test(long seed) 
    { 
     StdOut.println("Seeding test with: " + seed); 
     Random r = new Random(seed); 
     RedBlackBST<Integer, Integer> llrb = new RedBlackBST<Integer,Integer>(TD234); 
     ArrayList<Integer> treeValues = new ArrayList<Integer>(); 
     for (int i = 0; i < 1000; i++) 
     { 
     int val = r.nextInt(); 
     if (!treeValues.contains(val)) 
     { 
      treeValues.add(val); 
      llrb.put(val, val); 
     } 
     else 
      i--; 
     } 
     for (int i = 0; i < treeValues.size(); i++) 
     { 
     llrb.delete(treeValues.get(i)); 
     if (!llrb.check()) 
     { 
      return false; 
     } 
//   StdDraw.clear(Color.GRAY); 
//   llrb.draw(.95, .0025, .008); 
     } 
     return true; 
    } 

Полный исходный код можно найти here.