W i l l k o m m e n   b e i   [ www.mauspfeil.com ]
 
 



 

Wörterbuch der Bedeutung
<<Zurück
Bitte wählen Sie einen Buchstaben:
A, Ä | B | C | D | E | F | G | H | I | J | K | L | M | N | O, Ö | P | Q | R | S | T | U, Ü | V | W | X | Y | Z | 0-9

Suchen:

(Groß-/Kleinschreibung wird nicht unterschieden)

Google


K-d-Baum

*** Shopping-Tipp: K-d-Baum

{{Korrekter Titel|''k''-d-Baum}} Der '''''k'''''‍'''-d-Baum''' oder auch ''k''-dimensionale-Baum ist ein Balancierter_Baum 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).

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 Blatt (Graphentheorie) 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). Kategorie:Suchbaum

Beispiel 2-d-Baum
Bild:2dbaum.svg Eine Menge von Punkten mit dazugehörigem inhomogenem 2-d-Baum

Siehe auch
Quadtree, UB-Baum, R-Baum, Bereichsbaum, Gridfile als Alternativen

Literatur
* Rolf Klein: ''Algorithmische Geometrie'', 2. Auflage. Springer-Verlag, Berlin Heidelberg 2005, ISBN 3-540-20956-5.

Weblinks

- Universität Osnabrück en:Kd-tree es:?rbol kd he:עץ kd




[Der Artikel zu K-d-Baum stammt aus dem Nachschlagewerk Wikipedia, der freien Enzyklopädie. Dort findet sich neben einer Übersicht der Autoren die Möglichkeit, den Original-Text des Artikels K-d-Baum zu editieren.
Die Texte von Wikipedia und dieser Seite stehen unter der GNU Free Documentation License.]

<<Zurück | Zur Startseite | Impressum | Zum Beginn dieser Seite