düğümlerin çok sayıda hızlı yerleştirilmesi için en iyi kendini dengeleyen BST

oy
8

Birkaç kendini dengeleyen ilgili ayrıntıları bulmak mümkün oldum BSTbirkaç kaynaklar aracılığıyla s, ama herhangi bir iyi açıklamaları Farklı durumlarda kullanmak en iyisidir hangisinin detaylandırma (ya da gerçekten önemli değil ise) bulamadım.

Ben istiyorum BSTon milyon düğümler aşan depolamak için en uygun olduğunu. Düğümlerin yerleştirilmesi sırası temelde rastgele ve ben düğümleri silmenize gerek kalmayacak, bu yüzden ekleme zamanı optimize edilmesi gerekir tek şeydir.

Bir önceki yapılandırması zaten karşılaştı olup olmadığını hızla kontrol edebilir, böylece bir bulmaca oyunu daha önce ziyaret oyun durumlarını saklamak için kullanmak niyetinde.

Oluştur 05/08/2008 saat 16:40
kaynak kullanıcı
Diğer dillerde...                            


4 cevaplar

oy
3

Neden kullanmak BSThiç? Daha iyi değilse anlattıklarına bakılırsa bir sözlük, tıpkı iyi çalışacaktır.

Bir kullanarak tek nedeni BSTanahtar sırayla kabın içindekileri dışarı listelemek istiyorsa olurdu. Eğer bu durumda karma tablo için gitmek, bunu istedikleri gibi kesinlikle gelmiyor. O(1)Ekleme ve arama, silme hakkında hiçbir endişe, daha iyi ne olabilir?

Cevap 29/08/2008 saat 01:10
kaynak kullanıcı

oy
3

Kırmızı-siyah ekleme-ağır uygulamalar için AVL daha iyidir. Nispeten homojen bir görünüm-up öngörmek, o Kırmızı-siyah gitmek yoludur. Daha son görüntülenen öğeleri tekrar görüntülenebilir olasılığı daha yüksektir nispeten dengesiz bir görünüm-up öngörüyor ise kullanmak istediğiniz yayvan ağaçlar .

Cevap 05/08/2008 saat 16:59
kaynak kullanıcı

oy
0

İki kendini dengeleyen BSTben en aşina olduğum s-kırmızı, siyah ve AVLböylece başka çözümler daha iyi olup olmadığını Kesin diyemem, ama hatırladığım kadarıyla, kırmızı-siyah hızlı ekleme ve kıyasla daha yavaş alma vardır AVL.

Ekleme alımı daha yüksek bir öncelik Yani, eğer kırmızı-siyah daha iyi bir çözüm olabilir.

Cevap 05/08/2008 saat 16:50
kaynak kullanıcı

oy
-2

[Karma tablo bilgisi] o (1) yerleştirilmesini ve arama

Bence bu yanlış.

Eğer sonlu olması keyspace sınırı, her şeyden önce, bir dizi elemanları depolamak ve bir O (1) lineer tarama yapabilir. Yoksa dizi shufflesort ve sonra O (1) beklenen sürede doğrusal tarama yapabilir. malzeme sonlu olduğunda, malzeme kolayca O olduğu (1).

Öyleyse şimdi de karma tablo rasgele bit dizisini depolar diyelim; o kadar uzun sonlu olan her biri tuşların sonsuz seti, orada olduğu gibi, pek de önem kazanıyor. Sonra, herhangi bir sorgu ve yerleştirme girişinin tüm bitlerini okumak başka ben y0 ve y1 sen bakma tek bit konumundaki farklılık y1, boş bir karma ve sorguda y0 eklemek gerekir.

Ama anahtar uzunlukları bir parametre değildir diyelim. Ve yerleştirme O almak ararsanız (1), özellikle karma hangi yalnızca olasılığı var olan hash fonksiyonu (dan çıktı sonlu miktarda bakmak anlamına gelir, O (1) zaman alır olacak verilen sadece sonlu çıkışı, ).

Bu sonlu sayıda kovalarla, hepsi aynı karma değere sahip dizeleri sonsuz bir küme olması gerektiği anlamına gelir. Çok şey eklemek varsayalım, yani ω (1), olanların ve sorgulama başlar. Bu karma tablo benim sorguları yanıtlamak için geri diğer bazı Ç (1) yerleştirme / arama mekanizması üzerinde düşmeye sahip olduğu anlamına gelir. Hangisi ve neden sadece doğrudan kullanan?

Cevap 01/02/2009 saat 13:49
kaynak kullanıcı

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more