← Volver a los ejercicios

compartir: qué construye una inserción

Los tres campos de un NoVacio se fijan al construirlo y después nadie los cambia, así que insertar entrega un árbol distinto en lugar de modificar el que recibe. Prediga cuántos nodos cuesta eso y cuántos quedan como estaban, y después mire el árbol resultante.

1. El árbol y el insertar que se le aplica

val c = Vacio.insertar(10).insertar(8).insertar(15)
.insertar(6).insertar(9).insertar(13)
.insertar(16)

Siete nodos NoVacio, en orden List(6, 8, 9, 10, 13, 15, 16). Los cuadrados son el object Vacio, uno solo para todos los subárboles vacíos.

1object Vacio extends ConjEnt {
2 def insertar(x: Int): ConjEnt =
3 new NoVacio(x, Vacio, Vacio)
4}
5
6class NoVacio(elem: Int, izq: ConjEnt, der: ConjEnt)
7 extends ConjEnt {
8
9 def insertar(x: Int): ConjEnt =
10 if (x < elem)
11 new NoVacio(elem, izq insertar x, der)
12 else if (x > elem)
13 new NoVacio(elem, izq, der insertar x)
14 else this
15}

En la línea 11 el tercer argumento es der: el subárbol derecho entra al nodo nuevo tal como está. En la línea 13 pasa lo mismo con izq.

2. Prediga las dos cantidades para val d = c insertar 7

¿Cuántos new NoVacio se evalúan?

De los nodos NoVacio del árbol d, ¿cuántos son los mismos objetos que ya estaban en c?

El 7 no está en c, y el sitio donde entra sale de las mismas comparaciones de pertenece.

3. El árbol d, nodo por nodo

construido por esta inserción el mismo objeto que ya estaba en c

Las construcciones, en el orden en que ocurren:

    Los nodos azules son exactamente el camino de la raíz al sitio del 7, más el 7. Los verdes cuelgan de ese camino y entraron sin tocarse: el subárbol con el 9, y el subárbol con 15, 13 y 16 completo.

    4. Ahora con un elemento que ya está

    La tercera rama de insertar dice else this: cuando el elemento coincide, devuelve el mismo nodo. ¿Cuántos new NoVacio se evalúan al calcular c insertar 9, con el 9 ya en el árbol?

    5. Después de val d = c insertar 7, ¿qué responde c.pertenece(7)?

    6. Lo que se lleva de aquí

    Una inserción no recorre el árbol para copiarlo: construye un nodo por cada paso del camino de la raíz al sitio donde entra el elemento. El subárbol que no cambia entra al nodo nuevo por donde está. En el árbol de siete nodos, insertar el 7 cuesta cuatro construcciones y deja cuatro nodos compartidos. En un árbol con mil elementos y las comparaciones repartidas, el camino tiene alrededor de diez nodos, y es eso lo que cuesta la inserción.

    Compartir nodos entre dos árboles es seguro porque nadie los escribe. Si NoVacio permitiera cambiar der después de construido, el subárbol con 15, 13 y 16 estaría en los dos árboles y un cambio hecho desde d le aparecería a c sin que nadie lo pidiera. Con los campos fijos, c y d conviven: el primero responde sobre siete elementos, el segundo sobre ocho, y el que tenga el nombre viejo sigue sirviendo para lo que ya se había calculado con él.

    El caso del elemento repetido muestra hasta dónde llega el else this: ahorra el nodo que coincide y nada más, porque las llamadas de arriba ya habían entrado a una rama con un new NoVacio en el cuerpo. El resultado tiene los mismos siete elementos que c y comparte con él cinco nodos, pero su raíz es otro objeto.