Keeping the element counts gives you something called weight-balanced binary trees. Here's a paper on them by Stephen Adams:

  http://groups.csail.mit.edu/mac/users/adams/BB/

I used a variation on these for my FSet functional collections library for Common Lisp.