We have an n-ary tree used for searching that we'd like to keep balanced.  It is currently mostly a B-tree without the balancing operations. The issue we have for implementing those is that each sub-tree has its own sorting criteria (chosen in a set of five, if that's important) and that the balancing algorithms we know don't work in that case.Is there a known algorithm which work in that case?  Or for a variation, we would probably reduce the number of criteria -- but not to one! -- and ensure that all nodes at a given level are using the same criteria if that help to keep the tree balanced at a reasonable cost and avoid rebuilding the whole tree like we do in some cases.
Balanced multi-criteria trees
data structures;trees