Inserta, en el orden especificado, los siguientes enteros en un árbol (no hay que aplicar rotaciones, resultar á un ABOE): 11, 8, 7, 6, 10, 15, 13, 12, 20, 18 y 21. Borrar los siguientes enteros en el orden especificado, aplicando las rotaciones cuando corresponda: 7, 8, 11, 10, 15, 13, 12 y 21
1) Realizamos las inserciones, y resulta el siguiente árbol
2) Marcamos el nodo a borrar: [Nodo 7]
3) Borramos el nodo
4) Al estar el árbol equilibrado, marcamos el siguiente nodo a borrar
5) Y ahora lo borramos
5) Como el árbol sigue equilibrado, marcamos el siguiente nodo a borrar
6) El nodo a borrar es la raíz, por lo que la nueva raíz va a ser el más grande de los pequeños, es decir, el 10. (Se puede elegir como nueva raíz el más grande de los pequeños o el más pequeño de los grandes, en nuestro grafo, el 10 o el 12)
7) En este caso, el árbol está desequilibrado por la derecha, por lo que vamos a re-equilibrarlo con una rotación simple DD (derecha-derecha)
8) Una vez equilibrado, marcamos el siguiente a borrar
9) En este caso, al borrarse el 10, sube el nodo 6.(el más grande de los pequeños).
10) El árbol ha vuelto a quedar desequilibrado por la derecha, por lo que se re-equilibra con una rotación doble DI (derecha-izquierda)
11) Ahora, una vez equilibrado de nuevo marcamos el siguiente nodo a borrar
12) Al ser otra vez la raíz la que será borrada, pasa a ser la raíz el más grande de los pequeños
13) Aunque parece que el árbol esta des-equilibrado, en realizad si se analizan todos los nodos desde las hojas no lo esta, por lo que marcamos el siguiente nodo a borrar
14) Una vez más la raíz vuelve a ser borrada. En este caso, el más grande de los pequeños es el 12. Por ello, promocionamos dicho nodo como nodo raíz.
15) Una vez más como el árbol esta equilibrado (aunque no lo parezca), marcamos el siguiente a borrar.
16) Otra vez la raíz (en serio, que manía con la raíz, XD). Sube el 6.
17) Ahora si está des-equilibrado, por lo que hacemos una rotación simple DD (derecha – derecha) para re-equilibrar el árbol
18) Marcamos el siguiente nodo a borrar:
19) Realizamos el borrado y…
20) Nos queda un árbol degenerado, es decir, una lista. Por lo que utilizamos una rotación doble ID (izquierda – derecha) para resolver el problema.
Y hemos terminado con el ejercicio.
El ejercicio que hemos propuesto de borrado es:
Dadas las siguientes inserciones (20, 5, 30, 2, 8, 21, 35, 6, 18, 32). Crea el árbol ordenado equilibrado resultante y borra los siguientes nodos: 20, 2, 21, 18, 8, 6, 35.
Viviendo entre Pingüinos 