Ağaçlar, Binary Search Tree ve Heap
Hiyerarşik veriyi; tree, traversal, dengeli arama ağacı ve heap farkları üzerinden öğrenin.
Dosya sistemi, şirket organizasyonu ve HTML DOM’u neden liste yerine ağaçla modellenir? Çünkü her öğenin alt öğeleri olabilir ve verinin doğal ilişkisi hiyerarşiktir.
Ağaç sözlüğü
En üst düğüm root, bağlantılı alt düğüm child, üst düğüm parent olarak adlandırılır. Çocuğu olmayan düğüm leaftir. Bir düğümün root’a uzaklığı depth, ağacın en uzun yolu height olarak ifade edilir.
Traversal, bütün düğümleri belirli sırayla gezmektir. Depth-first yaklaşımda preorder, inorder ve postorder; breadth-first yaklaşımda seviye sıralı gezi kullanılır.
Binary Search Tree
BST’de her düğümün sol alt ağacındaki değerler daha küçük, sağdakiler daha büyüktür. Dengeli bir ağaçta arama, ekleme ve silme O(log n) olabilir. Değerler sıralı eklenip ağaç tek dala dönüşürse maliyet O(n) olur.
AVL ve red-black tree gibi dengeli ağaçlar rotasyonlarla yüksekliği sınırlar. Karşılığında ekleme/silme uygulaması karmaşıklaşır. Veritabanı indekslerinde disk erişimine uygun B-tree ailesi yaygındır.
Heap farklı bir ağaçtır
Min-heap’te parent her zaman çocuklarından küçük veya eşittir. Yalnızca en küçük öğeyi hızlı bulma garantisi vardır; BST gibi genel sıralı arama sunmaz. peek minimumu O(1), ekleme ve minimumu çıkarma O(log n) sürer.
Priority queue için heap uygundur: en acil iş kökte tutulur. “Bu değer var mı?” sorusu sık soruluyorsa hash table; sıralı aralık gerekiyorsa dengeli BST daha uygundur.
Fonksiyonlar ne yapar?
Recursive inorder traversal önce sol alt ağacı, sonra düğümü, sonra sağ alt ağacı gezer. BST’de bu sıra değerleri küçükten büyüğe üretir. Base case olarak node === null kontrolü recursion’ın sonlanmasını sağlar.
Alıştırma
10, 5, 15, 3, 7 değerleriyle bir BST çizin. Preorder, inorder ve postorder çıktılarını ayrı ayrı yazın; sıralı sonucu hangi gezinmenin verdiğini gözlemleyin.