Boyut
Karşılaştırmalar

İşlem Ortalama En kötü durum

Veri yapıları hakkında daha fazla bilgi

Veri yapısı görselleştirici

Veri yapısı, en sık sorulan soruların hızla yanıtlanması için veriyi saklama biçimidir. Yığından kırmızı-siyah ağaca kadar on bir klasik yapıdan birini seçin, bir değer yazın ve bir işleme basın. Her adım ekranda oynar: hangi düğümün karşılaştırıldığı, hangi bağlantının değiştiği, bir ağacın neden döndüğü ya da bir değerin neden yükseldiği, ne olduğunu söyleyen bir cümleyle birlikte. Kutucuklar her işlemin yaptığı işi sayar, bir tablo da çalışma süresini verir. Bir yapı seçin, bir değer yazın ve bir işleme basın. Her işlem adım adım oynatılır: vurgulanan düğümler neyin karşılaştırıldığını, taşındığını ya da değiştiğini gösterir; resmin altındaki satır ne olduğunu ve nedenini söyler. Geri, Adım, Oynat ve Son adımları yeniden gezer. Rastgele doldur ve Temizle baştan başlar, Geri al bir işlemi geri alır. Kutucuklar boyutu, ağaçların yüksekliğini, son işlemin yaptığı işi (karşılaştırmalar, yoklamalar ya da izlenen ebeveyn bağlantıları) ve yapı için önemli bir sayıyı gösterir; tablo her işlemin çalışma süresini verir.

Nasıl çalışır

  1. İkili arama ağacı, özet tablosu ya da trie gibi bir yapı seçin. Rastgele içerikle başlar; Rastgele doldur ve Temizle baştan başlar.
  2. Bir değer yazın ve bir işleme basın: push, kuyruğa ekle, ekle, sil, ara, bir dolaşma, union ya da find. Adımlar kendiliğinden oynar; Geri, Adım, Oynat ve Son onları yeniden gezer.
  3. Resmin altındaki satırda her adımın ne yaptığını okuyun, kutucuklarda boyutu, yüksekliği ve son işlemin işini izleyin, tablodaki çalışma sürelerini karşılaştırın.

Listeler, yığınlar ve kuyruklar

En basit yapılar öğeleri sıra hâlinde tutar. Yığın yalnızca bir uçta çalışır, bu yüzden en son giren öğe ilk çıkar, tıpkı üst üste konmuş tabaklar gibi; kuyruk arkaya ekler ve önden alır, tıpkı bir gişe önündeki sıra gibi. Buradaki kuyruk dairesel bir arabellekte yaşar: ön ve arka sabit bir dizinin etrafında döner ve sondan sonra başa geçer; arabellek dolunca öğeler iki kat büyük bir arabelleğe kopyalanır. Bağlı liste düğümleri işaretçilerle bağlar; başa eklemek hiçbir şeye mal olmaz, ama kuyruğu ya da bir indeksi bulmak için bağlantıları tek tek izlemek gerekir.

Ağaçlar, heap'ler, özet tabloları ve kümeler

İkili arama ağacı küçük değerleri solda, büyükleri sağda tutar; böylece ağaç gür kaldığı sürece bir arama her adımda adayları yarıya indirir. AVL ve kırmızı-siyah ağaçlar bunu, izleyebileceğiniz ve durumlarına göre adlandırılmış döndürmelerle sağlar. Heap yalnızca en küçük ya da en büyük değeri tepede tutar; bir öncelik kuyruğunun ihtiyacı da bundan ibarettir. Özet tablosu anahtardan hesaplanan bir kovaya doğrudan atlar ve çakışmalarla başa çıkmak zorundadır; trie kelimelerin öneklerini paylaşır; union-find iki öğenin aynı kümeye ait olup olmadığını neredeyse sabit sürede söyler.

Sık sorulan sorular

Hangi veri yapısını kullanmalıyım?

En sık sorduğunuz sorulara bağlıdır. Öğeler geliş sırasıyla ya da tersiyle işleniyorsa yığın ya da kuyruk; bir anahtarı aramak için özet tablosu; anahtarları sıralı ya da en yakın anahtarı da istiyorsanız AVL veya kırmızı-siyah ağaç gibi dengeli bir arama ağacı; her zaman yalnızca en küçük ya da en büyük öğe gerekiyorsa heap; kelimeler ve önekler için trie; birleşen grupları izlemek için union-find.

AVL ağacı ile kırmızı-siyah ağaç arasındaki fark nedir?

İkisi de ikili arama ağacını sığ tutar, böylece her arama, ekleme ve silme log n ile orantılı süre alır. AVL ağacı daha sıkı dengelenir; her düğümün iki tarafının yükseklikleri en fazla bir farklıdır, bu yüzden aramalar biraz daha hızlıdır. Kırmızı-siyah ağaç daha fazla esneklik tanır ve değiştiğinde daha az döndürme gerektirir; birçok standart kütüphanenin sıralı eşlemeleri ve kümeleri için onu kullanmasının nedeni budur.

Özet tablosu en kötü durumda neden yavaş olabilir?

Birçok anahtar aynı kovaya düşerse, bir arama onları tek tek kontrol etmek zorunda kalır, tıpkı bir listede olduğu gibi. İyi bir özet fonksiyonu anahtarları eşit dağıtır ve tablo fazla dolmadan büyür; böylece bir arama ortalama sabit süre alır. Aynı rakamla biten sayılarla ya da birbirinin anagramı olan kelimelerle 10 boyutlu bir tablo deneyin ve çakışmaların nasıl biriktiğini görün.

AVL düğümlerinin yanındaki sayılar ne anlama gelir?

Bunlar denge çarpanlarıdır: bir düğümün sol alt ağacının yüksekliği eksi sağ alt ağacının yüksekliği. Bir AVL ağacında her denge çarpanı −1, 0 ya da +1 olmalıdır. Bir ekleme ya da silme bunlardan birini +2 ya da −2 yaptığında ağaç o düğümde döner; durum (LL, RR, LR ya da RL) fazladan yüksekliğin hangi yöne eğildiğini söyler ve bir mi iki mi döndürme gerektiğine karar verir.

Bir sunucuya bir şey gönderiliyor mu?

Hayır. Her işlem tarayıcınızda çalışır ve her yapının içeriği bu tarayıcının yerel depolamasına kaydedilir.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Editöre Git