Help with fast tree-like structure

[Lonnie Princehouse]

> A = [<A node data>, B, C]
>    B = [<B node data>, D]
>    C = [<C node data>]

Why store node data in the same list that contains the children?  It
seems like the OO approach would be more extensible, e.g.

class Node:
  def __init__(self):
     self.children = []   # list of nodes
     # store node data as attributes...

# If you wanted to, you could even implement the [] operator for the
exact same syntax:

  def __getitem__(self, i):
    return self.children[i]

(Note that using slots will make the above class more efficient,
particularly for trees with many nodes)

Of course, that doesn't answer your question.  If I've interpreted it
right, then what you're trying to do could be restated as  "make
multiple nodes at the root tier appear to be a single node", the
implication of which is that finding the n-th child of this meta-node
is now going to take O(R) time, where R is the number of concealed
roots.  You could make a new list of pseudo-roots everytime one is
inserted or deleted --- the book-keeping you refer to, probably --- and
that would make your searches constant time at the expense of inserts
and deletes which are ~linear w.r.t the total number of pseudo-roots.
 Not really any way around it... the best approach will likely be
determined by frequency of search operations vs. frequency of
insert/deletes.