Veri Yapısı Ağaçlar

Ağaçlar

Ağaç, düğümlerle adlandırılan, birinin kök olarak ayrıcalıklandırıldığı, ailemsi ilişkinin var olduğu, hiyerarşik yapıyla gelen elemanlar kümesidir. Bir düğüm, listedeki bir eleman gibi istediğimiz tipte olabilir. Genelde düğümü bir harf veya sayıyı çemberle çevreleyerek resmedebilirsiniz. Belirtilen harf veya sayı düğümün değeridir (anahtarıdır).

Ağaç Yapısı Örneği

Özellikler:

  • Tek bir düğümün kendisi de ağaçtır.
  • B ve C düğümlerine kardeş düğümler denir.
  • İki düğümü birleştiren kenara çizgi kenar denir.
  • Ağacın kökü A’dır.
  • Çocuğu olmayan düğümlere yaprak denir. (G, Ğ, H, I)
  • Aynı derinliğe sahip düğümler kümesi seviye olarak adlandırılır.

İkili Ağaç

Her bir düğümün en fazla iki tane çocuğa sahip olduğu ağaçlar ikili ağaç olarak adlandırılır.

İkili Ağaç Resmi

İkili Arama Ağacı

İkili ağaçların en önemli uygulamasından biri ikili arama ağacıdır. İkili ağacı, ikili arama ağacı yapan farklılık, ağaçtaki her bir düğüm (X), sol ağacındaki tüm anahtarların değerlerinden büyüktür. Aynı zamanda sağ ağacındaki değerler X’den büyüktür.

İkili Arama Ağacı

İkili Ağaç İşlemleri

Bul: Bu işlem ağaçta verilen X değerine sahip bir anahtar var mı onu arar. Varsa konum bilgisini verir veya sadece EVET (var anlamında) bilgi döndürür.

En Küçük ve En Büyük: Bu işlem ağaçtaki en küçük ve en büyük anahtar değerlerini bulur. Bunlara ait yolu gönderir (tercihen).

Ekle: Ekleme işlemi basit bir işlem sayılır. X elemanını T ağacına eklemek için Bul işlemi gibi sırayla aşağıya doğru ineriz. Eğer X bulunursa işlem gerçekleşmez. Aksi halde ziyaret edilen en son pozisyona X’i ekleriz.

Sil: En zor işlem Silme işlemidir. Önce silinecek düğüm bulunur. Bu aşamadan sonra birkaç olasılık vardır.

  • Silinecek düğüm bir yaprak ise ailesiyle bağı kopartılır, elemanın tuttuğu alan boşaltılır.
  • Eğer düğüm tek çocuğa sahipse genel strateji olarak bu düğümü, ailesi kendisini by-pass edecek şekilde, ailesi ile çocuğu arasında bir bağ oluşturduktan sonra düğümü sileriz.
  • Eğer düğüm, iki çocuğa sahipse düğümün sağ alt ağacındaki en küçük anahtara sahip düğüm ile yer değiştirilir, ardından o düğüm silinir.
İlginizi Çekebilir:  Veri Yapılarına Giriş

Full İkili Ağaç

Her bir düğüm ya sıfır ya da 2 çocuğa sahipse bu ağaç “İkili Full Ağaç” olarak adlandırılır.

Full İkili Ağaç Resmi

Tam Ağaç

En alt seviyenin soldan sağa doğru dolduğu, bir üst seviyedeki düğümlerin (en sağ taraftakiler hariç) ve diğer üst seviyedeki düğümlerin iki çocuğa sahip olduğu ağaç türüdür.

Tam Ağaç Resmi

Tam Ağaç ve Full İkili Ağaç Arasındaki Farkı Anlamak İçin Aşağıdaki Görseli İnceleyin:

Full ve Tam Ağaç Farkı

İkili Heap

Heap bir tam ağaçtır ve herhangi bir düğümdeki anahtarın değeri sol ve sağ alt ağaçlardaki düğümlerin anahtarlarındaki değerlerden küçüktür. Bu Minimum Heap olarak alınır.

Maksimum Heap’de ise her bir düğümdeki anahtarların değeri sol ve sağ alt ağaçlarındaki düğümlerin anahtarlarındaki değerlerden büyüktür.

Yığında son giren ilk çıkar. Sıra da ilk giren ilk çıkar.

Minimum ve Maximum Heap Ağacı Resmi

AVL Ağacı

Yükseklik ağaçlarda hızlı hareket etmek için önemli bir kriterdir. Eğer aynı veri grubunu iki farklı şekilde yapılandırırsak iyi olanı tercih ederiz.

AVL Ağacı Resmi

Yukarıdaki gibi iki ağaç verilirse sağdaki AVL Ağacı’nı tercih ederiz.

AVL Ağacı Olduğunu Belirleme İşlemleri

T bir ağaç olsun. T ağacındaki her bir düğüm için;

  • | Yükseklik (sol alt) – Yükseklik (sağ alt) | <= 1
  • Diğer bir anlatımla T ağacının her bir düğümünün sol ağacı ile sağ ağacı arasındaki en büyük fark maksimum bir olmak zorunda.

Bu denge özelliğine “AVL Özelliği” denir.

Yani AVL Ağacı, AVL Özelliği’ne sahip ikili arama ağacıdır.

Yukarıdaki AVL Ağacı’nı belirtilen kriterlere göre incelersek:

  • Sol düğüm 4’dür. 4’ün solunda bir düğüm, sağında bir düğüm mevcut (yükseklik) 1 – 1 işleminden 0 bulunur devam edilir.
  • Sağ düğümün en altına geçilir. 23’ün sol düğümü yoktur, sağ düğümünün yüksekliği 1’dir. 0 – 1 işleminden 1 bulunur devam edilir. Mutlak değer işaretini göz önüne alırsak 1 sonucu elde edilir.
  • 18 düğümüne geçtiğimizde sol düğümün yüksekliği 1’dir, sağ düğümü 2 yüksekliğe sahip 1 – 2’den sonuç 1 olarak bulunur.
  • Köke gelinir (11) sol ağacın yüksekliği 0, sağ ağacın yüksekliği 1 olduğundan sonuç 1 çıkar bu ağaç AVL Ağacı olarak anılır.
İlginizi Çekebilir:  Veri Yapılarına Giriş

İnfografik

Veri Yapıları - Ağaçlar İnfografik Resim

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir