The simplest possible balance criterion--let the tree take any shape as long as its height is logarithmic--can be used to produce very efficient code. A general balanced tree is a plain binary search tree with no balance information in the nodes. Balance is maintained by partial rebuilding. This data structure can be implemented very efficiently. (In experiments, it performs better than the skip list and the plain unbalanced tree.)