K-d-Baum

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Hinweis: Der korrekte Titel dieses Artikels lautet „k-d-Baum oder kd-Baum“. Diese Schreibweise ist aufgrund technischer Einschränkungen derzeit nicht möglich.

Der k-d-Baum oder auch k-dimensionale-Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem $\mathbb{R}^k$ . Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher, dafür ist der Speicheraufwand unabhängig von der Dimension $k$ $O (n)$ .

[Bearbeiten] Definition

Es gibt homogene und inhomogene k-d-Bäume. Bei homogenen k-d-Bäumen speichert jeder Knoten einen Datensatz. Bei der inhomogenen Variante enthalten die inneren Knoten lediglich Schlüssel, die Blätter enthalten Verweise auf Datensätze.

Bei einem inhomogenen k-d-Baum sei $H_i(t) = (x_1, x_2, \ldots , x_{i-1}, t , x_{i+1}, \ldots , x_k)$ $1 \leq i \leq k$ die achsenparallele $(k - 1)$ -dimensionale Hyperebene an der Stelle $t$ . Für die Wurzel teilt man die Punkte durch die Hyperebene $H 1 (t)$ in zwei möglichst gleich große Punktemengen und trägt das $t$ in die Wurzel ein, links davon werden alle Punkte gespeichert, deren $x 1$ kleiner sind als t, rechts von der Wurzel alle größeren. Für den linken Sohn werden die Punkte wiederum durch eine neue Splitebene $H 2 (t)$ geteilt und die das $t$ in dem inneren Knoten gespeichert links davon werden alle Punkte gespeichert deren $x 2$ kleiner als $t$ ist. Dies wird nun rekursiv über alle Dimensionen fortgeführt. Danach wird wieder bei der ersten Dimension angefangen, bis jeder Punkt durch Hyperebenen eindeutig identifiziert werden kann.

Ein k-d-Baum lässt sich in $O (n log n)$ konstruieren. Orthogonale Bereichsanfragen lassen sich in $O(n^{1-\frac{1}{k}}+a)$ beantworten, wobei $a$ die Größe der Antwort bezeichnet. Der Speicherplatzbedarf für den Baum selbst liegt in $O (n)$ .