¿Cómo combinar dos BST de manera eficiente?

Question

¿Cómo combinar dos árboles de búsqueda binarios que mantienen la propiedad de BST?

Si decidimos tomar cada elemento de un árbol e insertarlo en el otro, la complejidad de este método sería O(n1 * log(n2)), donde n1 es el número de nodos del árbol (por ejemplo T1), que hemos dividido y n2 es la cantidad de nodos del otro árbol (digamos T2). Después de esta operación, solo una BST tiene n1 + n2 nodos.

Mi pregunta es: ¿podemos hacer algo mejor que O (n1 * log (n2))?

Answer 1

¿Qué tal aplanar ambos árboles en listas ordenadas, fusionar las listas y luego crear un nuevo árbol?

Answer 2

• Acoplar árboles en listas ordenadas.
• Combinar listas ordenadas.
• Crear árbol fuera de la lista fusionada.

IIRC, que es O (n1 + n2).

Answer 3

respuesta de Naaff con un poco más detalles:

• aplanamiento de una BST en una lista ordenada es O (N)
  • Es sólo iteración "en orden" en todo el árbol.
  • haciendo por tanto es O (n1 + n2)
• La fusión de dos listas ordenadas es en una lista ordenada es O (n1 + n2).
  • Mantener punteros a los jefes de ambas listas
  • escoger la cabeza más pequeña y avanzar en su puntero
  • Esta es la forma en la unión de fusión-tipo funciona
• Creación de una BST perfectamente equilibrada de una La lista ordenada es O (N)
  • El valor en el medio sería la raíz y recurse.
  • En nuestro caso, la lista ordenada es de tamaño n1 + n2. de modo O (n1 + n2)
  • El árbol resultante sería el BST conceptual de binario a buscar la lista

Tres pasos de O (n1 + n2) resultar en O (n1 + n2)

para N1 y N2 del mismo orden de magnitud, eso es mejor que O (n1 * log (N2))

Answer 4

Jonathan,

Después de la clasificación, tenemos una lista de longitud n1 + n2. La construcción de un árbol binario tomará el tiempo de registro (n1 + n2). Esto es lo mismo que ordenar por combinación, solo que en cada paso recursivo no tendremos un término O (n1 + n2) como lo tenemos en el algoritmo de ordenación por fusión.Entonces la complejidad del tiempo es log (n1 + n2).

Ahora la complejidad de todo el problema es O (n1 + n2).

También diría que este enfoque es bueno si dos listas son de tamaño comparable. Si los tamaños no son comparables, es mejor insertar cada nodo del árbol pequeño en un árbol grande. Esto tomaría O (n1 * log (n2)) tiempo. Por ejemplo, si tenemos dos árboles uno del tamaño 10 y otro del tamaño 1024. Aquí n1 + n2 = 1034 donde como n1log (n2) = 10 * 10 = 100. Por lo tanto, el enfoque debe depender de los tamaños de los dos árboles.

Answer 5

O (n1 * log (n2)) es el caso medio, incluso si tenemos 2 fusionar cualquier lista sin clasificar en una BST. No estamos utilizando el hecho de que la lista es una lista ordenada o una BST.

Según yo Supongamos que un BST tiene elementos n1 y otro tiene elementos n2. Ahora convierta un BST en una lista de matriz ordenada L1 en O (n1).

BST Fusionada (BST, Array)

si (Array.size == 0) de regreso BST si (Array.size == 1) insertar el elemento en el BST. devolver BST;

Encuentra el índice en la matriz cuyo elemento izquierdo < BST.rootnode y elemento de la derecha> = BST.rootnode dicen Índice. si (BST.rootNode.leftNode == null) // es decir, ningún nodo izquierdo { insertar todos los array de Índice a 0 en la izquierda de BST y } otro { BST Fusionada (BST.leftNode, Array { 0 al índice}) }

si (BST.rootNode.rightNode == null) // es decir, ningún nodo derecho { insertar todos los array de índice para Array.size en derecho de BST } otro { BST fusionado (BST.rightNode, matriz {índice a tamaño de matriz}) }

return BST.

Este algoritmo tomará < < tiempo que O (n1 * log (n2)) como cada partición de la matriz y BST para manejar el subproblema.

---

Answer 6

La idea es utilizar el recorrido iterativo inorden. Usamos dos pilas auxiliares para dos BST. Como necesitamos imprimir los elementos en forma ordenada, cada vez que obtenemos un elemento más pequeño de cualquiera de los árboles, lo imprimimos. Si el elemento es mayor, lo empujamos hacia atrás para apilarlo para la siguiente iteración.