Código
#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