RedBlackTree with Array Store

[Steven Wawryk]

I haven't looked at your code, but I came across the idea of a vector 
map in C++ (based on a std::vector of std::pairs) with some performance 
advantages over std::map if there aren't a lot of insertions and 
deletions.  The idea is a good one.  Whether it's best as a custom store 
for RedBlackTree or as a separate container I don't know.

The "unsorted binary tree" you mention doesn't sound right.  Such a 
container would need to be kept sorted.

On 14/01/11 15:55, %u wrote:
> Hi,
>
> I've noticed that, just as you can have a heap with an array-backed store, you
> can also have a binary search tree with the same store (although structured
> differently; see attachment for a bare-bones unsorted binary tree
> implementation -- which I have NOT yet tested, but which I can test if it will
> be used). The improvement will be in data locality, and while it may seem to
> use a bit more space than a link-based tree, I think it's worth it to let the
> RedBlackTree class use a custom store, such as any store that has
> getLeft/getRight/setLeft/setRight methods, and that uses opaque pointers.
>
> How does this idea sound?
> Thank you!