This post says

Binary Space Partitioning Trees are a generalization to dimensions > 1 of binary search trees

which indicates the binary search trees lives in 1d space.

Is my understanding right?


This just means that the elements stored in a binary search tree are one dimensional. Or more generally that they can be ordered in some meaningful way. You can think of this ordering as putting all the elements on a line, from "smallest" to "biggest" (for an appropriate notion of small and big depending on the particular case). And partitioning then always happens by cutting this line at some point. Hence the "1-dimensionality" of the binary search trees.

But in 2D space-partitioning for example, your data lives in a 2D space and you can not simply order them from "smallest" to "biggest". You need more freedom in the way you cut your space in half.

The trees themselves are just binary trees in both cases, the "dimension" comes from what the nodes represent and how the trees are used.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.