Foro de elhacker.net

#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