c++ - delete - ¿Cómo combinar dos BST de manera eficiente?

search binary tree c++

Question

¿Cómo fusionar 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 (digamos 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

Jonathan,

Después de ordenar, 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. Entonces el enfoque debe depender del tamaño de los dos árboles.

Answer 3

La idea es usar un recorrido iterativo iterativo. 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.

Answer 4

La respuesta de Naaff con un poco más de detalles:

• Aplanar una BST en una lista ordenada es O (N)
  • Es solo una iteración "en orden" en todo el árbol.
  • Hacerlo para ambos es O (n1 + n2)
• La fusión de dos listas ordenadas en una lista ordenada es O (n1 + n2).
  • Mantenga los punteros a la cabeza de ambas listas
  • Elija la cabeza más pequeña y avance su puntero
  • Así es como funciona la fusión de merge-sort
• La creación de un BST perfectamente equilibrado a partir de una lista ordenada es O (N)
  • Ver fragmento de código a continuación para el algoritmo [1]
  • En nuestro caso, la lista ordenada es de tamaño n1 + n2. entonces O (n1 + n2)
  • El árbol resultante sería el BST conceptual de búsqueda binaria en la lista

Tres pasos de O (n1 + n2) dan como resultado O (n1 + n2)

Para n1 y n2 del mismo orden de magnitud, es mejor que O (n1 * log (n2))

[1] Algoritmo para crear una BST equilibrada a partir de una lista ordenada (en Python):

def create_balanced_search_tree(iterator, n):
    if n == 0:
        return None
    n_left = n//2
    n_right = n - 1 - n_left
    left = create_balanced_search_tree(iterator, n_left)
    node = iterator.next()
    right = create_balanced_search_tree(iterator, n_right)
    return {''left'': left, ''node'': node, ''right'': right}

Answer 5

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

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

Combinado BST (BST, Array)

if (Array.size == 0) devuelve BST si (Array.size == 1) inserta el elemento en el BST. devolver BST;

Encuentre el índice en la matriz cuyo elemento izquierdo <BST.rootnode y elemento derecho> = BST.rootnode dicen Índice. if (BST.rootNode.leftNode == null) // ie No nodo izquierdo {inserte todo el conjunto de Index a 0 en left of BST y} else {BST combinado (BST.leftNode, Array {0 to Index})}

if (BST.rootNode.rightNode == null) // ie No nodo derecho {insertar todo el conjunto de Index a Array.size a la derecha de BST} else {BST combinado (BST.rightNode, Array {Index to Array.size} )}

devolver 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

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

IIRC, que es O (n1 + n2).