Monday, May 24, 2010

[bvesrahq] Tree with Heap

An associative array (Map) between keys and values, which also supports findMinimumValue (not minimum key, which would be easy).  I'm imagining an overlay of a balanced tree (e.g., red-black) and a heap, with seven pointers per node. 

Two children pointers and a parent pointer for the balanced tree side.

Heap: children and parent, too, plus a pointer to help find "one plus" the last element in the heap, for insertions.  The heap tree is independent of the Map tree.

We need parent pointers for both trees because the node may have been found from the other tree.

Seems messy.  Ideally part of a library so one normally does not have to implement it.

No comments :