Quadtree (2D) nicht-balancierte Datenstruktur für mehrdimensionale Punkt-Objekte (hier: 2-dimensionale)•Ansatz: Jeder Knoten hat sowohl für die x- als auch für die y-Koordinate je zwei Kindknoten: x (<=,>) und y (<=,>) (je Knoten also vier Kindknoten „•Quad“-•Tree)•Aufbau des Baums:•erster Punkt bildet Wurzel•bei jedem weiteren Punkt:•Bestimmung des Quadranten, in dem Punkt liegt•Abstieg in entsprechenden Kindknoten•falls kein Kindknoten für diesen Quadranten existiert:•Hinzufügen eines Kindknotens•hier: Hauptspeicherstruktur •(Verzweigungsgrad = 2•d• für d Dimensionen)•später: Quadrant = Bucket zur Verwendung als•Sekundärspeicherstruktur 3D: Octree•1D: Segmenttree