Algoritmo de búsqueda para estructura de datos anidados

[Rhessus]

¡Hola a todos!
Hace tiempo quería pasarme por acá, pero no encontraba la excusa

Tuve que hacer un buscador para el caso de recibir un arreglo de objetos de esta clase:

Código [Seleccionar] Expandir

class Menu {
 id: int
 name: string
 url: string | null
 children: Menu[]
}

Como pueden notar, es multinivel. Y vale aclarar que sólo los objetos sin hijos (hojas, si los vemos como árboles) tendrán un valor distinto de null en el atributo url, el cual permite hacer la redirección.

El buscador muestra únicamente:
(1) Aquel objeto cuyo name cumpla con los valores ingresados
(2) Los hijos de (1), si los tiene
(3) El padre de (1) y sus ascendentes (abuelo, bisabuelo, etc.), hasta el primer nivel.

Mi solución fue muy engorrosa, por lo cual me gustaría saber si hay una forma simple (mas no sencilla) de hacerlo. Cuando tenga más tiempo repaso el código y comento qué hice.

¡Muchas gracias!

[Serapis]

...Mi solución fue muy engorrosa, por lo cual me gustaría saber si hay una forma simple  de hacerlo.

Si no pones algo de código/pseudocódigo/detalles del 'como lo hiciste'... aparte de meramente una estructura, cómo sabe nadie que se trata de una tarea (camuflada como un interés particular)???.

Cuando tenga más tiempo repaso el código y comento qué hice.

Ídem... cuando tengas ese tiempo para poner tu código o comentar qué hiciste, veremos de tener tiempo para responder a vuesa merced.

[Rhessus]

Lo que hice fue lo siguiente:

1- Recorrer el arreglo original (dataResponse[]) y crear dos nuevos arreglos:

a) levelsArray[][], en el que cada posición del mismo representa uno de los niveles, y colocar en cada una un arreglo con los objetos de dataResponse[] en el arreglo correspondiente a su nivel (si tuviese tres niveles, quedando algo como levelsArray = [[objeto, objeto], [objeto, objeto, objeto], [objeto, objeto]]); y

b) filteredArray[][], parecido al anterior, pero colocando en cada una de las posiciones un arreglo con los objetos de ese nivel que cumplen con el criterio de búsqueda. En caso de que no haya ninguno, la posición se completa con un arreglo vacío. En base al ejemplo anterior y si sólo el primer nivel tuviese un único objeto que cumple, quedaría filteredArray = [[objeto], [], []].

2- Hacer una copia de filteredArray[][], llamada menuArray[][].

3- Recorrer cada arreglo de menuArray[][] en sentido inverso y agregar a los hijos y al padre que no están en filteredArray[][] de cada objeto en el arreglo correspondiente a su nivel (tomándolos de levelsArray[][]). Según el ejemplo anterior, podría quedar menuArray = [[objeto], [objeto], []]. Para evitar traer hijos de más, el objeto del que se traerán su padre e hijos debe estar en filteredArray[][].

4- Recorrer de forma ascendente menuArray[][] y traer a toda la descendencia de los objetos que cumplen con la búsqueda y no fueron añadidos en el paso anterior. Para esto basta fijarse si dicho objeto está en filteredArray[][]. De esta forma, menuArray = [[objeto], [objeto], [objeto]].

5- Crear un arreglo de arreglos menuArrayNoNesting[][] donde los objetos de menuArray[][] pasan a tener el atributo children = [].

6- Recorrer menuArrayNoNesting[][] de manera inversa y anidar a los hijos en el atributo children de sus padres correspondientes, creando un arreglo menuFiltered[] que vuelve a tener la estructura de dataResponse[], pero con los objetos filtrados según los criterios especificados.

[Serapis]

