java - funciona - Devolver un elemento desde un TreeSet usando búsqueda binaria

treeset java como funciona

Question

En TreeSet hay un método llamado contiene que devuelve verdadero si un elemento está en el conjunto. Supongo que este método utiliza la búsqueda binaria y no itera a través de todos los elementos en orden ascendente. ¿Estoy en lo cierto?

Tengo un TreeSet que contiene objetos de una clase que usa dos variables de instancia de String para distinguirlo de otros objetos de la misma clase. Quiero poder crear un método que busque en TreeSet comparando los objetos dos variables de instancia (utilizando los métodos get, por supuesto) con otras dos variables de String y, si son iguales, devuelva el elemento. Si las variables de instancia son menores que ir al primer elemento en el subárbol correcto o si son de mayor búsqueda en el subárbol izquierdo, etc. ¿Hay alguna manera de hacerlo?

Sé que podría simplemente almacenar los objetos en una ArrayList y usar la búsqueda binaria para encontrar el objeto, pero esto no sería tan rápido como buscar el TreeSet.

Answer 1

Debe implementar Comparable en su objeto o crear una clase Comparator separada que pase al momento en que se construye TreeSet. Esto le permite intercalar su lógica personalizada de comparación de entradas y dejar que TreeSet haga su actividad optimizada de búsqueda / tienda.

Answer 2

En lugar de usar un TreeSet , puede almacenar sus objetos en un TreeMap<Foo, Foo> o TreeMap<FooKey, Foo> (si no puede crear fácilmente un nuevo Foo real cada vez que quiera buscar). Set no están destinados a la búsqueda.

Para el ejemplo FooKey , FooKey sería una clase inmutable simple que solo contiene las dos String y es Comparable . Encontrar el valor de Foo para dos String sería una simple cuestión de treeMap.get(new FooKey(firstString, secondString)) . Por supuesto, esto utiliza el recorrido del árbol en el que desea encontrar el valor.

Answer 3

Obtuviste la respuesta sobre el uso de comparables / comparadores, pero pensé que agregaría que tienes razón en que contiene () hace una búsqueda binaria, aunque no deberías necesitar conocer esos detalles

Answer 4

Una cosa que me preguntaba es por qué quieres buscar en un conjunto ordenado. Si desea poder iterar en orden y buscar rápidamente, puede beneficiarse al almacenar sus objetos en dos estructuras de datos separadas. Uno como su SortedSet<Foo> y luego también un HashMap<FooKey,Foo> similar a lo que ColinD mencionó. Luego, obtiene búsquedas de tiempo constante en lugar de registrar (n) en TreeMap. Tiene una penalización por escritura de tener que escribir en ambas estructuras y una penalización de recursos de memoria por tener las dos estructuras de datos, pero ha optimizado completamente su acceso a los datos.

Además, si los recursos de la memoria están restringidos, y sus cadenas son realmente lo que diferencian a los objetos, entonces puede implementar hashcode() y equals() en su objeto Foo y luego simplemente usarlos como la clave y el valor (como HashMap<Foo,Foo> . La advertencia es que tienes que construir un Foo para llamar al getter.

Answer 5

set.tailSet(obj).first();

hace lo que quieres