B
B
borgch2015-09-26 19:34:15
C++ / C#
borgch, 2015-09-26 19:34:15

Range tree in the general case, if the points have some matching coordinates?

I read this article here: goo.gl/kXmR7L and related chapters from de Berg, Computational Geometry. As the basis of the tree, it is proposed "to use a balanced binary search tree, in the leaves of which we will store the points of the desired set, and in the non-leaf vertices - the separating values ​​that will be searched in the tree."

A one-dimensional range-tree is just the search tree described above.
d-dimensional range-tree - a search tree (by the first coordinate X_1), similar to that described above, but at each vertex additionally storing a d-1-dimensional range-tree (by the remaining coordinates X_2 x ... x X_d) for a set of elements, which are leaves of a subtree of this vertex.

Suppose we need to build a tree from such points: (1, 2), (1, 3) and (1, 4). Obviously, it is impossible to make such a search tree that it has several identical leaves. Well, how then to build a search tree from the first x-coordinates, that is, from units?) What kind of data type is such that even such a simple example cannot store?) Where did I misunderstand the definition?

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question