# Chapter 60
dD Range and Segment Tree

Gabriele Neyer

This chapter presents the CGAL range tree and segment tree data structures.

The range tree is theoretically superior to the Kd-tree, but the latter often seems to perform better. However, the range tree as implemented in CGAL is more flexible than the Kd-tree implementation, in that it enables to layer together range trees and segment trees in the same data structure.

### Concepts

RangeSegmentTreeTraits_k
Sublayer

### Traits Classes

CGAL::Range_segment_tree_traits_set_2<R>
CGAL::Range_segment_tree_traits_set_3<R>
CGAL::Range_tree_traits_map_2<R,T>
CGAL::Range_tree_traits_map_3<R,T>
CGAL::Segment_tree_traits_map_2<R,T>
CGAL::Segment_tree_traits_map_3<R,T>
CGAL::tree_interval_traits
CGAL::tree_point_traits

### Search Structure Classes

CGAL::Range_tree_d<Data, Window, Traits>
CGAL::Range_tree_k<Traits>
CGAL::Segment_tree_d<Data, Window, Traits>
CGAL::Segment_tree_k<Traits>
CGAL::Tree_anchor<Data, Window>

### Alphabetical Listing of Reference Pages

- RangeSegmentTreeTraits_k

- Range_segment_tree_traits_set_2<R>

- Range_segment_tree_traits_set_3<R>

- Range_tree_d<Data, Window, Traits>

- Range_tree_k<Traits>

- Range_tree_traits_map_2<R,T>

- Range_tree_traits_map_3<R,T>

- Segment_tree_d<Data, Window, Traits>

- Segment_tree_k<Traits>

- Segment_tree_traits_map_2<R,T>

- Segment_tree_traits_map_3<R,T>

- Sublayer

- tree_interval_traits

- tree_point_traits

- Tree_anchor<Data, Window>