Arbol binario equilibrado (insertar y borrar)

Me da igual el lenguaje de programacion, solamente necesito la idea de como hacer para insertar y borrar elementos en un arbol binario para que siempre este equilibrado. El problema es saber como demonios el programa detecta que está desequilibrado el arbol (tu lo ves facilmente, pero hacerselo ver al programa no lo logro).
Basicamente ese es mi gran problema. El hecho de equilibrarlo una vez el programa sepa que se ha desequilibrado no creo que sea demasiado problema (tambien tiene lo suyo...)

Creo recordar que un arbol estaba equilibrado si o bien no tenía hijos o bien la profundidad de sus hijos se diferenciaba en a lo sumo 1.
Partiendo de esa premisa si es correcta tan solo tendrías que ir recorriendo el árbol hacia abajo y ver que se cumplen esas condiciones, para ello yo me ayudaría de una función que dado un árbol, te devuelva su profundidad.

Ahhh, creo que lo tengo. Lo que voy a hacer es coger todas las hojas que no tengan hijos, y de sus alturas, sacar el minimo y el maximo. Si su diferencia es 1 o 0, bien. Si es 2, es que se ha desequilibrado.
De todas formas, para hacer esto tienes que recorrer todo el arbol, y creo que hay metodos mucho mas rapidos. El prfoesor nos orientó con que partiamos de que el arbol estaba equilibrado antes de hacer la operacion (insertar o eliminar).
Y en la wikipedia he encontrado algo increible: arboles cuya complejidad de insertar y eliminar es O(log n). Es decir, la misma que la de la busqueda. Estoy intrigado por ver ese codigo, aunque muy trivial no creo que sea.

Hola,

Supongo que te refieres a un arbol balanceado.

éste artículo de la wikipedia es bastante claro. Está el algoritmo e incluso una implementación en c++ (pasarlo a C o a Java es trivial).

Saludos.

Hablas de un arbol AVL.

El método no consiste en detectar si el arbol esta equilibrado sino de mantenerlo equilibrado desde el principio.
Eso te lo digo porque el método que propones

Citar

Ahhh, creo que lo tengo. Lo que voy a hacer es coger todas las hojas que no tengan hijos, y de sus alturas, sacar el minimo y el maximo. Si su diferencia es 1 o 0, bien. Si es 2, es que se ha desequilibrado.

es muy ineficiente, no podes recorrer todo el arbol cada vez que insertas o eliminas. El recorrido se lo se hace a partir del nodo agregado/insertado y hacia arriba.

Eso se hace agregando un valor a cada nodo que valdrá 0 si sus hijos estan equilibrado, 1 si esta desequilibrado a derecha y -1 a izquierda.

Te digo que no es un algoritmo fácil, pero información hay mucha, en si el algoritmo es igual que el de una árbol binario de búsqueda al que se agregan los métodos de rotación que son los que mantienen el árbol equilibrado.

Tipicamente los métodos se llama RSI, RSD, RDI y RDD

Rotacion Simple Izquierda.
Rotacion Simple Derecha.
Rotacion Doble Izquierda.
Rotacion Doble Derecha.

Citar

Y en la wikipedia he encontrado algo increible: arboles cuya complejidad de insertar y eliminar es O(log n). Es decir, la misma que la de la busqueda. Estoy intrigado por ver ese codigo, aunque muy trivial no creo que sea.

Pues si, son muy eficientes. Tanto la eliminación como la inserción se reducen a Buscar que nodo hay que eliminar o bien en donde hay que insertarlo.

Te digo que es muy teórico, he pasado unos dos años estudiando arboles en la facultad y en realidad nunca llegue a programar mas que un simple árbol binario de búsqueda. No tiene mucho sentido, el codigo ya esta escrito, para que romperse la cabeza bigsmile bigsmile bigsmile

Si buscas arboles de búsqueda auto balanceados quizás quieras ver aquí. Hay muchos otros algoritmos, pero esos son los mas usados.

Si lo que quieres es un buen algoritmo para búsquedas con eficiencia logarítmica quizás debas revisar aquí. Que es un algoritmo mucho mas simple y con rendimiento similar al de un árbol binario siempre balanceado. (personalmente he tenido mejor experiencia con las listas de saltos)

Recuerda que "hay dos maneras de desarrollar aplicaciones, puedes hacerlas tan sencillas que sea obvio para todos que no tiene deficiencias o puedes hacerlas tan complicadas que no sean obvias las deficiencias" (Sir Charles Antony Richard Hoare) .

Ahora estoy siguiendo un libro de algoritmos de programacion en Java, y viene esto muy bien explicado.
Lo que hace es simplemente aplicar la definicion que dice PatoSilva de AVL al nodo que borras o eliminas, e ir subiendo hasta la raiz comprobando que está balanceado. Supongo que a lo mejor tambien es valido hacer rotaciones todo el rato comprobando si la raiz está balancead. Si no lo está, otra rotacion. Sino, otra..., en vez de hacer rotacion, comprobar, y si está, subir al siguiente nivel.
Primero programaré el metodo que viene en el libro, luego el mio, y compararé a ver cual es mas eficiente, y si es que funciona el mio jeejje, aunque deberia

Una funcion recursiva que recorra cada uno de los nodos en el que se te devuelva el numero de hijos, si no mal recuerdo puede tener o 0 1 o 2 hijos con lo que yo lo que haria son llamadas recursivas es decir algo como

funcion llamante()
{
       nodo //declaracion del nodo;
       recorridonodo(nodo);
}

funcion recorridonodo(nodo,numero)
{
     if (nodo.childNodes.length>0){
             i=0;
             while ( i < nodo.childNodes.length){
                    recorridonodo(nodo.childNodes[i],numero)
                 i++;
             } 
     }
}



El codigo en si no sirve para nada y faltan muchas cosas pero creo que en si la estructura, que es para lo que lo he puesto sirve, lo de numero bueno en realidad lo puse por algo pero me quede dormido delante del ordenador y no lo recuerdo XD.

----EDITADO----
Mañana como creo que dispondre de algo de tiempo intentaré hacer un ejemplo para recorrer un arbol binario (si no me equivoco un arbol binario en si seria lo mas parecido a una jerarquia de nodos en javascript DOM, solo que cada nodo como maximo debe tener 2 nodos (hojas) y ambas ramas deben tener el mismo numero de elementos (para que no se descompensen como si de una balanza se tratase ¿correcto?.

----EDITADO2-----
En la wikipedia hay mas datos e incluso código en c de ejemplo

Citar

solo que cada nodo como maximo debe tener 2 nodos (hojas) y ambas ramas deben tener el mismo numero de elementos (para que no se descompensen como si de una balanza se tratase ¿correcto?.

Y el hijo de la izquierda es menor que el padre, quien es menor que su hijo derecho.
Cuando haga el arbolcito de las narices lo colgaré en mi pagina de applets, aunque lo tendre que hacer con una clase grafica, porque sino el applet no mola mucho