Foro Conjuntos e Implementaciones, incluyendo hashing y árboles balanceados

No hay mucho más para seguir. Solo justificar que tras las rotaciones la altura del subárbol vuelve a ser la misma que antes de la inserción. Si eso ya está claro no hace falta leer el resto.

Supongamos que $u$ es el nodo más profundo que queda desequilibrado tras una inserción. Por simplicidad, con un abuso de lenguaje vamos a darle el mismo nombre al nodo y al subárbol que lo tiene como raíz. A los hijos izquierdo y derecho de $u$ les llamamos $\ell$ y $r$ respectivamente. Sin pérdida de generalidad supongamos que la inserción se hizo en el subárbol izquierdo de $u$. Como se va a producir un desequilibrio sabemos que antes de la inserción la altura de $\ell$ es mayor (uno más) que la de $r$. Entonces si la altura de $u$ es $h$ la de $\ell$ es $h-1$ y la de $r$ es $h-2$.

Como $\ell$ no es vacío tiene hijos, que sí pueden ser vacíos, y les llamamos $\ell \ell$ y $\ell r$. La altura de ambos tiene que ser la misma, $h-2$. Si no fuera así, como la inserción hace crecer la altura de $\ell$ tiene que hacer crecer la altura del más alto de sus subárboles y como consecuencia $\ell$ quedaría desequilibrado, lo que contradice la hipótesis original de que $u$ es el más profundo de los nodos que quedan desequilibrados.

Ahora hay que distinguir dos casos: la inserción se hace en $\ell \ell$ o en $\ell r$. La altura de ese subárbol va a pasar a ser $h-1$ y como consecuencia la de $\ell$ pasa a ser $h$ y la de $u$ pasa a ser $h+1$ y además queda desequilibrado. La altura de algunos ancestros de $u$ pudo aumentar y también quedar desequilibrados.

En este punto habría que hacer uno mismo un diagrama y luego verificar si coincide con esto.

• La inserción se hizo en $\ell \ell$. Tras la rotación la raíz del árbol pasa a ser $\ell$ (en lugar de $u$). Su subárbol izquierdo es $\ell \ell$ de altura $h-1$. Su subárbol derecho es $u$ que también va a tener altura $h-1$ porque sus dos subárboles, $\ell r$ y $r$ tienen altura $h-2$. Por lo tanto $\ell$, la nueva raíz del árbol, tiene altura $h$. Y la altura de los ancestros, si habían cambiado, también vuelven a ser la que tenían antes.
•  La inserción se hizo en $\ell r$. A los hijos de este nodo después de la inserción vamos a llamarlos $\ell r \ell$ y $\ell r r$. Veamos que la altura de uno de ellos es $h-2$ y la del otro es también $h-2$ o $h-3$. Si $\ell r$ era vacío, lo que implica que $h-2 = 0$, sus dos subárboles tras la inserción van a ser vacíos, de altura $h-2$. Si $\ell r$ no era vacío sus dos subárboles antes de la inserción tenían altura $h-3$ (tienen que ser iguales por la misma razón que tenían que ser iguales los subárboles de $\ell$). Como consecuencia uno para a  tener altura $h-2$ y el otro queda en $h-3$. Lo importante es que la altura de ambos no es mayor a $h-2$. Como consecuencia de las rotaciones la nueva raíz es $\ell r$. Su subárbol izquierdo es $\ell$ que tiene altura $h-1$ porque sus subárboles son $\ell \ell$ de altura $h-2$ y $\ell r \ell$ de altura $h-2$ o $h-3$.  Su subárbol derecho es $u$ que también tiene altura $h-1$ porque sus subárboles son $\ell r r$ de altura $h-2$ o $h-3$, y $r$ de altura $h-2$. Por lo tanto, también en este caso el subárbol que antes tenía a $u$ en la raíz vuelve a tener altura $h$.