Forum: Diğer Konular RSS
Ağaç Yapısı Üzerine
iyileştirme (optimization)
Avatar
Salih Dinçer #1
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: Ağaç Yapısı Üzerine
Merhaba,

İstanbul'dayım (bir hafta tatil yapmıştım) ve gelir gelmez uzunca uyudum. Hani uykuda bir sorunu düşününce cevabı uyku ile beraber geliyor ya iyi oldu. Bir taşla iki kuş hesabı...:)

Şuradaki başlıkta Hüseyin kardeşimiz, diğerleri gibi çok ilginç konuda bir soru sormuştu ve bu soru bizi veri yapılarında çok temel öğelerine (bağlı liste, yığın, ağaç, öbek vb.) götürmüştü. Akabinde, bilgi eksikliğimi tamamlamaya (şu Youtube vidyosundaki ders gibi) gayret ettim ama gel gör ki bir sarmaşık ağacı gibi karışık şeylerle karşılaştım...:D

Ancak, kağıt kalemi eline alınca okuyacağınız sayfalarca yazıdan daha verimli olduğunu söyleyebilirim...

Nerede kalmıştık, şöyle bir soru sormuştum:

Salih Dinçer on 2012-09-24, 18:28:
Peki hocam; kodumuzda 2^5 elemanlı bir verimiz olsun, örneğin bir dizi. Bu durumda dizi 32 elemanda oluşur ve sağ/sol diye ikili ağaç (binary tree) kurarsak şöyle olmaz mı?
    auto veri = [ 90, 10, 20, 30, 40, 50, 60, 70, 80,
                  5, 15, 25, 35, 45, 55, 65, 75, 85,
                  100, 200, 300, 400, 500, 600, 700,
                  150, 250, 350, 450, 550, 650, 750
                ];//*/
    /*            90
     *        ----------
     *       /          \
     *      10          100
     *     / \            \
     *    5  20           200
     *       / \          / \
     *      15 30       150 300
     *         / \          / \
     *        25 40       250 400
     *           / \          / \
     *          35 50       350 500
     *             / \          / \
     *            45 60       450 600
     *               / \          / \
     *              55 70       550 700
     *                 / \          / \
     *                65 80       650 750
     *                     \
     *                     85
     */
Bu durumda 85'i bulması için 5 değil 10 adım gerekli. Yoksa hile mi yaptım! Ağaç yapısı daha mı farklı olacaktı...:)

Meğer bu sayılardan en verimli yapı şu şekilde oluşturuluyormuş:
    auto veri = [ 85, /* en tepedeki kök (root) */
                  45, 25, 65, /* soldaki ilk iki dal */
                  15, 10, 20, /* sonraki birinci dalın, soldaki ikilisi */
                  35, 30, 40, /*                        sağdaki ikilisi */
                  55, 50, 60, /* sonraki ikinci dalın, soldaki ikilisi */
                  75, 70, 80, /*                       sağdaki ikilisi */
                 145,125,165, /* sağdaki büyükler... */
                 115,110,120, /* yukarıdaki gibiler */
                 135,130,140,
                 155,150,160,
                 175,170,180 ];
 
    /*                  ______________85______________
     *                /                                \
     *           ____45____                      _____145_____
     *         /            \                  /               \
     *       25             65                125             165
     *     /   \           /   \            /     \         /     \
     *   15     35       55     75        115     135     155     175
     *  / \     / \     / \     / \       / \     / \     / \     / \
     * 10 20   30 40   50 60   70 80    110 120 130 140 150 160 170 180
     */
Bu ağaç yapısın (veriyi) şuradaki kod ile deneyebilir ve hafızada farklı şekilde temsil edilen veri ağacı üzerinde arama yapabilirsiniz. Böylece yarı yarıya daha verimli arama sonucu elde edebiliyorsunuz. Basit bir şekilde rasgele aramalar yapıldığında, ortalaması 3,6 ila 5,3 karşılaştırma arasında değişiyor. Oysa ilk naklettiğim 7 ila 10 arasında değerler gördüm. Tabi bunlar toplam karşılaştırmanın bulunan sayı adetine bölümü olduğunun altını çizmeliyim.

Yine de binlerce test yapmadığım için aralıkta küçük sapmalar olası. Buna rağmen %50 optimize edildiği söylenebilir. Sıra geldi herhangi bir veriyi bu yapıya gelmesini zorlamak. Sanırım basit bir şekilde dallar arasında yer değiştirme yeterli olacak.

Başarılar...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #2
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yeni öğrendiğim bir şey, meğer toplam düğüm sayısı seviyeye (n) göre şöyle hesaplanıyormuş: (2^n + 1) - 1
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-19, 00:42:56 (UTC -08:00)