← Volver a los ejercicios

despacho: qué pertenece corre en cada nodo

La clase abstracta declara pertenece y no le escribe cuerpo. Los cuerpos están en Vacio y en NoVacio, y la llamada izq pertenece x está escrita una sola vez. Llene una fila por cada nodo que recibe una llamada: la última columna pide cuál de los dos cuerpos corre ahí.

1. La jerarquía

1abstract class ConjEnt {
2 def insertar(x: Int): ConjEnt
3 def pertenece(x: Int): Boolean
4}
5
6object Vacio extends ConjEnt {
7 def pertenece(x: Int): Boolean = false
8 def insertar(x: Int): ConjEnt =
9 new NoVacio(x, Vacio, Vacio)
10}
11
12class NoVacio(elem: Int, izq: ConjEnt, der: ConjEnt)
13 extends ConjEnt {
14
15 def pertenece(x: Int): Boolean =
16 if (x < elem) izq pertenece x
17 else if (x > elem) der pertenece x
18 else true
19
20 def insertar(x: Int): ConjEnt =
21 if (x < elem)
22 new NoVacio(elem, izq insertar x, der)
23 else if (x > elem)
24 new NoVacio(elem, izq, der insertar x)
25 else this
26}

El árbol de los dos recorridos se construye así, y los cuadrados grises del dibujo son el object Vacio:

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

Recorrido en orden: List(6, 8, 9, 10, 13, 15, 16). En izq pertenece x el tipo que el compilador conoce para izq es ConjEnt, y ConjEnt no tiene cuerpo para pertenece.

2. Llene la tabla de los dos recorridos

Una fila por nodo que recibe una llamada. La fila se cierra cuando las cuatro casillas coinciden, y entonces aparece la siguiente; cuántas filas hay es parte de lo que hay que averiguar. La columna qué pertenece corre se responde mirando qué objeto recibió la llamada, no cómo está escrita.

3. En izq pertenece x, ¿qué decide cuál de los dos cuerpos corre?

4. Lo que se lleva de aquí

ConjEnt declara pertenece y no lo implementa, así que la expresión izq pertenece x no queda resuelta al escribirla. Lo que corre sale del objeto que recibe la llamada: los nodos con elemento son NoVacio y entran a la cadena de comparaciones; el subárbol vacío es el object Vacio y su cuerpo es false. En c.pertenece(7) el mismo texto de una línea corrió cuatro veces y sirvió dos cuerpos distintos.

Los dos recorridos terminan de formas distintas, y esa es la diferencia entre las dos respuestas. pertenece(9) se detiene en la tercera rama del if/else, con 9 == 9, y devuelve true sin bajar más. pertenece(7) no encuentra con qué comparar: baja hasta un subárbol vacío, y ahí el false de Vacio es el que cierra la búsqueda. Un conjunto sin el object Vacio necesitaría preguntar en cada nodo si el subárbol existe antes de bajar.

El dibujo marca los nodos visitados: tres en cada recorrido sobre un árbol de siete. La altura del árbol es lo que acota ese número, no la cantidad de elementos, y de ahí sale el interés de mantener los menores a la izquierda y los mayores a la derecha.