Can Burak Cilingir <[EMAIL PROTECTED]> writes:
> (N)ear (e)valuated (p)riority (t)ree veri tipi icerisinde sakladiginiz
> veriyi sirali olsun, olmasin BST (binary search tree) benzeri bir
> sekilde calisarak aradiginiz veriye en fazla agacin derinligi kadar
> islemde erismenizi saglar.  Bu da en kotu durumda bahsettiginiz gibi
> O(n) yerine O(log(n)) performans saglayacak, n'in ozellikle buyuk
> degerleri icin kiyaslanamayacak kadar iyi bir basarim getirecektir.

Benim burada değinmek istediğim nokta, bahsi geçen arama işlemini sadece
tek bir kez yapacaksanız doğrudan sequential scan ile listeyi taramak en
doğrusu olacaktır -- bu O(n) karmaşıklığında. Çünkü bunu herhangi bir
ağaca yerleştirmek istediğinizde veri yapısının yeni hale aktarımı için
en azından O(nlogn) adım gerekmektedir, kaldı ki bu çok iyimser bir
oran. Eğer bu arama işlemleri birden fazla kez yapılacaksa, tabii ki
sorgu tipine özel bir arama ağacı kullanmanız kaçınılmaz olacaktır.

Şu da var ki, her veri tipi için istenilen ağaç yapısı
oluşturulamayabilir. Çünkü herhangi bir veriyi ağaçta saklayabilmeniz
için o ağaç tarafından şart koşulan karşılaştırma operatörlerinin
saklanacak veri üzerinde tanımlanması gerekmektedir.


İyi çalışmalar.

_______________________________________________
cs-lisp mailing list
cs-lisp@cs.bilgi.edu.tr
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp

Cevap