Hiyerarşik Verilerin Temeli - BST, Heap ve Daha Fazlası
Şimdiye kadar öğrendiğimiz veri yapılarını düşünelim: diziler, bağlı listeler, stack'ler ve queue'lar. Bunların hepsinde ortak bir şey var: veriler tek bir sıra halinde diziliyor. Bir elemandan sonra başka bir eleman geliyor, o bittikten sonra bir sonraki... Tıpkı bir tren gibi, vagonlar arka arkaya sıralanıyor.
Peki ya verilerimiz doğası gereği tek sıra halinde değilse? Bir şirketin organizasyon yapısını düşünün: CEO'nun altında birden fazla müdür var, her müdürün altında birden fazla çalışan var. Ya da bilgisayarınızdaki dosya sistemi: bir klasörün içinde hem dosyalar hem başka klasörler var, o klasörlerin içinde de daha fazla dosya ve klasör... Bu tür dallanarak ilerleyen, hiyerarşik yapıları nasıl temsil edeceğiz?
İşte ağaç (tree) veri yapısı tam olarak bu sorunu çözmek için tasarlandı. Ağaç, verilerin dallar gibi ayrılarak organize edildiği bir yapıdır. Bir noktadan başlarsınız ve oradan birden fazla yöne dallanabilirsiniz.
Ağaç yapısı programlamada en sık karşılaşılan yapılardan biridir çünkü gerçek dünyadaki birçok ilişkiyi doğal olarak modelliyor:
🏠 Dosya Sistemi: Bilgisayarınızda /home/kullanici/belgeler/rapor.pdf gibi bir yol izlediğinizde aslında bir ağaçta geziniyorsunuz. Kök dizin (/) ağacın tepesi, klasörler dallar, dosyalar yapraklar. Bir klasör birden fazla alt klasör ve dosya içerebilir - bu tam olarak ağaç yapısı.
👨👩👧👦 Soy Ağacı: "Soy ağacı" ifadesi boşuna değil! Büyükanne-büyükbabadan başlayıp çocuklara, torunlara uzanan yapı doğal bir ağaç. Her kişinin (kök hariç) tam olarak iki ebeveyni var ve sıfır veya daha fazla çocuğu olabilir.
🏢 Şirket Hiyerarşisi: CEO en tepede, altında departman müdürleri, onların altında takım liderleri, en altta çalışanlar. Kimin kime rapor verdiği ağaç yapısıyla gösterilir.
🌐 HTML/Web Sayfaları: Bir web sayfasının yapısı aslında bir ağaçtır. <html> kök, onun çocukları <head> ve <body>, <body>'nin çocukları <div>, <p> vs. Tarayıcılar bu ağacı "DOM (Document Object Model)" olarak tutar.
Ağaç veri yapısının en zarif özelliklerinden biri, kendisini kendi cinsinden tanımlayabilmesidir. Buna matematikte ve bilgisayar biliminde "recursive (özyinelemeli) tanım" denir.
Bir ağacı şöyle tanımlayabiliriz:
Temel Durum: Boş küme (∅) bir ağaçtır. (Hiç düğüm yoksa, bu boş bir ağaçtır.)
Recursive Durum: Eğer T₁, T₂, ..., Tₖ birer ağaç ise, bir kök düğümü r alıp bu ağaçları r'nin alt ağaçları olarak bağlarsak, ortaya çıkan yapı da bir ağaçtır.
Bu tanım ilk bakışta kafa karıştırıcı gelebilir, ama aslında çok sezgisel. Şöyle düşünün: Bir ağacın herhangi bir düğümüne bakın ve o düğümü "kök" kabul edin. O düğümün altındaki her şey de kendi başına geçerli bir ağaç oluşturur! Yani büyük bir ağaç, aslında daha küçük ağaçların bir araya gelmesinden oluşuyor.
Neden bu önemli? Recursive tanım, ağaç algoritmalarını yazmayı inanılmaz kolaylaştırır. Bir ağaç üzerinde işlem yapmak istediğinizde, "önce kök üzerinde işlem yap, sonra aynı işlemi her alt ağaca uygula" diyebilirsiniz. Mesela bir ağaçtaki tüm elemanları saymak için: "1 (kök) + sol alt ağaçtaki eleman sayısı + sağ alt ağaçtaki eleman sayısı". Bu recursive yaklaşım, ağaç algoritmalarının temelini oluşturur ve ileride traversal, arama gibi konularda sürekli karşınıza çıkacak.
Her düğüm koleksiyonu bir ağaç değildir. Bir yapının geçerli bir ağaç sayılması için bazı temel kuralları sağlaması gerekir. Bu kurallar, ağaçları diğer veri yapılarından (özellikle genel graflardan) ayırır.
Bir ağaçta tam olarak bir kök düğüm olmalıdır. Kök, parent'ı (ebeveyni) olmayan tek düğümdür. Eğer birden fazla "en üst" düğüm varsa, bu yapı tek bir ağaç değil, bir "orman" (forest) olur - yani birden fazla bağımsız ağaç.
Bu kural kritik önem taşır ve ağaçları genel graflardan ayırır. Bir düğümün iki farklı parent'ı olamaz. Neden? Çünkü eğer bir düğümün iki parent'ı olsaydı, kökten o düğüme giden birden fazla yol olurdu. Bu durum ağaç yapısını bozar ve aslında bir "graf" oluşturur.
Örneğin soy ağacında bir çocuğun iki babası olamaz (biyolojik olarak). Ya da dosya sisteminde bir dosya aynı anda iki farklı klasörün içinde olamaz (shortcut/link hariç). Bu tek-parent kuralı, ağaçlarda her düğüme kökten tam olarak bir yol olmasını garanti eder.
Bu matematiksel özellik, yukarıdaki kuralların doğal bir sonucudur. Bir ağaçta n düğüm varsa, tam olarak n-1 kenar (edge) bulunur. Ne fazla, ne eksik.
Neden n-1? Her düğümün (kök hariç) tam olarak bir parent'ı olduğunu söyledik. Parent ile child arasındaki bağlantıya "kenar" diyoruz. Kök hariç n-1 düğümün her birinin bir parent'a bağlantısı var, yani n-1 kenar.
Bu kuralı doğrulama: Size bir yapı verildiğinde, düğüm ve kenar sayısını sayarak bunun ağaç olup olmadığını hızlıca kontrol edebilirsiniz. 10 düğüm varsa 9 kenar olmalı. 15 düğüm varsa 14 kenar. Eğer kenar sayısı n-1'den azsa yapı bağlı değil (parçalar ayrı), fazlaysa döngü var demektir.
Ağaçlarda asla döngü (cycle) olmaz. Herhangi bir düğümden başlayıp kenarlarda ilerleyerek aynı düğüme geri dönemezsiniz. Eğer dönebiliyorsanız, bu yapı ağaç değil graftır.
Bu kural aslında "n düğüm, n-1 kenar" kuralının başka bir ifadesidir. Bağlı bir yapıda n-1'den fazla kenar varsa mutlaka döngü oluşur.
Bu dört kural birbirine bağlıdır. Eğer yapınız bağlıysa (her düğüme ulaşılabiliyorsa), döngü yoksa, tek kök varsa ve n-1 kenar varsa - geçerli bir ağaçtır.
💡 Düğümlerin üzerine gelin
Ağaç veri yapısını anlamak için bazı temel terimleri bilmeniz gerekiyor. Bu terimler tüm ağaç konularında (BST, Heap, vb.) sürekli karşınıza çıkacak, o yüzden şimdiden iyi öğrenmekte fayda var.
Ağacın en tepesindeki düğüme kök denir. Tıpkı gerçek bir ağacın gövdesinin yerden başladığı nokta gibi (tabii bilgisayar bilimciler ağaçları baş aşağı çizerler!). Kökün ayırt edici özelliği: parent'ı (ebeveyni) yoktur. Herkes birinin çocuğudur ama kök hiç kimsenin çocuğu değildir. Her ağaçta tam olarak bir kök bulunur.
Çocuğu olmayan düğümlere yaprak denir. Bunlar ağacın "uç noktaları"dır - dallanma burada biter. Dosya sisteminde dosyalar yapraktır (içlerinde başka klasör yok), klasörler ise iç düğümdür (içlerinde başka şeyler var). Yapraklar bazen "external node" (dış düğüm) olarak da adlandırılır çünkü ağacın dışına doğru en uçtadırlar.
En az bir çocuğu olan düğümlere iç düğüm denir. Kök de (çocuğu varsa) bir iç düğümdür. İç düğümler ağacın "orta kısmını" oluşturur - hem bir parent'a bağlıdırlar hem de kendileri başka düğümlerin parent'ıdırlar. Dosya sistemindeki klasörler genellikle iç düğümlerdir.
Bir düğümün hemen üstündeki düğüme o düğümün parent'ı, hemen altındakilere ise child'ları (çocukları) denir. Bu ilişki yönlüdür: A, B'nin parent'ı ise, B de A'nın child'ıdır.
Kritik kural: Her düğümün en fazla bir parent'ı vardır (kök hariç, onun hiç parent'ı yok). Ama bir düğümün kaç çocuğu olacağına dair genel ağaçlarda sınır yoktur - 0, 1, 5, 100 çocuk olabilir. İkili ağaçlarda (binary tree) ise en fazla 2 çocuk sınırı vardır.
Aynı parent'a sahip düğümlere kardeş (sibling) denir. Tıpkı gerçek hayattaki kardeşler gibi - aynı ebeveynden geliyorlar. Yukarıdaki örnek ağaçta B, C ve D kardeştir çünkü hepsinin parent'ı A'dır. E ve F de kardeştir (ikisinin de parent'ı B).
İki düğüm arasındaki bağlantıya kenar (edge) denir. Her kenar bir parent-child ilişkisini temsil eder. Daha önce bahsettiğimiz gibi, n düğümlü bir ağaçta tam olarak n-1 kenar bulunur. Bunun sebebi basit: kök hariç her düğümün tam olarak bir parent'a bağlantısı var, yani n-1 bağlantı (kenar).
Herhangi bir düğümü ve o düğümün altındaki tüm düğümleri alırsanız, bu kendi başına geçerli bir ağaç oluşturur - buna alt ağaç denir. Bu kavram recursive tanımla doğrudan bağlantılı: bir ağaç, kök ve kökün alt ağaçlarından oluşur. Alt ağaç kavramı, ağaç algoritmalarında sürekli kullanılır - "sol alt ağaca git", "sağ alt ağaçta ara" gibi.
Ağaçlarda düğümlerin "nerede olduğunu" tanımlamak için iki önemli kavram kullanılır: derinlik ve yükseklik. Bu kavramlar özellikle ağaç algoritmalarının karmaşıklık analizinde kritik rol oynar.
Derinlik (Depth): Bir düğümün kökten ne kadar uzakta olduğunu gösterir. Kökten o düğüme giderken kaç kenar geçtiğinizi sayarsınız - işte bu sayı o düğümün derinliğidir. Kökün derinliği 0'dır (kendisine gitmek için kenar geçmiyorsunuz). Kökün çocuklarının derinliği 1, torunlarının derinliği 2, vs.
Yükseklik (Height): Bir düğümden en uzaktaki yaprağa olan mesafedir. Yaprakların yüksekliği 0'dır (altlarında hiçbir şey yok). Ağacın yüksekliği = kökün yüksekliği = en derin yaprağın derinliği. Yükseklik, o düğümün altındaki alt ağacın ne kadar "uzun" olduğunu gösterir.
Kökten o düğüme olan kenar sayısı
O düğümden en uzak yaprağa olan kenar sayısı
Bu iki kavram sık karıştırılır. Hatırlaması kolay bir yol: Derinlik yukarıdan aşağı bakıyor (kökten düğüme), yükseklik aşağıdan yukarı bakıyor (yapraktan düğüme).
Pratik örnek: Bir dosya sisteminde /home/kullanici/belgeler/rapor.pdf dosyasının derinliği 4'tür (kök dizinden 4 adım). Yüksekliği ise 0'dır çünkü bir dosya olduğu için altında başka bir şey yok (yaprak).
Neden önemli? Algoritmaların çalışma süreleri genellikle ağacın yüksekliğine bağlıdır. Mesela dengeli bir ikili arama ağacında arama O(h) sürer, burada h ağacın yüksekliğidir.
Şimdiye kadar "genel ağaç" yapısını gördük - bir düğümün istediği kadar çocuğu olabiliyor. Pratikte ise en sık kullanılan ağaç türü ikili ağaç (binary tree)'dır. İkili ağaçta her düğümün en fazla 2 çocuğu olabilir ve bu çocuklar sol (left) ve sağ (right) olarak adlandırılır.
Neden "en fazla 2"? Bir düğümün 0 çocuğu olabilir (yaprak), 1 çocuğu olabilir (sadece sol veya sadece sağ), veya 2 çocuğu olabilir (hem sol hem sağ). Ama 3 veya daha fazla çocuk olamaz.
Sol ve sağ neden önemli? Genel ağaçlarda çocuklar sadece bir liste içinde tutulur - sıraları pek önemli değil. Ama ikili ağaçlarda sol çocuk ile sağ çocuk farklı anlamlara sahiptir. Özellikle İkili Arama Ağacı (BST)'nda sol çocuk her zaman parent'tan küçük, sağ çocuk her zaman büyük değerleri tutar - bu sayede logaritmik arama yapılabilir.
İkili ağaçlar programlamada en yaygın ağaç türüdür, çünkü:
1. Basitlik: Her düğümün sadece sol ve sağ pointer'ı var - kodlaması ve anlaması kolay.
2. Verimlilik: Dengeli bir ikili ağaçta arama, ekleme ve silme işlemleri O(log n) sürede yapılabilir - milyonlarca veri arasında bile hızlı.
3. Yaygın Kullanım: BST (Binary Search Tree), Heap, AVL Tree, Red-Black Tree gibi kritik veri yapılarının hepsi ikili ağaç temelli. Veritabanı indeksleri, öncelik kuyrukları, sözlükler hep bunları kullanır.
4. Recursive Yapı: "Sol alt ağaç" ve "sağ alt ağaç" olarak ikiye bölünmesi, divide-and-conquer algoritmaları için ideal.
Elbette var! Her düğümün en fazla 3 çocuğu olan ternary tree (üçlü ağaç), 4 çocuğu olan quaternary tree (dörtlü ağaç), hatta k çocuğu olan k-ary tree gibi yapılar tanımlanabilir.
Ancak pratikte bu yapılar ikili ağaçlar kadar yaygın değildir. Bunun birkaç sebebi var:
• Teorik güç aynı: Herhangi bir k-ary ağaç, ikili ağaca dönüştürülebilir. Yani ikili ağaçla yapamayacağınız bir şey yok.
• Kodlama karmaşıklığı: 2 çocuk için left ve right yeterli. Ama k çocuk için dinamik bir liste yönetmeniz gerekir - daha karmaşık.
• Özel durumlar: Üçlü ve dörtlü ağaçlar genellikle çok özel alanlarda kullanılır. Örneğin B-tree veritabanı indekslerinde, quadtree iki boyutlu uzay bölümlemede (oyunlarda çarpışma tespiti gibi), octree üç boyutlu grafiklerde kullanılır.
Kısacası: Bu derste ikili ağaçlara odaklanacağız çünkü temel kavramları öğrendikten sonra diğer ağaç türlerini anlamak çok daha kolay olacak.
Ağaç veri yapısının teorik kısmını gördük, şimdi bunu Python'da nasıl kodlayacağımıza bakalım. Python'da hazır bir "Tree" sınıfı yoktur - ağaçları kendimiz düğüm (node) sınıfları oluşturarak temsil ederiz.
Temel fikir şu: Her düğüm iki şey tutar: (1) kendi verisini, (2) çocuklarına referansları. Genel ağaçlarda çocuklar bir liste içinde tutulur. İkili ağaçlarda ise sadece left ve right pointer'ları vardır.
Aşağıdaki kodda basit bir dosya sistemi modelleyeceğiz. Her düğüm bir klasör veya dosya adı tutuyor ve çocukları bir liste içinde saklıyor.
TreeNode sınıfı: Her düğümü temsil eden sınıf. İki önemli özelliği var:
self.data → Düğümün tuttuğu veri (burada klasör/dosya adı)
self.children = [] → Çocuk düğümlerin listesi. Başta boş, sonra eklenir.
add_child() metodu: Yeni bir çocuk düğümü listeye ekler. root.add_child(home) dediğimizde, home düğümünü root'un çocukları listesine ekliyoruz.
print_tree() fonksiyonu: Bu fonksiyon recursive - yani kendini çağırıyor! Nasıl çalışıyor?
1. Önce mevcut düğümü yazdır (uygun girintiyle)
2. Sonra her çocuk için print_tree(child, level + 1) çağır
3. Her çocuk da kendi çocuklarını aynı şekilde yazdırır...
Bu recursive yaklaşım, ağaçları işlemenin en doğal yoludur. Ağacın derinliği ne olursa olsun, aynı mantık çalışır.
# Çok çocuklu ağaç için Node sınıfı
class TreeNode:
"""Çok çocuklu genel ağaç düğümü"""
def __init__(self, data):
self.data = data
self.children = [] # Çocuklar listesi (0 veya daha fazla)
def add_child(self, child_node):
"""Çocuk ekle"""
self.children.append(child_node)
def __repr__(self):
return f"TreeNode({self.data})"
# Dosya sistemi örneği oluşturalım
# Yapı: /
# ├── home
# │ ├── kullanici1
# │ └── kullanici2
# └── usr
# ├── bin
# └── lib
root = TreeNode("/") # Kök dizin
home = TreeNode("home")
usr = TreeNode("usr")
root.add_child(home) # home, root'un çocuğu
root.add_child(usr) # usr, root'un çocuğu
user1 = TreeNode("kullanici1")
user2 = TreeNode("kullanici2")
home.add_child(user1) # kullanici1, home'un çocuğu
home.add_child(user2)
bin_dir = TreeNode("bin")
lib_dir = TreeNode("lib")
usr.add_child(bin_dir)
usr.add_child(lib_dir)
# Ağaç yapısını inceleyelim
print("=== Ağaç İlişkileri ===")
print(f"Kök: {root.data}")
print(f"Kökün çocukları: {[c.data for c in root.children]}")
print(f"home'un çocukları: {[c.data for c in home.children]}")
print(f"usr'nin çocukları: {[c.data for c in usr.children]}")
print(f"kullanici1'in çocukları: {[c.data for c in user1.children]}") # Boş - yaprak!
# Ağacı hiyerarşik yazdır (DFS - Depth First Search)
def print_tree(node, level=0):
"""Ağacı hiyerarşik yazdır - RECURSIVE FONKSİYON"""
indent = " " * level # Her seviye için 2 boşluk ekle
print(f"{indent}📁 {node.data}")
# Bu kısım recursive: her çocuk için aynı fonksiyonu çağır
for child in node.children:
print_tree(child, level + 1) # level+1: bir seviye daha derin
print("\n=== Ağaç Yapısı (Hiyerarşik) ===")
print_tree(root)İkili ağaçlarda her düğümün en fazla 2 çocuğu olabilir. Bu yüzden çocukları liste yerine doğrudan left ve right olarak tutarız. Bu daha basit ve verimlidir.
Genel ağaçta: self.children = [] → Çocuklar bir liste, istediğiniz kadar ekleyebilirsiniz.
İkili ağaçta: self.left = None ve self.right = None → Sadece iki pointer, en fazla 2 çocuk.
İkili ağaç kodu daha basit görünür çünkü "children listesi" yönetmek yerine sadece iki değişken var. Ayrıca node.left ve node.right şeklinde doğrudan erişim, node.children[0] ve node.children[1]'den daha okunaklı.
# İkili ağaç için Node sınıfı
class BinaryNode:
"""İkili ağaç düğümü - en fazla 2 çocuk"""
def __init__(self, data):
self.data = data
self.left = None # Sol çocuk (başta yok)
self.right = None # Sağ çocuk (başta yok)
# Örnek ikili ağaç oluşturalım:
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root = BinaryNode(1)
root.left = BinaryNode(2)
root.right = BinaryNode(3)
root.left.left = BinaryNode(4)
root.left.right = BinaryNode(5)
root.right.right = BinaryNode(6) # Sağ çocuğun sadece sağ çocuğu var
# Ağacı yazdırma fonksiyonları (3 farklı sıralama)
def inorder(node):
"""Sol - Kök - Sağ sıralaması"""
if node is None:
return
inorder(node.left) # Önce sol alt ağaç
print(node.data, end=" ") # Sonra kendisi
inorder(node.right) # En son sağ alt ağaç
def preorder(node):
"""Kök - Sol - Sağ sıralaması"""
if node is None:
return
print(node.data, end=" ") # Önce kendisi
preorder(node.left) # Sonra sol alt ağaç
preorder(node.right) # En son sağ alt ağaç
def postorder(node):
"""Sol - Sağ - Kök sıralaması"""
if node is None:
return
postorder(node.left) # Önce sol alt ağaç
postorder(node.right) # Sonra sağ alt ağaç
print(node.data, end=" ") # En son kendisi
print("=== İkili Ağaç Gezinme (Traversal) ===")
print("Inorder (Sol-Kök-Sağ): ", end="")
inorder(root)
print()
print("Preorder (Kök-Sol-Sağ): ", end="")
preorder(root)
print()
print("Postorder (Sol-Sağ-Kök): ", end="")
postorder(root)
print()
# Düğüm sayısını hesapla (recursive)
def count_nodes(node):
"""Ağaçtaki toplam düğüm sayısı"""
if node is None:
return 0
# 1 (kendisi) + sol alt ağaçtaki düğümler + sağ alt ağaçtaki düğümler
return 1 + count_nodes(node.left) + count_nodes(node.right)
print(f"\nToplam düğüm sayısı: {count_nodes(root)}")Bir ağaçtaki tüm düğümleri belirli bir sırayla ziyaret etmeye traversal denir. İkili ağaçlarda 3 temel traversal yöntemi var:
Inorder (Sol-Kök-Sağ): Önce sol alt ağacı gez, sonra kökü işle, en son sağ alt ağacı gez. BST'lerde bu sıralama elemanları küçükten büyüğe verir!
Preorder (Kök-Sol-Sağ): Önce kökü işle, sonra sol, en son sağ. Ağacı kopyalamak veya serialize etmek için kullanılır.
Postorder (Sol-Sağ-Kök): Önce çocukları işle, en son kökü. Ağacı silmek veya alt ağaç hesaplamaları için kullanılır.
Bu üç yöntem de recursive'dir - dikkat ederseniz hepsi aynı kalıba uyuyor, sadece print satırının yeri değişiyor!
Recursive fonksiyonları anlamak başta kafa karıştırıcı olabilir. Hadi adım adım düşünelim:
Bir recursive fonksiyon çağrıldığında, bilgisayar o anki durumu (hangi düğümdeyiz, nereye kadar geldik) bir call stack'e kaydeder. Tıpkı bir kitap yığını gibi - en son koyduğunuz kitabı ilk alırsınız (LIFO).
Her recursive fonksiyonun bir base case'i (durma koşulu) olmalıdır. Ağaç traversal'da bu:
if node is None:
return # Boş düğüme ulaştık, geri dön!Bu olmazsa fonksiyon sonsuza kadar kendini çağırır ve program çöker (stack overflow).
Ağaçta her düğüm için şunu düşünün: "Ben sadece kendimle ilgileniyorum, çocuklarım kendi işlerini halleder."
def inorder(node):
if node is None:
return
inorder(node.left) # ← "Sol çocuğum, sen git işini yap"
print(node.data) # ← "Benim sıram geldi, kendimi yazdır"
inorder(node.right) # ← "Sağ çocuğum, şimdi senin sıran"Şu ağacı düşünelim ve inorder traversal yapalım:
1
/ \
2 3
Adım adım:
inorder(1) çağrıldı → Stack: [1]inorder(2) çağrıldı (1'in solu) → Stack: [1, 2]inorder(None) çağrıldı (2'nin solu) → None, hemen return → Stack: [1, 2]inorder(None) çağrıldı (2'nin sağı) → None, hemen returninorder(3) çağrıldı (1'in sağı) → Stack: [1, 3]inorder(None) (3'ün solu) → returninorder(None) (3'ün sağı) → returnTek fark print satırının nerede olduğu:
| Traversal | print Yeri | Düşünce |
|---|---|---|
| Inorder | Ortada (sol-kök-sağ) | "Önce solumu bitireyim, sonra konuşurum" |
| Preorder | Başta (kök-sol-sağ) | "Önce ben konuşayım, sonra çocuklar" |
| Postorder | Sonda (sol-sağ-kök) | "Çocuklar bitirsin, en son ben" |
Bir traversal yöntemi seçin ve adım adım izleyin. Her adımda call stack'in nasıl değiştiğini ve hangi düğümün işlendiğini görün.