Estoy buscando un algoritmo para fusionar dos árboles de búsqueda binarios de tamaño y rango arbitrarios. La forma obvia de implementar esto sería encontrar subárboles completos cuyo rango pueda caber en un nodo externo arbitrario en el otro árbol. Sin embargo, el peor tiempo de ejecución para este tipo de algoritmo parece ser del orden de O(n+m)
dónde n
y m
del tamaño de cada árbol, respectivamente.
Sin embargo, me han dicho que esto se podría hacer en O(h)
, donde h
está la altura del árbol con la altura más grande. Y estoy completamente perdido en cómo esto es posible. He intentado experimentar rotando uno de los árboles primero, pero girar un árbol en una columna ya es O (h).
O(log n)
con una simple función de nodo de movimiento?n
. Solo los árboles binarios completos o completos tienen una altura logarítmica con respecto a su número total de nodos.Respuestas:
En ArXiv: 1002.4248 , John Iacono y Özgür Özkan describen un algoritmo relativamente simple para fusionar dos árboles de búsqueda binarios en tiempo amortizado ; El análisis es la parte difícil. [ Actualización: como Joe observa correctamente en su respuesta, este algoritmo se debe a Brown y Tarjan.] También describen una estructura de datos de diccionario más complicada, basada en listas de omisión sesgadas, que admite fusiones en el tiempo amortizado O ( log n ) .O(log2n) O(logn)
Por otro lado, es imposible un límite de peor de los casos . Considere dos árboles de búsqueda binarios con n nodos, uno almacena los enteros pares entre 2 y 2 n , el otro almacena los enteros impares entre 1 y 2 n - 1 . Fusionar los dos árboles crea un nuevo árbol de búsqueda binario que almacena todos los enteros entre 1 y 2 n . En cualquiera de estos árboles, una fracción constante de los nodos tiene una paridad diferente a la de sus padres. (Prueba: el padre de una hoja impar debe ser par.) Por lo tanto, la fusión de los árboles pares e impares requiere un cambioO(logn) n 2 2n 1 2n−1 1 2n punteros.Ω(n)
fuente
Puede encontrar útil esta referencia: Brown y Tarjan, un algoritmo de fusión rápida , en el que los autores muestran cómo fusionar árboles binarios balanceados (AVL) en que es óptimo (para algoritmos basados en comparación). mynson las longitudes de las listas ordenadas representados por los árboles binarios de búsqueda, y se supone quem≥n.O(nlogmn) m n m≥n
También podría ver una discusión sobre diferentes técnicas para fusionar conjuntos ordenados en la sección 11.5 de este documento sobre árboles de búsqueda de dedos
fuente
Puede fusionar árboles en peor de los casosO (1) sin dejar de admitir: insertar, eliminar y buscar en .O (log n )
Brodal, Gerth Stølting, Christos Makris y Kostas Tsichlas. "Listas ordenadas catenables en tiempo constante con el peor caso puramente funcional" . En Actas de la 14ª Conferencia sobre el Simposio Europeo Anual - Volumen 14, 172–183. ESA'06. Londres, Reino Unido, Reino Unido: Springer-Verlag, 2006. [ PDF ]
fuente