Re: [boost] Re: Indexed Map container

From: John E. Potter (jpotter_at_[hidden])
Date: 2001-06-03 20:12:30

On Sun, 3 Jun 2001 dheld_at_[hidden] wrote:

> --- In boost_at_y..., "John E. Potter" <jpotter_at_f...> wrote:
> > Yes, distance(m.begin(), iter) would get it in O(N), but it should
> > be available in O(lgN).
> 
> No, because ++iter *itself* can be O(log n).  If iter points to the 
> predecessor of the root node, for instance, it is the rightmost child 
> of root's left subtree.  To get the successor, one must climb the 
> parent nodes all the way to the top, which is clearly O(log n).  Of 
> course, if iter has a right subtree of size 1, then ++iter will be O
> (1).  But that doesn't change the fact that ++iter is O(log n) in the 
> general case, and thus distance(m.begin(), iter) is O(n log n), which 
> is abominable for frequent indexing operations.

You are missing the average case.  The number of branches in a tree
with N nodes is N - 1.  A complete traversal of the tree follows each
branch twice which is 2N when the initial step to begin and the final
step to the dummy are considered.  The worst possible height of a node
in an rb-tree is 2lgN.  Yes, you can get a single step of 2lgN but
the time for distance(begin(), iter) is still O(distance(begin(),
iter)).  Distance(iter1, iter2) must be less than 2N.  It is still
true that O(N) is unacceptable for indexing while O(lgN) is usable.

> > I know that all of this can be done with a single int added to the
> > node.  Will be interested in your use of two.
> 
> Yes, I originally started out with two ints that represented the size 
> of the left and right subtree, then realized that one int 
> representing the index of the node within it's subtree's vector 
> representation would suffice.  However, one of the rotate operations 
> requires knowing the size of a right subtree.  The size of the left 
> subtree is just equal to the index, but unless you store the size of 
> the whole subtree (or the right explicitly), you have to descend the 
> right subtree (in particular, find the rightmost child of the 
> subtree) to get its size.  This is clearly O(log n).  But rotate can 
> be called O(log n) times in the course of an insert or delete, so 
> that would make insert and delete O(log^2 n), which is not terribly 
> bad; but I opted for retaining the complexity characteristics of 
> std::map and added a size field instead.  If the general concensus is 
> that the time sacrifice is worth the storage saved, I will revert the 
> implementation to just one int.

I think you missed something there.  We have rotate left and rotate
right.  Let x be the position of X within the tree for which it is
the root.  Given a tree (T((M)R)) and rotate left at T to produce
((T(M))R), the only position which changes is r.  The new r is t +
nodes(M) + 1.  But nodes(M) is the old r; so, r += t + 1.  Given a
tree ((L(M))T) and rotate right at T to produce (L((M)T)), the only
position which changes it t.  The new t is nodes(M).  But nodes(M)
is t - l - 1; so, t -= l + 1.

John