[C/C++] Insertar balanceado en Arbol binario

[_TTFH_3500]

Código (c) [Seleccionar] Expandir

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

struct nodo_binario {
  int dato;
  nodo_binario* izq;
  nodo_binario* der;
};

typedef nodo_binario* BST;


unsigned int cant_nodos(const BST b) {
  if (b == NULL) return 0;
  else return 1 + cant_nodos(b->izq) + cant_nodos(b->der);
}

/**
* Insetar en orden O(log n) x en b de manera que la cantidad de nodos del
* subarbol izquierdo (no la altura) sea 1 mayor o igual que la del subarbol derecho.
*/
void Insetar_Balanceado(int x, BST &b) {
/// x siempre mayor que todos los elementos de b.
BST aux = b;
// Buscar nodo mas a la derecha e insertar
while (aux != NULL) {
aux = aux->der;
}
aux = new nodo_binario;
aux->dato = x;
aux->der = aux->izq = NULL;

if (cant_nodos(b->der) - cant_nodos(b->izq) == 1) {
// Balancear... ?

}
}

¿Como puedo implementar este procedimiento?

Quiero rotar el árbol de manera que la cantidad de nodos del subarbol izquierdo sea 1 mayor o igual que la del subarbol derecho.
Pero no se me ocurre como hacerlo, por ejemplo:

Si el árbol es vació solo inserto y no tengo que hacer nada mas ya que queda balanceado porque la cantidad de nodos del subarbol izquierdo y derecho es igual (vale 0).

Luego si b tiene un elemento, como x es mas grande que los elementos de b al insertar a la derecha por la propiedad de los arboles binarios de búsqueda me queda desbalanceado:
1
 \
  2
ya que el subarbol derecho tiene 1 nodo y es mayor que la cantidad del izquierdo que es 0.

Debería rotar para que quede:
  2
 /
1