#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