Trabajo voluntario de estructura de datos. Arbol ABOE


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

1-Base

2) Marcamos el nodo a borrar: [Nodo 7]

2-Borrar el 7

3) Borramos el nodo

3-7 Borrado4) Al estar el árbol equilibrado, marcamos el siguiente nodo a borrar

4-Borrar el 85) Y ahora lo borramos

4-8 Borrado5) Como el árbol sigue equilibrado, marcamos el siguiente nodo a borrar

5-Borrar 116) 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)

6-11 Borrado7) 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)

7-Equilibrado8) Una vez equilibrado, marcamos el siguiente a borrar

8-Borrar 109) En este caso, al borrarse el 10, sube el nodo 6.(el más grande de los pequeños).

9-10 Borrado10) El árbol ha vuelto a quedar desequilibrado por la derecha, por lo que se re-equilibra con una rotación doble DI (derecha-izquierda)

10-Equilibrado11) Ahora, una vez equilibrado de nuevo marcamos el siguiente nodo a borrar

11-Borrar1512) 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

12-15Borrado13) 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

13-Borrar1314) 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.

14-13Borrado15) Una vez más como el árbol esta equilibrado (aunque no lo parezca), marcamos el siguiente a borrar.

15-Borrar1216) Otra vez la raíz (en serio, que manía con la raíz, XD). Sube el 6.

16-12Borrado17) Ahora si está des-equilibrado, por lo que hacemos una rotación simple DD (derecha – derecha) para re-equilibrar el árbol

17-Equilibrado18) Marcamos el siguiente nodo a borrar:

18-Borrar2119) Realizamos el borrado y…

19-21Borrado20) Nos queda un árbol degenerado, es decir, una lista. Por lo que utilizamos una rotación doble ID (izquierda – derecha) para resolver el problema.

20-EquilibradoY 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.

Anuncios

Aquí puedes dejar tus comentarios.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s