RedBlackTree with Array Store

[Steven Wawryk]

I see.  It's not what I meant when I described the vector map.  That has 
no pointers/indices stored in it.  The position in the tree is implied 
by the index.

On 14/01/11 18:21, %u wrote:
>> The "unsorted binary tree" you mention doesn't sound right.  Such a
> container would need to be kept sorted.
>
> It would, IF it was implemented the same way as a heap. But it's not. Take a look
> at my implementation if you get the chance; every node has four members in
> addition to the value, which are the indices of the (1) node (self-pointer), (2)
> parent, (3) left child, and (4) right child. There's no direct mapping between the
> place of a node in the tree and its place in the array, so there's no need to keep
> anything sorted.
>
> Hopefully that made sense... let me know if it doesn't. :)