Ok, I promise, this is the last entry about skewtrees. I just wanted to point out that this problem is widely known and dealt with in the algorithms literature under the name "optimal binary search trees". I found that out by accident while googling for something else. Just search for "optimal binary search trees" and you'll see what I mean. There are even top-down approaches that provide almost optimal solutions.
