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

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.