I'm just wondering about how you distinguish complex from not complex.

Well, I don't think it's possible to draw a sharp border. Just as it's almost impossible to draw the line when you call it "light" or "dark". That doesn't mean that in a lot of cases, it's clear when it's "light" or "dark". ;-)

Anyway, for me, to call a datastructure complex it usually satisfies these points:

• It stores elements where the place in the structure implies (or is implied by) a (spacial) relationship between the elements.
• It's optimized such that queries and/or updates can be done in less time than a full scan, or a rebuild of the entire datastructure.
• It will often have some kind of associated datastructure.

Abigail