¿Complejidad computacional de las operaciones TreeSet en Java?

Question

Estoy tratando de aclarar algunas cosas con respecto a la complejidad en algunas de las operaciones de TreeSet. En el javadoc que dice:

"Esta aplicación proporciona registro garantizado (n) Coste de tiempo para los operaciones básicas (añadir, eliminar y contiene)."

Hasta ahora todo bien. Mi pregunta es lo que sucede en addAll(), removeAll(), etc. Aquí el Javadoc para Set dice:

"Si la colección especificada es también un conjunto , la operación addAll efectivamente modifica este conjunto de manera que su el valor es la unión de los dos conjuntos ".

¿Está simplemente explicando el resultado lógico de la operación o está dando una pista sobre la complejidad? Quiero decir, si los dos conjuntos están representados por, por ejemplo, árboles rojo-negro sería mejor unirse a los árboles que "agregar" cada elemento de uno a otro.

En cualquier caso, ¿hay alguna manera de combinar dos TreeSets en uno con complejidad O (logn)?

Gracias de antemano. :-)

Answer 1

Se podía imaginar lo que sería posible optimizar los casos especiales a O(log n), pero el peor de los casos tiene que ser donde m y n son el número de elementos en cada árbol.

Editar:

http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm

describe un algoritmo caso especial que puede unirse a los árboles en O(log(m + n)) pero tenga en cuenta la restricción: todos los miembros de S1 debe ser inferior a todos los miembros de S2. Esto es lo que quise decir con optimizaciones especiales para casos especiales.

Answer 2

De acuerdo con este post blog:
http://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html
es O (n log n). Debido a que la documentación no da pistas sobre la complejidad, es posible que desee escribir su propio algoritmo si el rendimiento es crítico para usted.

Answer 3

Al observar el origen de java para TreeSet, parece que si la colección pasada es un SortedSet entonces utiliza un algoritmo de tiempo O (n). De lo contrario, llama a super.addAll, que supongo que dará como resultado O (n logn).

EDITAR - supongo que leo el código demasiado rápido, TreeSet sólo puede utilizar el O (n) algoritmo de si se trata de la correlación de respaldo está vacía

Answer 4

No es posible llevar a cabo la fusión de árboles o unirse a conjuntos como en Disjoint- establecer estructuras de datos porque no se sabe si los elementos en los 2 árboles son disjuntos. Dado que las estructuras de datos tienen conocimiento sobre el contenido en otros árboles, es necesario verificar si existe un elemento en el otro árbol antes de agregarlo o, al menos, intentar agregarlo a otro árbol y abortar agregarlo si lo encuentra en la manera. Entonces, debería ser O (MlogN)