Ben bir uygulama LLRB paketi gerekir işlem yapmak için iki modları, Aşağıdan Yukarıya 2-3 ya da Yukarıdan Aşağıya 2-3-4 described by Sedgewick (code geliştirilmiş kod, gerçi ilgili sadece 2-3 ağaç here, teşekkürler SC için işaretçi).

Sedgewick zaman 2-3-4 modu hakkında konuşmak için çok fazla zaman harcıyor, ancak 2-3 modu için ağaç operasyonların çok net bir açıklama sağlar. O da gösterir nasıl basit bir değişiklik sırasını renk çevirme sırasında ekleme değiştirebilir davranış ağacı (ya bölünmüş yolu için 2-3-4 veya bölünmüş yol için 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;
}

Ancak, aşağıdaki 2-3-4 LLRBs üzerinde silme o parlatıcılar:

Bir sonraki sayfada bu kodu silmek tam bir uygulamasıdır() LLRB 2-3 ağaç için. Göre ters yaklaşımı kullanılan Ekle yukarıdan aşağıya 2-3-4 ağaçları: yaptığımız rotasyonlar ve renk çevirir aşağı inerken arama yolu sağlamak için aramaz ucunda bir 2-düğüm, böylece biz sadece silmek düğüm altında. Düzeltme yöntemini kullanıyoruz() yinelemeli çağrılar aşağıdaki renk flip ve dönüş kodunu paylaşmak için Ekle() kodu. Düzeltme ile), sağ eğilimli kırmızı bağlantılar ve arama yolu 4-düğüm dengesiz gidebiliriz, bu koşullar ağacı yolda sabit olacak güvenli. (Bu yaklaşım ayrıca 2-3-4 ağaçları etkilidir, ama arama yolu kapalı değil düğüm 4 düğüm bir zaman ekstra bir dönüş gerektirir.)

Onun sil() fonksiyonu:

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

Benim uygulama doğru tutar LLRB 2-3 değişmezler için tüm ağaç işlemleri 2-3 ağaçları, ama başarısız için bir alt sağ taraflı silmeleri üzerinde 2-3-4 ağaçları (bu silme başarısız sonuç doğru eğilerek kırmızı düğümleri, ama kartopu ağacı dengesizlik ve nihayet null işaretçi kaldırma). Bir anketi örnek kodu anlatılır LLRB ağaçlar içerir ve seçenekler için inşaat ağaçlarda her iki mod, görünüşe göre hiçbiri doğru uygular silinmesi dışında bir 2-3-4 LLRB (yani yok ekstra döndürme ima etmek, örneğin Sedgewick java ve üzeri here).

Bir sorun yaşıyorum bulmaktan tam olarak ne kast etti "ekstra döndürme zaman sağ düğüm aramayı iptal yolu 4-düğüm"; muhtemelen bu bir sola çevirme, Ama nerede ve ne zaman?

Eğer ben sola Döndür Yukarı geçen son 4-düğüm eşdeğer (yani RR düğüm) ya doğru eğilerek 3-düğüm eşdeğer (BR düğüm) ya da çağırmadan önce düzeltme() veya sonunda düzelti işlevi hala aynı değişmeyen çelişki.

İşte buldum en başarısız örneklerinden ağaç Birleşik Devletleri (ilgili en büyük değer 0 öğelerin sıralı ekleme tarafından oluşturulan).

Ağaçların ilk çifti değişmeyen sarmalayan belli ki kırık devlet sonra eleman 15 silinmesi için devlet önce geçiş gösterir.

İkinci aslında yukarıdaki gibi aynı, ama 0..16 (aynı topoloji 15 sonuç silme) 16 silme. Değişmeyen çelişki kök düğüm geçmeyi başarıyor unutmayın.

Anahtar ihlalleri yürüyüş sırasında oluşturulan geri dönmek için nasıl anlamak hedef düğüme ağacı olacak. Aşağıdaki iki ağaç ilk ağacın üstündeki Sol Aşağı bir yürüyüşten sonra nasıl göründüğünü göstermek ve doğru sırasıyla (geri düzeltme ile yürüyüş önce silme olmadan ve()).

Sil '-1' düzelti:olmadan denemeden sonra

Sil '16' düzelti:olmadan denemeden sonra

Çalışırken döndürmek soldaki geri yürümek zaman düğüm tek bir kırmızı görünüyor sağ alt kısmında bir çözüm, ama bu doğru değil anlaşma ile iki kırmızı çocuklara, bir satır, bir önceki bu bir flipColor zaman hem çocuklar kırmızı görünüyor geliştirmek için durumu daha da, ama hala yaprakları bazı değişmezler ihlal etti.

