Çok Boyutlu Ağaçlar

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.

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.

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.