En general, una estructura de “búsqueda” funciona en un solo campo dentro de los nodos. Suele denominarse campo clave y se utiliza para evaluar la igualdad y la clasificación. No solo se limita a los árboles de búsqueda binarios, sino a todas las estructuras en las que desea encontrar un nodo en particular según un valor específico de uno de sus campos.
Dependiendo de la biblioteca, debería poder redefinir una función de comparación de modo que solo funcione en ese campo particular de cada nodo, ignorando los valores en los otros campos. Por ejemplo, supongamos que está utilizando la clase SortedSet (T) (System.Collections.Generic) en DotNet. Esa clase usa un árbol Rojo-Negro (una forma de árbol de búsqueda binaria autoequilibrado) para almacenar los nodos.
Tenga en cuenta que uno de sus constructores acepta un argumento IComparer. Esto le permite dar a la estructura una función de comparación personalizada. Dentro de esto, puede cambiar qué parte de cada nodo se compara entre sí cuando la estructura intenta encontrar la posición de cada nodo.
- ¿Cuál es el algoritmo para expulsar a los pasajeros del avión si está sobrevendido?
- ¿Cuál es el mejor camino para dominar el aprendizaje profundo?
- ¿Cuál sería el algoritmo para encontrar subárboles duplicados en un árbol binario?
- Cómo encontrar diferentes permutaciones de pila
- ¿Cuándo se usaría un algoritmo gráfico?
Alternativamente, podría implementar la interfaz IComparable en el tipo que está agregando al conjunto. Es decir, escribiría un método CompareTo para la clase / estructura que desea colocar dentro del conjunto. Similar se aplica a la definición de una clase de Comparer personalizada separada.
Varias otras bibliotecas (y otros entornos / idiomas) tienen formas similares de definir comparaciones personalizadas. Pero el principio es el mismo.
Otro tipo de estructura similar es una clase SortedDictionary (TKey, TValue) (System.Collections.Generic). Sin embargo, en este caso, genera su propio nodo combinando un valor y una clave en un tipo de par clave-valor y luego usándolo para insertarlo en la estructura de árbol de respaldo. Eso ya tiene su propio método CompareTo implementado. Y eso solo usa la clave para comparar entre dos nodos. De esta forma, podría extraer un nodo dependiendo del valor de su clave. Si bien usarlo en la forma en que el valor ya tiene un campo que define la clave significa que está duplicando el valor contenido en esa clave, sigue siendo bastante útil y muy simple de usar.
La razón por la que no hay una estructura implementada en la que pueda buscar un nodo especificando uno donde solo haya ingresado su clave es porque hace que la estructura sea menos general. Por ejemplo, si quisiera tener algo como un método GetValue en un SortedSet, necesitaría extender la clase SortedSet. Y necesitaría definir que su tipo de nodo debe implementar al menos una función de comparación. La idea del Diccionario simplemente hace que esto sea innecesario al comprometer el uso de la memoria.
Si quiere decir que desea buscar en cualquiera de los campos dentro del nodo, deberá crear una estructura de árbol para cada uno de los campos. Duplicar los datos (o al menos la referencia a ellos) en cada árbol, con un comparador para trabajar solo en el campo relevante. De nuevo, no es algo que sucede generalmente. Y de nuevo, mucho más simple de implementar usando la idea del diccionario, aunque comprometiendo el uso de la memoria.
Una vez más, otras bibliotecas y / o entornos pueden tener estructuras incorporadas similares que hacen más o menos lo mismo.
