How to build a balanced binary search tree where data is stored in sheets?

Question

C++ / C#

I'm trying to build a range tree for some set of n-dimensional points for learning purposes. For starters, a one-dimensional case. According to de Berg's book, for the simplicity of the algorithm, it is proposed to create a balanced binary search tree, and the data is stored in the leaves of this tree. I can't figure out how to create such a tree. Picture.

Answer 1

If you want to store data only in leaves, store an interval in non-leaf vertices. For example, in the tree in the figure, instead of the non-leaf vertex 37, store the interval [30, 49]. A similar idea is used at https://en.wikipedia.org/wiki/R-tree - read about it too if you need dots. This is just a tree for spatial indexing.