RTrees

I don't know advanced trees (as in binary, red/black, etc) but I know what I like. And I think I like this applet as an example of R-Trees:

http://www.dbnet.ece.ntua.gr/~mario/rtree/

This seems very graph/model like to me. I think you could use RTrees to do datatyping, lists and bags.

From a synopsis of the paper:
* Allows searches for contained in/overlapped with some rectangle.
* Like B+-Trees except each child key bounds all the objects below in
the hierarchy.
* Searches may now follow down multiple children because the keys can
cover overlapping area.
* Insert chooses the sub-tree that minimizes the expansion of the
bounding rectangles
* Under-full nodes are entirely re-inserted
* Nodes are split with the goal of minimizing the area of the two new
bounding rectangles

Apart from the basic RTree implementation, some other functions have
been implemented in the applet. In particular the RTree currently
supports the following operations:

* Traverse By Level: Returns a list of all nodes sorted by their level.
* Traverse Post Order: A post order traversal of the RTree nodes.
* Traverse Pre Order: A pre order traversal of the RTree nodes.
* Enclosure: Returns an enumeration of all rectangles that contain the
query rectangle or point.
* Intersection: Returns an Enumeration with all rectangles that
intersect with the query rectangle.
* Nearest Neighbor: Returns the rectangle nearest to the query point.

http://www.cs.ucr.edu/~marioh/spatialindex/

It looks to me like when to split R Trees is important. It talks about
when to split the overlapping of the boxes into to separate branches.
Again, playing with the applet it seems quite smart as to when to split
and group them.

I think traversing R-Trees is similar to log(n) but it looks like each
sub-tree may be visited more than once.

The paper I've been trying to finish reading is:
http://www.es.ucsc.edu/~tonig/rtrees/rtrees.pdf