## CGAL::Kd_tree<Traits, Splitter, UseExtendedNode>

### Definition

The class Kd_tree<Traits, Splitter, UseExtendedNode> defines a k-d tree.

#include <CGAL/Kd_tree.h>

### Parameters

Expects for the first template argument a model of the concept SearchTraits, for example CGAL::Search_traits_2<CGAL::Cartesian<double> >.

Excepts for the second template argument a model for the concept Splitter. It defaults to Sliding_midpoint<Traits>.

Expects for the third template argument CGAL::Tag_true, if the tree shall be built with extended nodes, and CGAL::Tag_false otherwise.

### Types

Traits::Point_d | Point_d; | Point class.
Traits::FT | FT; | Number type.

Kd_tree<Traits, Splitter, UseExtendedNode>::Splitter;
| Splitter type.
Kd_tree<Traits, Splitter, UseExtendedNode>::iterator;
| Bidirectional iterator with value type Point_d that allows to enumerate all points in the tree.

| advanced |

Kd_tree<Traits, Splitter, UseExtendedNode>::Node_handle;
| A handle with value type Kd_tree_node<Traits,Splitter>.
Kd_tree<Traits, Splitter, UseExtendedNode>::Point_d_iterator;
| Random access iterator with value type Point_d*.

| advanced |

### Creation

Kd_tree<Traits, Splitter, UseExtendedNode> tree ( Splitter s=Splitter());
| Constructs an empty k-d tree.
template <class InputIterator>

Kd_tree<Traits, Splitter, UseExtendedNode> tree ( | InputIterator first, InputIterator beyond, Splitter s=Splitter());

| Constructs a k-d tree on the elements from the sequence [first, beyond) using the splitting rule implemented by s. The value type of the InputIterator must be Point_d.

### Operations

void | tree.insert ( Point_d p)
|  | Inserts the point p in the k-d tree.
template <class InputIterator>

void

tree.insert ( | InputIterator first, InputIterator beyond)

|  | Inserts the elements from the sequence [first, beyond) in the k-d tree. The value type of the InputIterator must be Point_d.
template <class OutputIterator, class FuzzyQueryItem>
OutputIterator | tree.search ( OutputIterator it, FuzzyQueryItem q)
|  | Reports the points that are approximately contained by q. The types FuzzyQueryItem::Point_d and Point_d must be equivalent.
iterator | tree.begin () | Returns an iterator to the first point in the tree.
iterator | tree.end () | Returns the corresponding past-the-end iterator.
void | tree.clear () | Removes all points from the k-d tree.
unsigned int | tree.size () | Returns the number of points that are stored in the tree.

| advanced |

Node_handle | tree.root () | Returns a handle to the root node of the tree.
Kd_tree_rectangle<Traits>
| tree.bounding_box ()
|  | returns a const reference to the bounding box of the root node of the tree.
std::ostream& | tree.statistics ( std::ostream& s)
|  | Inserts statistics of the tree into the output stream s.

| advanced |

### See Also

Tree. CGAL::Kd_tree_node<Traits>,
CGAL::Search_traits_2<Kernel>,
CGAL::Search_traits_3<Kernel>,
CGAL::Search_traits<FT_,Point,CartesianIterator,ConstructCartesianIterator>.