The Arbitrary Substitution Principle

There is, I believe, an important principle in software development for which I've found no discussion elsewhere. It's a principle that therefore deserves more exposure. It's the Arbitrary Substitution Principle (ASP). Cleopatra supposedly died from the bite of an asp [in fact, we're told by Wikipedia that that version of events is fake news].

But you too can be "bitten" by this particular asp if you're not careful.

There's a well-known problem in the study of binary search trees: Hibbard deletion. Here's some code that will do the job:

    private Node delete(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0) x.smaller = delete(x.smaller, key);
        else if (cmp > 0) x.larger = delete(x.larger, key);
        else {
            if (x.larger == null) return x.smaller;
            if (x.smaller == null) return x.larger;
            Node t = x;
            x = min(t.larger);
            x.larger = deleteMin(t.larger);
            x.smaller = t.smaller;
        }
        x.count = size(x.smaller) + size(x.larger) + 1;
        return x;
    }

Do you see anything wrong with this code? Look at the following three statements:

            x = min(t.larger);
            x.larger = deleteMin(t.larger);
            x.smaller = t.smaller;

We could instead have written:

            x = max(t.smaller);
            x.smaller = deleteMax(t.smaller);
            x.larger = t.larger;

Why did we substitute the first form in favor of the second form? No good reason. Note that, if there had been a good reason, we should have documented it in the form of a comment.

In fact, using the first code fragment leads to very poor performance--where operations on the BST become O(N^0.5) rather than O(log N). Choosing which to use randomly (or simply alternating) can ameliorate this problem significantly.

This sort of thing is a code smell no less serious than many other code smells.

OK, back to work!