Quadtree

Ein Quadtree oder Quaternärbaum ist in der Informatik eine Baumstruktur, in der jeder innere Knoten genau vier Kindknoten hat. Quadtrees werden hauptsächlich zur Unterteilung eines zweidimensionalen Raumes genutzt, indem rekursiv in vier Bereiche (Quadranten) unterteilt wird. Die Bereiche können quadratisch oder rechteckig sein oder beliebige Formen haben. Eine ähnliche Aufteilung ist als Q-tree bekannt. Alle Formen von Quadtrees teilen bestimmte Merkmale: * Sie zerlegen den Raum in anpassbare Bereiche * Jeder Bereich hat eine Maximalkapazität. Wird diese erreicht, so wird der Bereich unterteilt. * Das Baumverzeichnis folgt der räumlichen Unterteilung des Quadtrees.