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.
insertar que se le aplicaSiete 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.
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.
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.
d, nodo por nodoc
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.
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?
val d = c insertar 7, ¿qué responde c.pertenece(7)?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.