non-binary self balancing tree I'm looking for a tree data structure that allows to keep the tree balanced in high (minimum high as possible).

I mean, suppose a tree where:


each node has a parameter k that is the maximum number of sons that can be attached to him, $0≤k≤N$
all the operations will be about insert and delete (no search): it's just just important that every node know the son/s, I'm not interested at all in search (&lt;0.1% of operations)


Would an adaption of RB-tree or AVL tree be a good idea for that task or there are better solutions (other data structures, other kind of tree, etc)?
You can use a binary prefix-trie (critbit-tree). It's not exactly selfbalancing, but it never requires rebalancing and imbalance is limited. For example, with 64bit keys, the maximum depth is strictly 64. This is not exactly the lowest possible height, but maybe that requirement can be relaxed because no rebalancing ever occurs?

You can find an (my) implementation here.