Q:

How can I eliminate gaps in the breadth-first ordering of a binary search tree?

A gap-less binary search tree is a self-balancing binary search tree with the gap-less property. The gap-less property states that there are no gaps in the breadth-first ordering of the tree. A gap in the breadth-first ordering is best defined through a diagram. In the image below, the areas highlighted by red dashed circles are considered gaps in the breadth-first ordering: 

If this tree were restructured to eliminate the gaps, it would look like this:

If the number 7 were added to this restructured tree without re-balancing, it would look like this: 

Again, after removing the gaps: 

Is there a log(n) algorithm to ensure the gap-less property after insertions and deletions to trees of arbitrary sizes?

A:

Is there a log(n) algorithm to ensure the gap-less property after insertions and deletions to trees of arbitrary sizes?

No.
To see why, consider this tree (which has the gap-less property):
           4
          / \
         2   6
        /|   |\
       1 3   5 7

To insert 8, you'd need to end up with this:
           5
          / \
         3   7
        /|   |\
       2 4   6 8
      /
     1

which clearly requires visiting every node at least once, because every single node has a different parent afterward than it had before. Therefore, you cannot possibly guarantee better than O(n) time.
Likewise, to remove 1, you'd need to end up with this:
           5
          / \
         3   7
        /|   |
       2 4   6

which, same problem.

