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

Ответ 1

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

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

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

Для начала возьмите код Sedgewick и исправьте устаревшие биты. В слайдах здесь (стр. 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- node на пути поиска. Там есть третий специальный случай, который не упоминается, и тогда вы возвращаетесь к дереву, вы можете оказаться там, где у вас h.right.left будет красный, что оставит вас недействительными, просто повернув влево. Это зеркало для случая, описанного для вставки на стр. 4 документа.

Требуется исправление вращения для 4- node:

    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;
   }

Полный источник можно найти здесь.