--- title: 'Çok Boyutlu Ağaçlar' source: 'https://academia.sh/tr/kurslar/veri-yapilari/cok-boyutlu-agaclar' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:08:03+00:00' license: 'CC BY-SA 4.0' --- # Çok Boyutlu Ağaçlar Uzamsal sorgular, k-d ağacında dönüşümlü bölme, en yakın komşu araması, budama ve boyut laneti. Buraya kadarki arama yapıları tek bir eksende sıralıyordu: her düğümde "küçük mü büyük mü" sorusu tek bir değere göre yanıtlanıyordu. Bazı veriler tek eksene sığmaz. Harita üzerindeki bir nokta iki koordinat, bir sensör kaydı sıcaklık ve nem, bir belge gömmesi yüzlerce sayı taşır. Bu verilerde sorulan sorular da farklıdır: **"şu noktaya en yakın kayıt hangisi"** veya **"şu dikdörtgen içindeki tüm noktalar"**. ## Tek Boyutlu Yapılar Neden Yetmez Noktalar yalnızca birinci koordinata göre sıralanırsa, o eksende yakın olan noktalar bulunabilir. Ancak birinci koordinatı yakın iki nokta, ikinci koordinatta çok uzak olabilir; sıralama, gerçek yakınlık hakkında bilgi vermez. İki ayrı dizin — biri her eksen için — tutulsa bile sonuç değişmez: her dizin bir eksende aday listesi verir, ama kesişimleri hesaplamak tüm adayları gezmeyi gerektirir. Gereken şey, uzayı **tüm boyutları birlikte** dikkate alarak bölen bir yapıdır. ## k-d Ağacı **k-d ağacı**, ikili arama ağacının çok boyutlu genellemesidir. Tek farkı, her düğümde karşılaştırmanın hangi boyuta göre yapıldığıdır: bölme boyutu, **derinliğe göre dönüşümlü** seçilir. İki boyutlu bir kümede kök birinci koordinata, çocukları ikinci koordinata, torunları yine birinciye göre böler. Her düğüm, uzayı bir doğruyla ikiye ayırır; alt ağaçlar bu yarı düzlemlere karşılık gelir. ```python class KdDugum: def __init__(self, nokta: tuple[float, ...], eksen: int) -> None: self.nokta = nokta self.eksen = eksen self.sol: "KdDugum | None" = None self.sag: "KdDugum | None" = None def kd_kur(noktalar: list[tuple[float, ...]], derinlik: int = 0) -> KdDugum | None: """Ortanca noktayı seçerek dengeli k-d ağacı kurar.""" if not noktalar: return None boyut = len(noktalar[0]) eksen = derinlik % boyut # dönüşümlü bölme sirali = sorted(noktalar, key=lambda p: p[eksen]) orta = len(sirali) // 2 dugum = KdDugum(sirali[orta], eksen) dugum.sol = kd_kur(sirali[:orta], derinlik + 1) dugum.sag = kd_kur(sirali[orta + 1:], derinlik + 1) return dugum noktalar = [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)] kok = kd_kur(noktalar) print(kok.nokta, kok.eksen) # (7, 2) 0 print(kok.sol.nokta, kok.sag.nokta) # (5, 4) (9, 6) ``` Kurulumda ortanca nokta seçilir; böylece iki alt ağaç eşit büyüklükte olur ve yükseklik $O(\log n)$'de kalır. Ortanca seçimi sıralamayla yapıldığında kurulum $O(n \log^2 n)$ sürer; doğrusal zamanlı seçim algoritmasıyla $O(n \log n)$'e iner. Seçim algoritmaları **Algoritmalar** kursunun konusudur. ## En Yakın Komşu Araması Aramanın çekirdek fikri budamadır: bir alt ağaç, o ana kadar bulunan en iyi adaydan kesinlikle daha uzaksa hiç gezilmez. Adımlar şunlardır: 1. Sorgu noktasının hangi tarafa düştüğüne bakarak ağaçta aşağı in; ulaşılan yaprak ilk adaydır. 2. Geri dönerken her düğümde, düğümün kendisinin daha yakın olup olmadığını sına. 3. Bölme doğrusuna olan uzaklık, şu ana kadarki en iyi uzaklıktan **küçükse** öbür alt ağaç da gezilir; büyükse o alt ağacın tamamı elenir. Üçüncü adım, verimliliğin tamamını sağlar: bölme doğrusuna uzaklık, o taraftaki herhangi bir noktaya olan uzaklığın alt sınırıdır. ```python def uzaklik2(a: tuple[float, ...], b: tuple[float, ...]) -> float: """Karesel uzaklık; karekök almak sıralamayı değiştirmez.""" return sum((x - y) ** 2 for x, y in zip(a, b)) def en_yakin(dugum: KdDugum | None, hedef: tuple[float, ...], en_iyi=None, sayac=None): """(en yakın nokta, ziyaret edilen düğüm sayısı) döndürür.""" sayac = {"n": 0} if sayac is None else sayac if dugum is None: return en_iyi, sayac["n"] sayac["n"] += 1 if en_iyi is None or uzaklik2(dugum.nokta, hedef) < uzaklik2(en_iyi, hedef): en_iyi = dugum.nokta eksen = dugum.eksen fark = hedef[eksen] - dugum.nokta[eksen] yakin, uzak = (dugum.sol, dugum.sag) if fark < 0 else (dugum.sag, dugum.sol) en_iyi, _ = en_yakin(yakin, hedef, en_iyi, sayac) # önce yakın taraf if fark ** 2 < uzaklik2(en_iyi, hedef): # budama sınaması en_iyi, _ = en_yakin(uzak, hedef, en_iyi, sayac) return en_iyi, sayac["n"] print(en_yakin(kok, (9, 2))) # ((8, 1), 3) print(en_yakin(kok, (4, 6))) # ((4, 7), 3) ``` İlk sorguda altı noktalı ağacın yalnızca üç düğümü ziyaret edilmiştir; üç düğüm budanarak elenmiştir. Karesel uzaklık kullanılması, karekök hesabından kaçınmak içindir — sıralama değişmediği sürece gereksiz bir işlemdir. ## Aralık Sorgusu Dikdörtgen (veya çok boyutlu kutu) sorgusu aynı budama mantığını kullanır: düğümün bölme doğrusu sorgu kutusunun tümüyle bir tarafında kalıyorsa, öbür alt ağaç hiç gezilmez. Bu, aralık ağaçlarındaki fikrin uzamsal karşılığıdır: sorgu, ağaçtaki düğümlerin bir alt kümesiyle kaplanır. ## Boyut Laneti k-d ağacının vaadi düşük boyutlarda geçerlidir. Boyut sayısı arttıkça budama işe yaramaz hâle gelir. Nedeni sezgiseldir: yüksek boyutlu bir uzayda, iki nokta arasındaki uzaklıklar birbirine yaklaşır ve bölme doğrusuna olan uzaklık neredeyse her zaman en iyi adaydan küçük çıkar. Budama koşulu sağlanmaz, her iki alt ağaç da gezilir ve arama doğrusal taramaya döner. Pratik ölçüt şudur: $n \gg 2^{k}$ olmalıdır ($k$ boyut sayısı). Yirmi boyut ve bin nokta ile k-d ağacı, doğrusal taramadan hızlı değildir — üstelik ek bellek kullanır. Bu, yalnızca bir veri yapısı ayrıntısı değildir; yüksek boyutlu verinin genel bir özelliğidir ve makine öğrenmesinde uzaklık temelli yöntemlerin sınırını da belirler. Ekleme ve silme de mümkündür, ancak k-d ağacı bu işlemlerde dengesini koruyamaz: dönme gibi bir onarım işlemi tanımlı değildir. Veri sık değişiyorsa ağaç belirli aralıklarla yeniden kurulur. ## Diğer Uzamsal Yapılar | Yapı | Bölme biçimi | Uygun kullanım | |---|---|---| | Izgara | Sabit boyutlu hücreler | Düzgün dağılmış veri, sabit yarıçaplı sorgular | | Dörtlü ağaç | Her düğüm alanı dörde böler | İki boyutlu, dengesiz yoğunluk | | k-d ağacı | Dönüşümlü tek eksen | Orta boyut, nokta verisi | | R-ağacı | Kapsayan dikdörtgenler | Nokta değil alan verisi; disk tabanlı dizinler | Yüksek boyutlu verilerde — belge ve görüntü gömmeleri gibi — kesin en yakın komşu aramasından vazgeçilir ve **yaklaşık** yöntemler kullanılır. Bu yöntemler, doğrusal yapılar konusundaki atlama listesi gibi olasılıksal güvenceler verir ve vektör veritabanlarının temelini oluşturur; yapay zekâ mühendisliği müfredatında ele alınırlar. ## Özet - Uzamsal sorgular tek boyutlu sıralamayla yanıtlanamaz; yakınlık tüm boyutlara birlikte bağlıdır. - k-d ağacı, bölme boyutunu derinliğe göre dönüşümlü seçer; her düğüm uzayı ikiye ayırır. - Ortanca nokta seçimi yüksekliği logaritmik tutar. - En yakın komşu araması, bölme doğrusuna olan uzaklığı alt sınır olarak kullanıp alt ağaçları budar. - Karesel uzaklık, karekök hesabından kaçınmak için kullanılır; sıralamayı değiştirmez. - Boyut sayısı arttıkça budama etkisizleşir ve arama doğrusal taramaya döner; pratik ölçüt $n \gg 2^k$'dir. ## Sonraki Adım Ağaçlar, döngüsüz ve tek ebeveynli yapılardı. Bu kısıt kaldırıldığında — bir düğümün birden çok "üstü" olabildiğinde ve döngülere izin verildiğinde — elde edilen yapı çok daha geneldir ve ağ, harita, bağımlılık ilişkisi gibi problemlerin doğal modelidir. Kursun son konusu çizgeleri ele alacak.