Había puesto uan solución en forma de árbol, pero después de releerte como te viene un array, y necesitas hacer búsquedas es preferible tirar de una tabla hash (es más rápido en funcionamiento). Desconozco si estás forzado a algo predeterminado, pues no lo especificas).
Has dejado al aire ciertas cuestiones, como si puede modificarse los elementos de la clase, asumo que sí pues no lo acotas (aunque no lo llevo al terreno de árboles, porque quizás serían más cambios de los que te cabría pensar).

Supongamos que tu array ha de contener a lo sumo 100-200 elementos... no es mala idea proveer entonces un array de alrededor de 1000 elementos, donde podrán buscarse en tiempo 1 por hash.

Deájeme que simplifique el nombre del array a simplemente 'datos', e igualmente siempre me acomoda más usar paréntesis que llaves (son diferencias 'habituales' de la herencia entre Fortran y Algol que han trascendido hasta los lenguajes de hoy)...

Te llega el array, lo hasheas...

Código [Seleccionar] Expandir


entero constante PRIMO_X = 1021  
entero arrayHash(0 a PRIMO_X - 1)
entero espacioLibre
Menu datos()


// Cuando se recibe el array 'datos'... se invoca esta función.
funcion SetArray()
   Menu item
   
   borrarTablaHash
   por cada item en datos()      
       add(item.Name, k)
   siguiente
Fin funcion


Con esto ya tenemos todos los datos portados al arrayHash...
La búsqueda sería:
NOTA: No se provee solución al caso de una búsqueda sin haber recibido aún los datos, queda a tu esfuerzo dicho código, como para todas las comprobaciones 'obvias', además para no extenderse más de lo preciso.

Código [Seleccionar] Expandir


Menu = Funcion Buscar(string Nombre)
   entero j, k

   k = Hashing(Nombre)
   Si Existe(nombre, k) = TRUE
       devolver datos(k)
   sino
       devolver null // no encontrado
   fin si
fin funcion

Si existe (por referencia devuelve el índice donde se localiza en otro caso devuelve -1
Esta función típicamente es privada, la pública es 'buscar'.
Aquí se resuelven las colisiones... que es lo que hace la función un poco más compleja.

Código [Seleccionar] Expandir


buleano = funcion Existe(string Nombre,por referencia entero index)
   entero j, k

   k= index
   Hacer
       j = arrayHash(index)
       
       si (j => 0) // Si existe
           si (datos(j).Nombre = nombre)  // Comprobar si se trata de una colisión...
                index = j     // ojo... es devuelto por referencia.
                devolver TRUE
           sino  // una colisión se resuelve buscando el próximo hueco libre.
               index = ((index + 1) modulo PRIMO_X)
               si (index = k) devolver FALSE   // evitar bucle infinito...
           fin si
       sino
           devolver FALSE
       fin si            
   repetir  
fin funcion

El bucle es incondicional, pero dentro está totalmente controlado. No es un bucle infinito a lo sumo recorre 1 vez todo el array de la tabla hash si está mal programado.
NOTA: (es la única comprobación que te pongo, porque para un novato 'puede ser fácil', incurrir en tal error...)

Restan las funciones Add, Hashing, etc...

Código [Seleccionar] Expandir


buleano = funcion add(string name, entero index)
   entero j,k

   k = Hashing(name)
   si Existe(name, k) = FALSE
       arrayHash(k) = index
       espacioLibre -= 1

       devolver TRUE ó k     // la devoluión es opcional... según el diseño y si otros métodos precisan más info...
   sino
       devolver FALSE ó -1    
   fin si
fin funcion
Se supone que la tabla hash es de un tamaño mucho mayor que el array 'datos', y que por ello siempre encontrará un hueco. 'espacioLibre', sirve para controlar esto...
Queda a tu esfuerzo que si se añaden elementos dinámicamente y hay una alta ocupación (cae el rendimiento de añadir y buscar, elementos) redimensionar la tabla a un tamaño mayor haciendo un rehashing de todos los elementos.
Como todo esto es algo más elaborado, no es para 'novatos', cuando te adentres más en la programación, ya explorarás medidas para controlar tamaño de tabla hash, funciones mejor diseñadas para evitar colisiones y como resolverlas, etc...). Mientras, para un simple ejemplo esto es suficiente...

