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