Binary Tree ve BST Nedir? Trees & BST Lab ile Görselleştirin

Tree ve Binary Search Tree konuları, doğrusal veri yapılarından hiyerarşik yapılara geçiş yaptığımız noktadır. Array veya linked list üzerinde çoğu zaman tek bir yönde ilerleriz. Bir tree düğümünde ise sol ve sağ alt ağaçlar, parent-child ilişkileri ve recursive dönüş yolları aynı anda düşünülmelidir.

Öğrenciler genellikle tree terimlerini tek tek bilir; fakat traversal sırasını, recursive çağrıların nasıl geri döndüğünü veya BST silme işleminde hangi düğümün neden replacement seçildiğini takip ederken zorlanır. Çünkü ekrandaki son ağaç, o sonuca ulaşırken gerçekleşen pointer ve çağrı değişikliklerini göstermez.

Websoftik Academy’de geliştirdiğimiz Trees & BST Lab, tree ilişkilerini, traversal stratejilerini, recursive hesaplamaları, expression tree’leri ve BST işlemlerini 27 kaynak destekli operasyonla adım adım incelemek için tasarlandı.

1. Tree Veri Yapısı Nedir?

Tree, düğümler arasındaki hiyerarşik ilişkileri temsil eden bir veri yapısıdır. En üstteki düğüm root olarak adlandırılır. Bir düğümün doğrudan altında bulunan düğümler child, doğrudan üstündeki düğüm parent ve child’larla birlikte aşağı doğru oluşan yapı subtree olarak tanımlanır.

• Leaf: child düğümü bulunmayan node
• Depth: root’tan ilgili düğüme kadar olan edge sayısı
• Height: düğümden aşağıdaki en uzak leaf’e giden edge sayısı
• Subtree: bir düğüm ve onun bütün descendant’ları
• Forest: birbirinden ayrı tree’lerden oluşan koleksiyon

Bu terimler yalnızca tanım soruları için değildir. Recursive bir fonksiyonun hangi alt probleme gönderildiğini ve hesaplanan değerin nereden döndüğünü açıklamak için ortak bir dil oluşturur.

2. Binary Tree ile Binary Search Tree Arasındaki Fark Nedir?

Binary tree’de her düğümün en fazla iki child’ı bulunur. Bu tanım düğümlerin değerleri arasında otomatik olarak bir sıralama ilişkisi kurmaz. Sol child’ın değeri parent’tan büyük de olabilir, küçük de olabilir.

Binary Search Tree yani BST ise ek bir ordering invariant’ına sahiptir. Yaygın tanımda bir düğümün sol subtree’sindeki değerler düğümden küçük, sağ subtree’sindeki değerler büyüktür. Duplicate değer politikası ayrıca belirlenebilir; önemli olan seçilen kuralın bütün ağaçta tutarlı kalmasıdır.

Dolayısıyla her BST bir binary tree’dir; fakat her binary tree BST değildir. Arama, minimum, maksimum ve sıralı traversal gibi avantajlar BST invariant’ı korunduğu sürece geçerlidir.

3. Trees & BST Lab Nasıl Çalışıyor?

Trees & BST Lab, tree üzerindeki her işlemi deterministic state’lere böler. Aktif düğüm, izlenen branch, recursive call stack, dönen partial result ve pointer değişiklikleri kaynak kodla birlikte gösterilir.

Uygulamayı Trees & BST Lab çalışma alanından açabilirsiniz. Öğrenme rotası tree vocabulary ile başlar; binary tree özellikleri, traversal, recursive metrics, expression trees, BST işlemleri ve shape-complexity ilişkisiyle devam eder.

Lab’de düğüm kimlikleri değerlerden ayrı tutulur. Bir deletion işleminde ekranda aynı değer görünse bile hangi node’un taşındığını, hangisinin kaldırıldığını ve hangi bağlantının değiştiğini takip edebilirsiniz.

4. Full, Complete, Perfect ve Balanced Tree Ne Demektir?

Tree şekillerini tanımlayan terimler birbirine benzer görünse de farklı özellikleri ifade eder:

• Full binary tree: her node ya sıfır ya da iki child taşır.
• Complete binary tree: son seviye dışında seviyeler doludur; son seviye soldan sağa yerleşir.
• Perfect binary tree: bütün internal node’ların iki child’ı vardır ve bütün leaf’ler aynı seviyededir.
• Balanced tree: alt ağaç yükseklikleri belirlenen denge sınırları içinde kalır.
• Skewed tree: düğümler ağırlıklı olarak tek bir yönde uzanır.

