|parent of this internal node |
|left child node pointer |
|right child node pointer |
|bit to test at this node |
|flags -- internal consumption only |
|route attached to this node |
This is the structure which glues the internals of the tree together. This really should be private to the implementation, and should be treated as such, but is exposed here to avoid the use of void pointers above and to allow inline searches to be written.
It is the case that in normal trees very few internal nodes have attached routes. There is hence a 20% savings of memory to be gained by only allocating the attached pointer when it is actually needed.