Código [Seleccionar] Expandir


// Borramos datos previos que constaran en la tabla hash
funcion borrarTabla
   entero k

   bucle para k desde 0 hasta PRIMO_X-1
       arrayHash(k) = -1
   siguiente  
   espacioLibre = PRIMO_X
fin funcion

entero = funcion Hashing(string nombre)
   entero j, k

   por cada par de caracteres (a,b) en nombre
       j += (a*b)  // se entiende que por 'a' y 'b' tomamos el valor del byte que supone cada char, superando el overflow del byte...
   siguiente

   Si tamaño(nombre) es impar
      j += (nombre.primercarater * nombre.ultimocaracter)
   fin si
 
   devolver (j modulo PRIMO_X)  // si se usa un solo valor debe ser primo, de otro modo las colisiones serán muy numerosas.
fin funcion

Y para algo básico eso es todo. Te toca pasar el pseudocódigo a código si quieres implementarlo o no si simplemente te basta con entenderlo (la práctica ayuda a la teoría).

Ahora algunas aclaraciones...
- La tabla hash puede a su vez ser una clase para que la lógica quede más clara, especialmente si se añaden más métodos... pués así encapsula toda su operatoria separada del resto, ahora mientras sean pocos métodos no enturbia que quede conjunto...
- Si la clase solo va a contener datos y no funcionalidad, quizás fuera preferible usar una estructura en vez de una clase (depende de otros factores, pero intenta examinar si es suficiente con una estructura).
- Si el campo 'Name', admite estar repetido, entonces el hashing no será aceptable. Para el hashing debe proveerse un campo de valor único (no repetible, en palabras claras), si no hay más remedio usa otro campo o bien concaténalo con URL, o incluso con 'id'... es decir con otro campo cuyo valor sea único.
- Sería conforme que tu clase contuviera un nodo 'parent' así tras la búsqueda exitosa, es fácil llegar hasta el padre x es meramente un bucle cuya funcionalidad es fácil de añadir... Ahora quizás dicho enlace esté señalado con el índice del campo 'Id'.... pero no hay suficientes explicaciones que lo aclaren.
- Si lo que te piden es un recorrido en profundidad (inorden, preorden, postorden), no me consta que quede aclarado, y he partido de la presunción de que tienes más código y bastante claro lo que te piden/quieres y has simplificado por la razón que sea. Con esos recorridos (no una búsqueda por nombre), conviene ceñirse entonces a un diseño de árbol en todo su concepto, en cambio si tienes libertad de elección esta solución suele ser la más eficaz, para búsqueda.
- Si el código es para tí (no un encargo para una empresa o cursillo) y si tu lengua materna no es el inglés, no veo motivo para que uses términos en inglés... (a mi me suena un poco pedante, pero es solo mi impresión otros opinarán distinto).
- Este pseudocódigo es mucho más eficiente que otras soluciones, si bien la función hash es bastante 'simple' y el valor del primo se ha elegido en base a la hipótesis de que tu array de datos no tendrá más de 200 elementos (el tamaño del array de la tabla hash debe mantener cierta premisa de proporción respecto de la cantidad máxima de elementos, si no es definible entonces debe ser un tamaño dinámico (que es algo más avanzado)...

Si tienes alguna duda, pregunta, pero procura ser claro, sin ausmir que uno tiene acceso a la especificación completa de lo que te piden, si no al final uno no hace más que asumir tal o cual cosa, donde la duda acecha.

...creo que se me queda alguna cosa en el tintero de las que tenía que señalarte, pero (mientas) al escribir al vuelo, es normal que luego unas se te vayan de la cabeza...