Medio parcial-2

Construccion de BST y recorridos en preorden, inorden y postorden

Fuente: Material del curso — Arboles.pdf (Ejemplo 1, Seccion 5.1)

bstarboles-binariosrecorridospreordeninordenpostordeninsercion

Enunciado

Considere la siguiente secuencia de valores a insertar en un arbol binario de busqueda (BST) inicialmente vacio:

$[45, 25, 65, 15, 35, 55, 75, 10, 20, 30]$

(a) Construya el BST insertando los valores en el orden dado. Dibuje el arbol resultante indicando claramente la raiz, los subarboles izquierdo y derecho de cada nodo.

(b) Realice los tres recorridos del arbol y escriba la secuencia de nodos visitados:

Preorden (raiz, izquierdo, derecho)
Inorden (izquierdo, raiz, derecho)
Postorden (izquierdo, derecho, raiz)

(c) Verifique que el recorrido inorden produce los elementos en orden ascendente. Explique por que esta propiedad siempre se cumple en un BST.

(d) Cual es la altura del arbol resultante? Cual seria la altura en el mejor caso (arbol perfectamente balanceado) para 10 nodos? Utilice la formula $h_{min} = \lfloor \log_2 n \rfloor$ .

(e) Si los valores se insertaran en orden ascendente $[10, 15, 20, 25, 30, 35, 45, 55, 65, 75]$ , como seria la forma del arbol? Cual seria su altura y por que esto es problematico para la eficiencia de las operaciones?

(f) Elimine el nodo con valor 25 del arbol original (construido en el punto a). Explique el procedimiento considerando que el nodo tiene dos hijos, y dibuje el arbol resultante.

Solución rápida — la idea clave sin formalismo

La idea en simple

Construir el BST. Regla unica: menor va a la izquierda, mayor a la derecha, desde la raiz hacia abajo. Empezando por 45 y siguiendo la lista queda:

            45
          /    \
        25      65
       /  \    /  \
     15    35 55   75
    /  \   /
  10   20 30

Los tres recorridos solo cambian cuando visitas la raiz:

Preorden (raiz primero): $45,25,15,10,20,35,30,65,55,75$
Inorden (raiz en medio): $10,15,20,25,30,35,45,55,65,75$
Postorden (raiz al final): $10,20,15,30,35,25,55,75,65,45$

El inorden sale ordenado porque en un BST todo lo de la izquierda es menor y todo lo de la derecha es mayor: al visitar izquierda -> nodo -> derecha, los numeros salen de menor a mayor solos.

Altura. El camino mas largo baja 3 pasos, y para 10 nodos lo minimo posible es $\lfloor \log_2 10 \rfloor = 3$ : este arbol quedo perfecto.

Cuidado con insertar en orden. Si metes $10,15,20,\dots,75$ ya ordenados, todo se va a la derecha y el arbol se vuelve una fila de altura 9. Buscar deja de ser $O(\log n)$ y pasa a $O(n)$ . Por eso existen los arboles que se auto-balancean (AVL).

Borrar el 25 (que tiene dos hijos). No lo quitas de golpe: lo reemplazas por el siguiente en orden (el mas pequeno de su lado derecho, que es 30) y borras ese 30. El 30 sube al lugar del 25 y el arbol sigue siendo valido.

Solución formal — lista para entregar en un parcial

Solucion formal

(a) BST tras insertar $[45,25,65,15,35,55,75,10,20,30]$ :

            45
          /    \
        25      65
       /  \    /  \
     15    35 55   75
    /  \   /
  10   20 30

(b) Recorridos:

\begin{aligned} \text{Preorden} &: 45,25,15,10,20,35,30,65,55,75\\ \text{Inorden} &: 10,15,20,25,30,35,45,55,65,75\\ \text{Postorden} &: 10,20,15,30,35,25,55,75,65,45 \end{aligned}

(c) Propiedad BST: $\forall x,\ \text{claves}(izq(x)) < x < \text{claves}(der(x))$ . El inorden ejecuta $\text{inorden}(izq)\,;\,x\,;\,\text{inorden}(der)$ . Por induccion sobre la altura, cada subllamada devuelve su subarbol ordenado; concatenar (menores) $< x <$ (mayores) mantiene el orden. Luego el inorden es ascendente. $\blacksquare$

(d) Altura (en aristas) $= 3$ por el camino $45\to25\to15\to10$ . Como $h_{\min} = \lfloor \log_2 10 \rfloor = 3$ , el arbol esta en altura minima (balanceado).

(e) Insercion ascendente $\Rightarrow$ cada clave baja siempre a la derecha $\Rightarrow$ arbol degenerado (cadena) de altura $n-1 = 9$ . Las operaciones pasan de $O(\log n)$ a $O(n)$ ; motiva los arboles balanceados (AVL, rojo-negro).

(f) Eliminar $25$ (dos hijos): se sustituye por su sucesor inorden $= \min(\text{subarbol derecho}) = 30$ , y se elimina el $30$ original (hoja). Resultado:

            45
          /    \
        30      65
       /  \    /  \
     15    35 55   75
    /  \
  10   20

$\blacksquare$

Explicación completa — paso a paso, con visualizaciones

Solucion

(a) Construccion del BST

