k-d tree

Angol

Főnév

k-d tree (tsz. k-d trees)

1. (informatika) A k-d tree (vagy k-dimensional tree, azaz k-dimenziós fa) egy térbeli adatstruktúra, amelyet többdimenziós adatok hatékony keresésére használnak. Gyakori alkalmazási területei közé tartozik a gépi tanulás, adatbázisok, számítógépes grafika, valamint a közeli szomszéd keresés (k-NN) algoritmusok. A következő leírásban 1000 szóban részletezzük, hogyan működik, milyen célokra használható, és mik a főbb jellemzői.

---

🧠 Alapfogalom

A k-d tree egy bináris keresőfa, amelyet k dimenziós pontok (pl. (x, y) vagy (x, y, z, w, ...)) tárolására és hatékony lekérdezésére terveztek. Minden egyes szinten a fa egy adott dimenzát használ a pontok szétválasztására (pl. először x, majd y, majd z, és így tovább körforgásban).

Példa: Ha 2D pontokat (x, y) tárolunk, a fa első szintjén x szerint, a másodikon y szerint hasonlítunk, a harmadikon ismét x, stb.

---

🌳 Hogyan épül fel a k-d tree?

1. Beszúrás (építés)

A faépítés során:

1. Válasszuk ki a tengelyt a mélység (depth) alapján: axis = depth % k.
2. A pontokat az adott tengely szerint rendezzük.
3. Válasszuk ki a mediánt – ez lesz az aktuális csomópont.
4. Az alatta és felette lévő pontok a bal és jobb részfákba kerülnek.
5. Rekurzívan ismételjük a lépéseket a részfákon.

Példa (2D):

Pontok: (7,2), (5,4), (9,6), (2,3), (4,7), (8,1)

Első tengely: x → sorbarendezve x szerint → medián = (7,2) → gyökér. Bal oldalra megy (2,3), (4,7), (5,4), jobb oldalra (8,1), (9,6). Következő szint tengelye: y. Rekurzívan folytatjuk.

---

🔎 Lekérdezések

1. Közeli pont keresés (Nearest Neighbor Search)

Ha egy ponthoz legközelebbi másik pontot keresünk, a k-d fa hatékony keresést biztosít:

• Mélyre lemegyünk, követve a tengelyeken a megfelelő oldalt.
• Visszafelé jövet minden szinten megnézzük, hogy van-e értelme a másik ágat is vizsgálni (ha a gömbmetszet belelóg a másik részfába).
• A lekérdezés időkomplexitása ideális esetben O(log n), de legrosszabb esetben akár O(n) is lehet.

2. Tartomány lekérdezés (Range Query)

Pl. keresés x ∈ [2, 6] és y ∈ [3, 7] intervallumokban. Rekurzívan bejárjuk a fát, és csak akkor nézünk be egy részfába, ha az adott tartományba eshet.

---

🧮 Időkomplexitás

Művelet	Átlagos eset	Legrosszabb eset
Építés	O(n log n)	O(n log n)
Beszúrás	O(log n)	O(n)
Keresés (NN, range)	O(log n)	O(n)
Törlés	Bonyolultabb	O(n)

A legrosszabb esetek elkerüléséhez fontos a kiegyensúlyozott fa létrehozása (pl. újraépítés időnként).

---

⚙️ Implementációs részletek

Minden csomópont (node) tartalmaz:

• Egy k dimenziós pontot (pl. std::vector<double>),
• Bal és jobb gyermekmutatót (left, right),
• Tengelyt, amely szerint szétválasztottuk.

Példa C++ szerű szerkezet:

struct KDNode {
    std::vector<double> point;
    int axis;
    KDNode* left;
    KDNode* right;
};

---

🌍 Felhasználási területek

1. Gépi tanulás
   • k-NN osztályozás
   • Dimenziós csökkentés (pl. PCA utáni keresés)
2. Számítógépes grafika
   • Objektumkövetés, ütközésvizsgálat
3. Robotika
   • Navigációs pontok hatékony kezelése
4. Játékfejlesztés
   • NPC-k közti távolságalapú döntések
5. GIS és térinformatika
   • Helyalapú lekérdezések (pl. „keresd meg a legközelebbi benzinkutat”)

---

🆚 Összevetés más adatstruktúrákkal

Adatszerkezet	Előny	Hátrány
k-d tree	Gyors keresés	Dimenzió növelésével gyengül
QuadTree	2D adatokra optimalizált	Csak 2D esetén
R-tree	Intervallum-alapú	Lassabb NN keresés
HashMap	Gyors kulcs-érték	Nem használható NN-re

---

🧪 Problémák és kihívások

• Curse of dimensionality: ha a dimenziók száma nagy (k >> 10), a keresési teljesítmény gyorsan romlik.
• Egyenlőtlen adateloszlás: torz fához vezethet, ezért érdemes újraépíteni vagy kiegyensúlyozó algoritmusokat alkalmazni.

---

📌 Alternatívák magas dimenziókra

• Ball tree
• VP-tree
• Approximate Nearest Neighbor (ANN) módszerek, pl. FAISS, HNSW

---

🧾 Összefoglalás

A k-d tree egy hatékony, keresés-orientált adatstruktúra, amely többdimenziós pontokat kezel és keres bennük. Előnye, hogy:

• jól működik kis és közepes dimenziók esetén,
• gyors lekérdezést biztosít,
• egyszerűen implementálható.

Viszont nagy dimenzióknál már nem a legjobb választás, ott más módszerek kerülnek előtérbe.

További információk

• k-d tree - Szótár.net (en-hu)
• k-d tree - Sztaki (en-hu)
• k-d tree - Merriam–Webster
• k-d tree - Cambridge
• k-d tree - WordNet
• k-d tree - Яндекс (en-ru)
• k-d tree - Google (en-hu)
• k-d tree - Wikidata
• k-d tree - Wikipédia (angol)