Complete ve balanced aynı şey değildir. Complete tanımı yerleşim biçimine, balanced tanımı ise yükseklik farklarına ve sonuçtaki operasyon maliyetine odaklanır. Lab, aynı düğüm sayısıyla farklı shape’ler üretip özellikleri karşılaştırır.

5. Preorder, Inorder, Postorder ve Level-Order Traversal Nasıl Ayrılır?

Traversal, tree’deki düğümleri belirli bir sırayla ziyaret etme yöntemidir. Depth-first traversal’larda temel fark root’un ne zaman işlendiğidir:

• Preorder: root → left → right
• Inorder: left → root → right
• Postorder: left → right → root
• Level-order: düğümleri seviyeler halinde queue kullanarak ziyaret eder.

Bir BST üzerinde inorder traversal değerleri sıralı sırada üretir. Preorder bir yapıyı root’tan başlayarak kopyalamak için, postorder ise child kaynaklarını parent’tan önce serbest bırakmak için doğal olabilir. Traversal sırası yalnızca ezberlenecek üç kelime değil, problemin gerektirdiği işlem zamanıdır.

6. Recursive ve Iterative Traversal Arasındaki Fark Nedir?

Recursive traversal’da programın call stack’i geri dönülecek düğümleri saklar. Iterative sürümde ise aynı sorumluluğu çoğu zaman açık bir stack veya queue veri yapısı üstlenir. İki yaklaşım aynı ziyaret sırasını üretebilir; fakat kontrol state’inin nerede tutulduğu farklıdır.

void inorder(node_t *root) {
  if (root == NULL) return;
  inorder(root->left);
  visit(root);
  inorder(root->right);
}

Trees & BST Lab recursive çağrıların oluşumunu ve dönüş sırasını gösterirken, iterative sürümde explicit stack’in içeriğini adım adım günceller. Böylece iki kodun aynı traversal’ı nasıl ürettiği görülebilir.

7. Recursive Tree Metrics Sonucu Nasıl Birleştirir?

Tree yüksekliği, düğüm sayısı, leaf sayısı veya belirli bir koşulu sağlayan düğümlerin toplamı gibi hesaplar recursive alt problemlere ayrılabilir. Her node sol ve sağ subtree için sonucu ister, ardından iki partial result’ı kendi katkısıyla birleştirir.

int size(node_t *root) {
  if (root == NULL) return 0;
  return 1 + size(root->left) + size(root->right);
}

Öğrenciler çoğu zaman aşağı doğru giden çağrıları takip eder fakat sonuçların dönüş yolunda nasıl toplandığını kaçırır. Lab, her stack frame’de beklenen ve tamamlanan sonucu ayrı gösterir.

8. Expression Tree Nasıl Çalışır?

Expression tree’de internal node’lar operatörleri, leaf node’lar operand’ları temsil eder. Örneğin (3 + 5) * 2 ifadesinde multiplication root, sol subtree addition ve sağ child 2 olabilir.

Preorder traversal prefix, inorder uygun parantezlerle infix ve postorder postfix gösterim üretir. Evaluation sırasında child değerleri önce hesaplanır, ardından parent operatörü uygulanır. Bu nedenle expression tree, traversal sıralarının gerçek bir probleme nasıl dönüştüğünü gösteren güçlü bir örnektir.

9. BST Search Neden Her Adımda Bir Subtree’yi Elenir?

BST search işleminde hedef mevcut düğümle karşılaştırılır. Hedef küçükse sağ subtree’nin tamamı, büyükse sol subtree’nin tamamı elenir. Bu karar BST ordering invariant’ına dayanır.

Dengeli bir BST’de yükseklik yaklaşık log n olduğu için arama da Θ(log n) seviyesinde olabilir. Ancak tree tek tarafa uzamışsa yükseklik n olur ve arama linked list benzeri Θ(n) davranışına yaklaşır. Yani maliyeti yalnızca düğüm sayısı değil, ağacın shape’i belirler.

10. BST Insert İşleminde Invariant Nasıl Korunur?