Insertamos $[45, 25, 65, 15, 35, 55, 75, 10, 20, 30]$ en un BST vacio. La regla de insercion: desde la raiz, si el valor es menor se baja a la izquierda, si es mayor a la derecha, hasta encontrar un hueco.

Nodo* insertar(Nodo* raiz, int x) {
  if (raiz == nullptr) return new Nodo{x, nullptr, nullptr};
  if (x < raiz->dato) raiz->izq = insertar(raiz->izq, x);
  else                raiz->der = insertar(raiz->der, x);
  return raiz;
}

Traza de las inserciones que definen la forma:

45 es la raiz.
25 < 45 -> izquierda de 45. 65 > 45 -> derecha de 45.
15 < 45 < 25 -> izquierda de 25. 35: 35 < 45, 35 > 25 -> derecha de 25.
55: >45, <65 -> izquierda de 65. 75: >45, >65 -> derecha de 65.
10: <45,<25,<15 -> izquierda de 15. 20: <45,<25,>15 -> derecha de 15.
30: <45,>25,<35 -> izquierda de 35.

Arbol resultante:

            45
          /    \
        25      65
       /  \    /  \
     15    35 55   75
    /  \   /
  10   20 30

(b) Recorridos

void preorden(Nodo* n)  { if(!n) return; visitar(n); preorden(n->izq); preorden(n->der); }
void inorden(Nodo* n)   { if(!n) return; inorden(n->izq); visitar(n); inorden(n->der); }
void postorden(Nodo* n) { if(!n) return; postorden(n->izq); postorden(n->der); visitar(n); }

Preorden (raiz, izq, der): $45,\ 25,\ 15,\ 10,\ 20,\ 35,\ 30,\ 65,\ 55,\ 75$
Inorden (izq, raiz, der): $10,\ 15,\ 20,\ 25,\ 30,\ 35,\ 45,\ 55,\ 65,\ 75$
Postorden (izq, der, raiz): $10,\ 20,\ 15,\ 30,\ 35,\ 25,\ 55,\ 75,\ 65,\ 45$

(c) Por que el inorden sale ordenado

La propiedad de BST dice que, para todo nodo $x$ , todas las claves del subarbol izquierdo son $< x$ y todas las del subarbol derecho son $> x$ . El recorrido inorden visita, en este orden exacto: (todo el subarbol izquierdo) $\to$ (el nodo) $\to$ (todo el subarbol derecho).

Por induccion sobre la altura: si inorden ordena correctamente cada subarbol (hipotesis), entonces produce primero todas las claves menores que $x$ en orden, luego $x$ , y luego todas las mayores que $x$ en orden. El resultado global queda ordenado ascendentemente. Por eso el inorden de un BST siempre entrega los elementos de menor a mayor.

(d) Altura del arbol

Usando la convencion de altura en aristas (un nodo solo tiene altura 0), el camino mas largo es $45\to25\to15\to10$ (o $\to25\to35\to30$ ): altura $= 3$ (equivalente a 4 niveles).

La altura minima para $n = 10$ nodos es

$h_{\min} = \lfloor \log_2 n \rfloor = \lfloor \log_2 10 \rfloor = \lfloor 3.32 \rfloor = 3.$

El arbol obtenido ya alcanza la altura minima ( $3 = h_{\min}$ ): esta bien balanceado gracias al orden afortunado de las inserciones.

(e) Insercion en orden ascendente

Si se insertan $[10, 15, 20, 25, 30, 35, 45, 55, 65, 75]$ , cada valor nuevo es mayor que todos los anteriores, asi que siempre baja a la derecha. El arbol degenera en una cadena inclinada a la derecha (una lista enlazada disfrazada):

Su altura es $n - 1 = 9$ . Esto es problematico: la busqueda, la insercion y la eliminacion pasan de $O(\log n)$ (arbol balanceado) a $O(n)$ (recorrido lineal). Se pierde por completo la ventaja del BST. Este es justamente el motivo por el que existen los arboles auto-balanceados (AVL, rojo-negro), que garantizan altura $O(\log n)$ sin importar el orden de insercion.

(f) Eliminar el nodo 25 (dos hijos)

El nodo $25$ tiene dos hijos (subarbol izquierdo con raiz 15 y derecho con raiz 35). No se puede simplemente quitar. El procedimiento estandar:

Buscar el sucesor inorden de $25$ : el minimo del subarbol derecho. El subarbol derecho tiene raiz $35$ y su hijo izquierdo es $30$ ; el minimo (mas a la izquierda) es $30$ .
Copiar el valor del sucesor ( $30$ ) en el nodo a eliminar (reemplaza al $25$ ).
Eliminar el nodo original $30$ , que ahora es una hoja (o tiene a lo sumo un hijo derecho), caso facil.

El sucesor inorden siempre tiene a lo sumo un hijo, por eso este truco convierte el caso dificil (dos hijos) en uno sencillo. Arbol resultante:

            45
          /    \
        30      65
       /  \    /  \
     15    35 55   75
    /  \
  10   20

Se conserva la propiedad de BST: bajo el $30$ , el subarbol izquierdo $\{10,15,20\}$ es menor que $30$ y el derecho $\{35\}$ es mayor. (Alternativamente se pudo usar el predecesor inorden — el maximo del subarbol izquierdo, que es $20$ — con un resultado igualmente valido.)