SORU
13 Mart 2011, Pazar


Neden std::map kırmızı-siyah ağaç olarak uygulanır?

Neden std::map red-black tree olarak uygulanır?

Birkaç binary search trees (BSTs) orada dengeli vardır. Tasarım ticaret-off kırmızı-siyah bir ağaç seçiminde neydi?

CEVAP
13 Mart 2011, Pazar


En yaygın muhtemelen iki kendini dengeleme ağaç algoritmaları Red-Black trees AVL trees vardır. Her iki algoritmaları güncelleme/ekleme sonra ağaç dengelemek için ağaç düğümleri yeniden dengeleme gerçekleştirmek için döndürülmüş olduğu dönmeler kavramı kullanın.

Arada her iki algoritmaları Ekle/silme işlemleri O(log n) olması durumunda Kırmızı-Siyah ağaç yeniden dengeleme ve rotasyon O(1) operasyon sırasında CEMİYET buna bir O(log n) operasyon yapma Kırmızı-Siyah ağaç daha verimli bu açıdan yeniden dengeleme sahne ve bir olası sebep olduğunu daha yaygın olarak kullanılan.

Kırmızı-Siyah ağaçların çoğu toplama kütüphaneleri, Java teklifleri ve Microsoft da dahil olmak üzere kullanılır .NET Çerçeve.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Alexey - servant of Christ

    Alexey - ser

    15 EYLÜL 2007
  • Photoshop Pro Help

    Photoshop Pr

    1 Ocak 2007
  • WiseOwlTutorials

    WiseOwlTutor

    21 EKİM 2011