algorithm - simple - ¿Cómo crear un Árbol AVL desde ArrayList de valores en O(n) tiempo?
rotacion simple a la izquierda (2)
La inserción es O(logn) , tan cierto, nadie puede hacer mejor que O(nlogn) al insertar. Realmente, no deberías insertar en el árbol AVL. Deberías simplemente crear el árbol. Cree todos los nodos y elija los valores de la matriz mientras construye nuevos nodos. No encuentre / busque el valor que necesita, simplemente tómelo, la matriz está ordenada.
Dada una lista que contiene 5 elementos y está ordenada, por ejemplo [1,2,3,4,5] , ¿cuál sería la raíz del árbol? ¿Qué tal para 7 elementos? 10? ...?
Después de obtener la raíz, ¿cuál sería la raíz del subárbol izquierdo? ¿Cuál es la lista para mirar? ¿Qué parte de la lista debe almacenar en el subárbol izquierdo?
Eso es todo.
Mi tarea es crear un Árbol AVL a partir de una lista ordenada de valores en O (n) tiempo donde n es el número de valores
He estado trabajando en esto pero no puedo obtener el tiempo de O (n), lo mejor que puedo obtener es O (nlog (n))
Mi problema es que cada vez que se inserta un nodo que hace que el árbol se desequilibre, tengo que hacer otro ciclo para encontrar el nodo que está desequilibrado y aplicar rotación (s) para equilibrar el árbol de nuevo.
¡Cualquier ayuda es muy apreciada, gracias!
¿Qué tal si creamos un árbol completo equilibrado, con algunos nodos en el nivel más bajo que posiblemente falte, por ejemplo, para 6 elementos, creemos
o / / o o / / / o o o
A continuación, haga una caminata inorder, y cuando visite el i-ésimo nodo, establezca su clave en A [i].
Este es un árbol AVL válido, ya que cada nodo tiene un niño izquierdo y derecho cuyas alturas difieren en un máximo de uno.
El árbol original se puede construir en O (n), y el inorder caminar en O (n), por lo que la complejidad es O (n).
Por cierto, en una nota semirrelatada, hay una técnica llamada heapify para construir un montón (mezcla o máx) de una matriz de enteros que es O (n) para una matriz de longitud n, incluso si la inserción en un montón es O (log n ) - el truco es hacerlo de abajo hacia arriba.