The problem that a binary search tree optimizes for is the lookup or sequence of lookups of data in a set with a total ordering. If you want to do range lookups instead, the binary search tree is still excellent, but possibly not optimal, though I'm under the impression that k-trees are usually just trivial extensions of a BST.
As for your heuristic, I'm not clear on your meaning. It's true that the "best" greedy top-down heuristic for a BST is to cut at the conditional median - but whether this is the same as a datum partitioning the sought from the unsought depends on more detail, especially since we're now talking about range searches.
Also, provided you have the distribution at hand and are willing to write a lot of hairy code, you can reduce the average path length by less than 1 (yay).
Thx for reply.
The difference between BSTs and k-trees is that balancing the tree is a huge misconception for k-trees.
Also, in my paper, I pose some basic hypothesis which are: data are points, without any indication of distribution and the search range is a convex in the point space. Something like a school case.
With this hypothesis which are general, balancing the tree (ak. Octree) is a hard misconception coming from BST.
It will be difficult to me to explain here why, but it's not really hard to see it.
Take this exemple and my hypothesis: you have a logarithmic distribution of points in 1D (but you don't know it particularly) and you are searching the points in random continuous ranges, then the best tree is a total unbalanced tree. And note that my heuristic will gives you a total unbalanced tree. If you have regurlarly distributed points, my heuristic will gives you an octree.
One day, I hope, I will find a damn good mathematician to prooves that the K-Means Tree is the best tree in the general hypothesis.:p or maybe i'm wrong =)
Without a distribution, the algorithms generally match what one would get with a uniform distribution, and convexity is a very small relaxation from a unit cube. These by themselves don't change much, provided the shape of the region is nice. Edit: actually, the convexity might - but then to actually use the convexity property, you'd have to move to theoretical distributions and maybe something like veb-trees.
What do you mean by total unbalanced tree? For an exponential distribution, a complete tree would naturally be suboptimal. The real trouble, as I understand it, with k-trees using the median heuristic is that there is no total ordering in more than one dimension, barring special cases, and so binary partitionings can no longer keep all sought nodes inside them.
If your larger point is that assuming a uniform distribution in octrees (instead of using a balanced tree structure) is vulnerable, then yes, I agree fully. If not, I'll conclude that you're talking about some sort of clustering, where the partitioning is spatial but the sought points are not necessarily described by a range. That's interesting, too.
As for your heuristic, I'm not clear on your meaning. It's true that the "best" greedy top-down heuristic for a BST is to cut at the conditional median - but whether this is the same as a datum partitioning the sought from the unsought depends on more detail, especially since we're now talking about range searches.
Also, provided you have the distribution at hand and are willing to write a lot of hairy code, you can reduce the average path length by less than 1 (yay).