İkili Ağaçlar İkili Arama Ağaçları Ağaçlar Bağlantılı listedeki erişim zamanı lineerdir



Yüklə 479 b.
tarix04.07.2017
ölçüsü479 b.


İkili Ağaçlar İkili Arama Ağaçları


Ağaçlar

  • Bağlantılı listedeki erişim zamanı lineerdir.

    • Çoğu işlemlerin (operasyon) (arama, ekleme, silme) çalışma zamanını daha aza indiren
    • (O(log N) gibi) başka bir veri yapısı var mıdır?


Ağaçlar

  • Ağaç düğümlerin koleksiyonudur.

    • Koleksiyon boş olabilir
    • Eğer boş değilse, ağaç birbirlerinden faklı r kök düğümünü ve sıfır veya birden fazla boş olmayan T1, T2, ...., Tk altağaçlarını içerir, herbiri r’ den gelen bir yönlendirilmiş kenar ile köke bağlıdır.


Bazı tanımlar

  • Çocuk ve ebeveyn

    • Kök hariç her düğümün bir ebeveyni vardır.
    • Bir düğümün çocuk sayısı değişebilir.
  • Yapraklar

    • Çocuğu olmayan düğümlere denir.
  • Kardeş

    • Ebeveyni aynı olan düğümlerdir.


Bazı Tanımlar

  • Patika – yol - Path

  • Uzunluk - Length

    • Bir yoldaki kenar sayısı
  • Bir düğümün derinliği

    • Kökten düğüme olan tekil yolun uzunluğu
    • Bir ağacın derinliği en derinde bulunan yaprağın derinliğine eşittir.
  • Bir düğümün yüksekliği

    • Düğümden bir yaprağa olan en uzun yola denir.
    • Bütün yapraklar yükseklik 0 ‘ da bulunur
    • Bir ağacın yüksekliği kökün yüksekliğine eğittir.
  • Ata (veya dede) ve torun



Örnek UNIX dizini



İkili Ağaçlar

  • Bu ağaçta hiçbir düğümün ikiden fazla çocuğu olamaz

  • Ortalama bir ikili ağacın derinliği N ‘den küçüktür, en kötü durumda bile derinlik N-1 olabilir.



Örnek:ifade ağaçları

  • Yapraklar terim (sabit veya değişken)

  • Diğer düğümler işlem

  • Bazı işlemler binary değilse ikili ağaçta gösterilemeyebilir.



Ağaç Gezme (Tree Traversal)

  • Bir ağaçtaki verileri belli bir düzende yazmak için kullanılır.

  • Önce-kök Gezme (Pre-order traversal)

    • Kökteki veriyi yaz
    • Sol altağaçtaki verileri iteratif olarak yaz
    • Sağ altağaçtaki verileri iteratif olarak yaz


Öncekök, sonrakök, ve içkök Preorder, Postorder and Inorder

  • Öncekök gezme

    • düğüm, sol, sağ
    • önek ifadesi
      • ++a*bc*+*defg


Öncekök, sonrakök, ve içkök

  • Sonrakök gezme

    • Sol, sağ, düğüm
    • Sonek ifadesi
      • abc*+de*f+g*+
  • İçkök yazma

    • Sol, düğüm, sağ
    • İçek ifadesi
      • a+b*c+d*e+f*g


Öncekök

  • Öncekök



sonrakök

  • sonrakök



Öncekök, sonrakök, ve içkök



İkili Ağaçlar

  • İkili ağaç SVY üzerindeki muhtemel işlemler

    • parent - ebeveyn
    • left_child, right_child - sol_çocuk, sağ_çocuk
    • Sibling - kardeş
    • root, etc - kök
  • Gerçekleştirmesi

    • İkili ağaçta en fazla iki çocuk olduğu için, bunlar için pointer kullanabiliriz.


Karşılaştırma: Genel bir ağaç gerçekleştirilmesi



İkili Arama Ağacı

  • Anahtarları düğümler içinde depolar; böylece arama, ekleme ve silme etkili bir şekilde yapılabilir.

  • İkili arama ağaç özelliği

    • Herbir X düğümü için, solundaki altağaçtaki (subtree) anahtarlar X düğümünde bulunan değerden daha küçüktür, ve sağındaki ağaçtaki anahtarlar X düğümünde bulunan değerden daha büyüktür.


İkili Arama Ağaçları



İkili Arama Ağaçları

  • Bir düğümün ortalama derinliği O(log N); maksimum derinliği ise O(N)



Gerçekleştirme



İAA Arama

  • Eğer 15’i arıyorsak arama işlemi biter.

  • Eğer aranan anahtar < 15 ise, sol altağaçta aramaya devam edilir.

  • Eğer aranan anahtar > 15 ise, sağ altağaçta aramaya devam edilir.





Arama (Bul - Find)

  • Find X: X anahtarını bulunduran düğümün pointer ini dönder veya eğer böyle bir düğüm yok ise NULL dönder.

  • Zaman Karmaşıklığı

    • O(ağaç yüksekliği)


İAA’ında içkök gezme

  • Bütün anahtarları sıralanmış bir şekilde getirir.



findMin/ findMax

  • Ağaçtaki en küçük elemanı içeren düğümü dönderir.

  • Kökten başla ve sol çocuk var olduğu sürece sola git. Durma noktasındaki eleman en küçük elemandır.

  • findMax için de mantık benzer şekildedir.

  • Zaman karmaşıklığı = O(ağaç yüksekliği)



Ekle - insert

  • Ağaçta ilgili yere find komutunda olduğu gibi git

  • Eğer X varsa, bir şey yapma (veya bir şey güncelle)

  • Diğer durumda, X i gezilen yoldaki en son noktaya ekle.

  • Zaman Karmaşıklığı = O(ağaç yüksekliği)



Sil - delete

  • Bir düğüm silindiği zaman, silinen düğümün çocuklarına nasıl yerleştireceğimizi düşünmemiş gerekir.

    • Bu işlem arama ağacı (search tree) özelliğinin korunması için gereklidir.


sil

  • Üç durum vardır:

  • (1) düğüm yaprak ise

    • sil
  • (2) düğümün tek çocuğu varsa

    • Ebeveynden bir çocuğa bir pointer ata


sil

  • (3) düğümün 2 çocuğu varsa

    • Silinen düğüm anahtarını sağ altağaçtaki minimum elemanla yer değiştir (replace the key of that node with the minimum element at the right subtree )
    • Minimum elemanı sil
      • Daha sonra ya hiç çocuk kalmamıştır yada bir çocuk vardır. Bu durumda durum 1 ve 2 uygulanır..
  • Zaman karmaşıklığı = O(ağaç yüksekliği)







Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2019
rəhbərliyinə müraciət

    Ana səhifə