code needed for this new data structure

Want to build a C++ Template code for the following modified Binary tree structure:

each node has left, right and parent pointer.
each node has a number of values in sorted order.
If a node has to null child pointer call it a leaf node and if it has one null child pointer call it a half leaf.

Insert Algorithm:

Search for the bounding node. ie min val<data<max val

If a node is found, then check for room for another entry. If the
insert value will tit, then insert it into this node and stop.
Else remove the minimum element from the node, insert the original
insert value, and make the minimum element the new insert
value. Proceed from here directly to the leaf containing the
greatest lower bound for the node holding the original insert
value. The minimum element (the new insert value) will be
inserted into this leaf, becoming the new greatest lower bound
value for the node holding the insert value.

If the search exhausts the tree and no node bounds the insert
value, then insert the value into the last node on the search path
(which is a leaf or a half-leaf). If the insert value fits. then it
becomes the new minimum or maximum value for the node.
Otherwise, create a new leaf (so the insert value becomes the
first element in the new leaf).

If a new leaf was added, then check the tree for balance by following
the path from the leaf to the root. For each node in the
search path (going from leaf to root), if the two subtrees of a
node differ in depth by more than one level, then a rotation
must be performed Once one rotation has been done, the tree is rebalanced and processing stops.


  • Suggestion:

    1.) C++ is not intended for the 0-60 approach of writing raw templates. Doing so will increase the likelihood of an error in your algorithm.

    2.) KEEP IT SIMPLE.... Start with a specific class type definition. Then test this class with all of the possibilities for that one-time use. Once your algorithm works, archive it.

    3.) Redesign the existing class into a template for further implementation on that broad scale you desire. You know at that point that the theory (algorithm) works. You can then isolate the testing to the implementation of the algorithm on a wider scope.

    P.S. I often overwhelm myself with the desire to create instant-open architecture in all of my code. ...As a result, I sometimes create code with bugs that take more time to resolve later than would have been the case earlier.


    Excellence Breeds! Go Hard or Go Home.

    Let Penguins rule the earth.
    Break some windows today.

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!


In this Discussion