Mehrdimensionale Binärbäume

Binärbäume sind ein wichtiges Konzept in der Informatik [14]. Die Speicherung von Daten erfolgt in den Blättern von binären Bäumen, wobei die Schlüssel so gewählt werden, dass jeweils eine Halbierung des Datenraums auftritt. Dies erlaubt einen Zugriff auf die Daten in $\log(n)$-Zeit [14]. Mehrdimensionale Binärbäume ($k$D-Bäume, hier $k=3$) verallgemeinern dieses Konzept der Halbierung des Datenraumes auf höhere Dimensionen. Die Idee dabei ist, Datenpunkte in einem Binärbaum so zu speichern, dass es während der Suche im Baum möglich ist, ganze Unterbäume abzuschneiden, die den nächsten Punkt nicht enthalten können.