por - imprimir arbol binario java

¿Cuáles son las complejidades de tiempo de varias estructuras de datos? (1)

Estoy tratando de enumerar las complejidades de tiempo de las operaciones de estructuras de datos comunes como Arrays, Árbol de búsqueda binaria, Heap, Lista enlazada, etc. y especialmente me refiero a Java. Son muy comunes, pero creo que algunos de nosotros no estamos 100% seguros sobre la respuesta exacta. Cualquier ayuda, especialmente referencias, es muy apreciada.

Por ejemplo, para la lista enlazada individualmente: cambiar un elemento interno es O (1). ¿Cómo puedes hacerlo? TIENE que buscar el elemento antes de cambiarlo. Además, para el Vector, agregar un elemento interno se da como O (n). ¿Pero por qué no podemos hacerlo en tiempo constante amortizado usando el índice? Por favor corrígeme si me falta algo.

Estoy publicando mis hallazgos / suposiciones como la primera respuesta.

Arrays

Establecer, verificar elemento en un índice en particular: O (1)
Búsqueda : O (n) si la matriz no está ordenada y O (log n) si la matriz está ordenada y se utiliza algo así como una búsqueda binaria,
Como lo señaló Aivean , no hay ninguna operación de Delete disponible en Arrays. Podemos eliminar simbólicamente un elemento estableciéndolo en algún valor específico, por ejemplo -1, 0, etc. según nuestros requisitos
Del mismo modo, Insert para matrices es básicamente Set como se menciona al principio

Lista de arreglo:

Agregar : Amortizado O (1)
Eliminar : O (n)
Contiene : O (n)
Tamaño : O (1)

Lista enlazada:

Insertar : O (1) , si se hace en la cabecera, O (n) si en otro lugar, ya que tenemos que llegar a esa posición al viajar linealmente la lista enlazada.
Eliminando : O (1) , si se hace en la cabecera, O (n) si en otro lugar, ya que tenemos que llegar a esa posición al viajar linealmente la lista enlazada.
Buscando : O (n)

Lista doblemente enlazada:

Insertar : O (1) , si se hace en la cabeza o la cola, O (n) si en cualquier otro lugar, ya que tenemos que llegar a esa posición al viajar linealmente la lista enlazada.
Eliminando : O (1) , si se hace en la cabecera o en la cola, O (n) si en algún otro lugar, ya que tenemos que alcanzar esa posición al viajar linealmente la lista enlazada.
Buscando : O (n)

Apilar:

Empuje : O (1)
Pop : O (1)
Superior : O (1)
Buscar (Algo parecido a la búsqueda, como una operación especial): O (n) (supongo)

Queue / Deque / Circular Queue:

Insertar : O (1)
Eliminar : O (1)
Tamaño : O (1)

Árbol de búsqueda binaria:

Insertar, eliminar y buscar : Caso promedio: O (log n) , Peor caso: O (n)

Árbol Rojo-Negro:

Insertar, eliminar y buscar : Caso promedio: O (log n) , Peor caso: O (log n)

Heap / PriorityQueue (min / max):

Encontrar Min / Buscar Max : O (1)
Insertar : O (log n)
Eliminar Mín. / Eliminar Máx . : O (log n)
Extraer Min / Extract Max : O (log n)
Buscar, Eliminar (si se proporciona): O (n) , tendremos que escanear todos los elementos ya que no están ordenados como BST

HashMap / Hashtable / HashSet:

Insertar / Borrar : O (1) amortizado
Re-tamaño / hash : O (n)
Contiene : O (1)