RedBlackTree with Array Store

%u wfunction at hotmail.com
Thu Jan 13 23:51:46 PST 2011


> 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. :)


More information about the Digitalmars-d mailing list