Eğer ben daha fazla olup olmadığını kontrol edin sağ alt sağ alt kırmızı zaman kardeş siyah ve sola çevirme eğer bu doğruysa ben sadece başarısız bir kez, ama bu noktada oldum gerektiren yeni bir teori yerine yeni bir epicycle.

Herhangi bir fikir?

Başvuru için, ben uygulama kullanılabilir here (Java değil).

Takip:

Bu ilgilendiğim bir sebebi de 2-3 LLRB ağaçları 2-3-4 LLRB ağaçları daha verimli olduğu birçok kişi tarafından iddia onaylamak oldu. Benim kıyaslama ekleme ve silme (2-3 %9 oranında daha hızlı hakkında) için bu onaylamıştır, ama bu alım 2-3-4 ağaçları için biraz daha hızlıdır çok buluyorum.

Aşağıdaki kere çalışır: karşısındaki temsilcisi ve tutarlı

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

İlk sütun tezgah adı, ikinci operasyon sayısı, üçüncü sonucudur. İ5M 2.27 üzerinde kriter.

Bende vardı bir göz at şube uzunlukları 2-3 ağaç ve 2-3-4 ağaçları ve küçük olduğunu açıklar alma fark (ortalama mesafeden kök düğüm ve S. D. 1000 ağaç her 10000 rasgele ekler):

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 

Güncellenmiş ve doğrulanmış

Test için kilit öneme sahip bu uygulama, ya da daha önce silinmiş varolmayan bir düğüm silme desteklemiyor. Yol işe benim çözüm oldu neden anlamaya çalışıyorum çok uzun zaman geçirdim"". kırık Bu ağaç hiç değilse anahtarı için ön araştırma yapıyor ve yanlış döndürerek sabit olabilir, ve bu çözüm altındaki bağlı kodu kullanılmıştır.

Yazdı kamuya açık 2-3-4 silinmesi için silme işlemi Sedgewick görünmüyor. Onun sonuçları özellikle anlaşma ile 2-3 ağaçları (o sadece üstünkörü söz 2-3-4 ağaçları onların ortalama yol uzunluğu (ve böylece arama maliyeti) yanı sıra diğer kırmızı-siyah ağaçlar, ayırt edilemez gelen 2-3 harf). Kimse birine kolayca bulmuş görünüyor, ya da, sorun hata ayıklama sonra ne buldum:

Başlamak için, Sedgewick kodu al ve tarihi bit dışarı düzeltmek. Slaytları here (pg 31) gördüğünüz gibi bu kodu hala kullandığı eski gösterimi 4 düğüm neredeydi tarafından yapılıyor olması, iki sol kırmızılar içinde bir satır yerine denge. 2-3-4 Silme bir rutin yazmak için önce biraz, sonra, bizim düzeltmeleri daha sonra doğrulamak yardımcı olacak bir sağlamlık kontrolü yapabiliriz. bunu düzeltmek için:

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

Bu kez biz, bir kaç şey biliyoruz. Bir gazeteden 4 düğüm 2-3-4 ağacı kullanırken yolda kırık olmaması gerektiğini görüyoruz. İki, 4-düğüm arama yolu üzerinde özel bir durum var. Üçüncü bir özel durum değil mi bahsetti, ve o zaman sen dönüyorsun, bir ağaç, Mayıs sonu h.right.left kırmızı, bırak sen geçersiz bir sola çevirme. Bu davanın ayna kağıdı Sayfa 4 eklemek için açıklanmıştır.

4-düğüm ihtiyacınız döndürme düzeltme aşağıdaki gibidir:

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

Ve bu 2-3-4 yanı sıra, üçüncü özel durum için düzeltme ekler üzerinde bölme kaldırır

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

Son olarak, bu test ve çalıştığından emin olmalıyız. En verimli olmak zorunda değiller, ama bu hata ayıklama sırasında buldum, aslında beklenen ağaç davranış (Ekle/sil yinelenen veri değil yani) ile çalışmak zorunda! Test yardımcı bir yöntem ile yaptım. Çizgiler oluşturarak, ve bariz dengesizliği için ağaç Ara kontrol ederdim orada olduğunu yorumladı. 100000 düğümlerle bu yöntemi denedim ve sorunsuz çalıştı:

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

Tam kaynak here bulunabilir.