Veri Yapıları - Ağaçlar | Biledu
Veri Yapıları – Ağaçlar
25 Ağustos 2018 25 Ağustos 2018 BilEduVeri Yapıları ve Algoritmalarağaçlar, veri yapı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).
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.
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 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 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.
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ç ve Full İkili Ağaç Arasındaki Farkı Anlamak İçin Aşağıdaki Görseli İnceleyin:
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.
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.
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.
Previous Previous post: Yorum Backlink
Next Next post: MozRank Nedir? Nasıl Yükseltilir?
Bulmak İçin Aramalısın
Son Yazıları Okudun Mu?
Fierce Nedir? – Kullanımı
Linux Terminalden Hava Durumuna Bakma
Find My Hash Kullanımı – MD5 Şifre Kırma
En Popüler Linux Dağıtımları
Flickr’dan Backlink Nasıl Alınır?
Kategorilere Göz Atmayı Unutma
Bilgisayar Tasarımı ve Organizasyonu