You know, I think there’s a good reason there isn’t a standard templated version of an ordered n-ary tree in C++. It’s unfortunate, then, that the way I found this out was by writing one myself. My head hurts now.
(I’d like to put the code up for download, actually, but I’m not sure if I’m allowed to – it’s possibly quite a useful piece of code for some other people, but as I wrote it at work, my company own it and I’m not sure if you’re allowed to see it)
It sounds far too much like B+ trees to be sensible. Actually, if you added a serialisation mechanism, you’d probably have half* oan RDBMS. 🙂
Kind of – except that these trees aren’t guaranteed to be balanced – and enforcing balancing would destroy the property that makes them useful.
A tree is constructed such that for any two nodes N and O with values n and o, N is a child of O if f(n,o) returns true (where f() is user definable, but will usually be some sort of is-contained-by function). It therefore follows that for a given node N, f(x,n) holds true for all X where X is below N in the tree.
The useful specialisation of this tree in my particular case is volumes in 3D space, with f(a,b) returning true if a is contained by b. This way, it’s possible to find the smallest possible volume containing a given point in space by walking the tree down to the lowest node for which our is-contained-by predicate holds true for our chosen point.