🎓 Ağaç formasyonu (Orman) Test 1 - Ders Notu
Bu ders notu, "Ağaç formasyonu (Orman) Test 1" testinde karşılaşabileceğin temel ağaç veri yapısı kavramlarını, ağaç türlerini ve ağaçlar üzerindeki önemli işlemleri sade bir dille özetlemektedir. Bilgisayar bilimlerindeki bu hiyerarşik yapıları anlamak, daha karmaşık algoritmaları çözmenin anahtarıdır.
📌 Ağaç Veri Yapısı Nedir?
Ağaç, bilgisayar bilimlerinde verileri hiyerarşik bir düzende organize eden, doğrusal olmayan bir veri yapısıdır. Tıpkı gerçek hayattaki bir aile soyağacı gibi, veriler de birbiriyle ilişkili bir düzen içinde saklanır.
- Kök (Root): Ağacın en üstündeki, hiçbir ebeveyni olmayan düğümdür. Tüm ağaç bu kökten başlar.
- Düğüm (Node): Ağaçtaki her bir veri elemanına düğüm denir.
- Kenar (Edge): İki düğüm arasındaki bağlantıdır. Bu bağlantılar, düğümler arasındaki ilişkiyi gösterir.
- Ebeveyn (Parent): Bir düğümün hemen üstündeki düğümdür.
- Çocuk (Child): Bir düğümün hemen altındaki düğümdür.
- Yaprak (Leaf): Hiç çocuğu olmayan düğümlere yaprak düğüm denir.
- Derinlik (Depth): Bir düğümün kökten olan uzaklığıdır (kenar sayısı). Kökün derinliği $0$'dır.
- Yükseklik (Height): Bir düğümün en uzak yaprak düğüme olan uzaklığıdır (kenar sayısı). Ağacın yüksekliği, kök düğümün yüksekliğidir.
💡 İpucu: Ağaçlar, veritabanları, dosya sistemleri ve web sayfalarının DOM yapısı gibi birçok alanda kullanılır. Hiyerarşik ilişkileri modellemek için idealdirler.
📌 Ağaç Türleri
Ağaçlar farklı kurallara göre çeşitlenir. İşte en sık karşılaşılan türlerden bazıları:
- Genel Ağaç (General Tree): Her düğümün istediği kadar çocuğu olabilir. En esnek ağaç türüdür.
- İkili Ağaç (Binary Tree): Her düğümün en fazla iki çocuğu olabilir: sol çocuk ve sağ çocuk.
- İkili Arama Ağacı (Binary Search Tree - BST): İkili ağacın özel bir halidir. Her düğüm için şu kural geçerlidir:
- Sol alt ağaçtaki tüm düğümlerin değerleri, kök düğümün değerinden küçüktür.
- Sağ alt ağaçtaki tüm düğümlerin değerleri, kök düğümün değerinden büyüktür.
- Sol ve sağ alt ağaçlar da birer ikili arama ağacıdır.
- Dengeli Ağaçlar (Balanced Trees - AVL, Red-Black): İkili Arama Ağaçlarının kötü performans göstermesini engellemek için geliştirilmiş özel ağaçlardır. Bu ağaçlar, ekleme ve silme işlemleri sırasında kendilerini otomatik olarak dengeleyerek arama süresini $O(\log n)$ seviyesinde tutmayı hedefler.
⚠️ Dikkat: İkili Arama Ağacında arama, ekleme ve silme işlemleri en kötü durumda $O(n)$ olabilir (eğer ağaç tek bir yöne doğru büyürse, yani bir liste gibi olursa). Dengeli ağaçlar bu durumu engeller.
📌 Ağaç Geçişleri (Traversal)
Ağaçtaki tüm düğümleri belirli bir sıraya göre ziyaret etme işlemine ağaç geçişi denir. Üç temel geçiş yöntemi vardır:
- Inorder (İçten Sıralı) Geçiş: Sol alt ağaç $\rightarrow$ Kök $\rightarrow$ Sağ alt ağaç.
- İkili Arama Ağaçlarında bu geçiş, düğümleri küçükten büyüğe sıralı olarak ziyaret etmenizi sağlar.
- Preorder (Ön Sıralı) Geçiş: Kök $\rightarrow$ Sol alt ağaç $\rightarrow$ Sağ alt ağaç.
- Bir ağacın kopyasını oluşturmak veya ağacı bir dosyaya kaydetmek için kullanışlıdır.
- Postorder (Son Sıralı) Geçiş: Sol alt ağaç $\rightarrow$ Sağ alt ağaç $\rightarrow$ Kök.
- Bir ağacı silerken veya matematiksel ifadeleri değerlendirirken (örneğin postfix notasyonunda) kullanılır.
💡 İpucu: Geçiş yöntemlerini ezberlemek yerine, "Kök" düğümün ne zaman ziyaret edildiğine odaklanarak mantığını kavramaya çalış. (Ön = Kök önce, İç = Kök ortada, Son = Kök sonda)
📌 Ağaç İşlemleri
Ağaçlar üzerinde temel olarak üç ana işlem gerçekleştirilir:
- Ekleme (Insertion): Ağaca yeni bir düğüm ekleme işlemidir. İkili Arama Ağaçlarında, yeni düğümün değeri, kökten başlayarak doğru konumu bulunana kadar ağaçta aşağı doğru ilerlenerek yerleştirilir.
- Arama (Search): Ağaçta belirli bir değeri bulma işlemidir. İkili Arama Ağaçlarında, aranan değer kökten başlanarak karşılaştırılır ve değerden küçükse sola, büyükse sağa gidilerek arama devam eder.
- Silme (Deletion): Ağaçtan bir düğümü kaldırma işlemidir. Bu işlem, silinecek düğümün çocuk sayısına göre farklı senaryolar içerir ve diğer işlemlere göre daha karmaşıktır.
📌 Orman (Forest) Veri Yapısı
Bilgisayar bilimlerinde "orman", birbirine bağlı olmayan, ayrık ağaçların bir koleksiyonudur. Yani, birden fazla bağımsız ağacın bir araya gelmesiyle oluşan bir yapıdır.
- Her bir ağacın kendi kök düğümü vardır ve ağaçlar arasında doğrudan bir bağlantı yoktur.
- Örnek olarak, bir dosya sistemindeki farklı sürücüler veya mantıksal bölümler bir orman olarak düşünülebilir.
💡 İpucu: Bir orman, tek bir kök düğüme sahip olmayan birden fazla ağaçtan oluşur. Tek bir ağaç ise, tek bir kök düğüme sahiptir.