Insert işlemi search ile aynı branch kararlarını izler ve uygun NULL bağlantıya ulaştığında yeni düğümü yerleştirir. Yeni node yalnızca bulunduğu noktadaki parent ile değil, bütün ancestor’larla uyumlu olmalıdır; doğru search path bunu otomatik olarak sağlar.

Duplicate değerler için “reddet”, “sayacı artır”, “eşitleri belirli tarafa yerleştir” gibi bir politika seçilebilir. Yanlış olan, davranışı tanımsız bırakmak veya farklı insert’lerde farklı kural uygulamaktır. Lab, her karşılaştırmadan sonra elenen range’i ve yeni node’un geçerli değer aralığını gösterir.

11. BST Delete İşleminin Üç Durumu Nedir?

BST deletion, hedef düğümün child sayısına göre üç temel duruma ayrılır:

1. Leaf node: parent bağlantısı doğrudan NULL yapılır.
2. Tek child: parent, silinen düğümün child’ına bağlanır.
3. İki child: inorder predecessor veya successor replacement olarak seçilir.

İki child durumunda replacement değerini bulmak işlemin yalnızca ilk kısmıdır. Seçilen predecessor veya successor kendi eski konumundan da güvenli biçimde kaldırılmalı ve bütün pointer’lar yeniden bağlanmalıdır. Trees & BST Lab bu süreci find, choose, copy/move, rewire, remove ve validate aşamalarına böler.

12. Düğüm Değeri ile Düğüm Kimliği Neden Ayrıdır?

Bir node’un değeri değişebilir veya replacement sırasında başka bir değer onun konumunda görünebilir. Fakat node’un bellekteki kimliği, ona ulaşan pointer’lar ve sahip olduğu child bağlantıları ayrı bir konudur.

Yalnızca değerleri ekranda izlemek, deletion sırasında gerçekte hangi node’un kaldırıldığını gizleyebilir. Lab düğümlere kararlı kimlikler vererek value change ile structural change arasındaki farkı korur. Bu yaklaşım linked list pointer rewiring çalışmalarının tree tarafındaki devamıdır. Temeli tekrar etmek için Linked List Lab rehberimize dönebilirsiniz.

13. BST Shape ile Complexity Arasındaki İlişki Nedir?

Aynı değerler farklı sırayla eklenirse tamamen farklı tree shape’leri oluşabilir. Ortadaki değerlere yakın bir başlangıç dengeli bir yapı üretirken sıralı değerleri art arda eklemek sağa doğru skewed bir tree oluşturabilir.

Search, insert ve delete işlemlerinin maliyeti çoğu zaman tree yüksekliğine bağlıdır: Θ(h). Dengeli durumda h ≈ log n, en kötü durumda h = n - 1 olabilir. Complexity’nin matematiksel tarafını ayrıca çalışmak için Complexity Lab rehberimize geçebilirsiniz.

Parent forest yapısının tree yüksekliğini algoritma maliyetine nasıl dönüştürdüğünü Quick Union ve Weighted Quick Union üzerinde görmek için Online Connectivity Lab rehberimizi kullanabilirsiniz.

14. Trees & BST Lab Nasıl Çalışılmalı?

1. Önce root, leaf, depth, height ve subtree terimlerini bir örnek üzerinde işaretleyin.
2. Aynı tree için preorder, inorder, postorder ve level-order sonuçlarını tahmin edin.
3. Recursive trace’te çağrı ve dönüş yollarını ayrı ayrı takip edin.
4. BST search ve insert sırasında her branch’in elediği değer aralığını açıklayın.
5. Delete işleminin üç durumunu küçük tree’lerde ayrı ayrı çalışın.
6. Her mutation sonrasında BST invariant’ını doğrulayın.
7. Son olarak mixed operation stream ve challenge exam modunu çözün.

Tree öğrenmenin hedefi traversal isimlerini veya deletion kodunu ezberlemek değildir. Asıl hedef, her adımda hangi subtree’nin işlendiğini, hangi bilginin call stack’te beklediğini ve yapılan pointer değişikliğinin invariant’ı nasıl koruduğunu açıklayabilmektir.

Tüm öğrenme araçlarını Websoftik Academy Lab sayfasında inceleyebilir veya Trees & BST Lab’i açarak traversal ve BST operasyonlarını çalışmaya başlayabilirsiniz. Daha geniş bir konu sırası için algoritma ve veri yapıları çalışma yol haritamızı kullanabilirsiniz.