programar - construir arbol binario a partir de su recorrido

Convertir un montón máximo a un árbol de búsqueda binario (3)

Se nos da una serie de 2 ^m - 1 elementos distintos, comparables, indexados a partir de 1.

Podemos ver la matriz como un árbol binario completo:

Node is placed at index i. Left child is placed at 2i. Right child is placed at 2i+1.

Por ejemplo, la matriz

[7 6 4 5 2 3 1]

es el arbol

7 / / 6 4 / / / / 5 2 3 1

Ahora, cuando se ven como un árbol binario, estos elementos satisfacen la propiedad de montón, un nodo es mayor que sus dos hijos:

A[i] > A[2i] and A[i] > A[2i+1]

¿Existe un algoritmo in situ razonablemente rápido para mezclar los elementos de la matriz de forma que el árbol binario resultante (como se describe anteriormente) sea un árbol de búsqueda binario?

Recuerde que en un árbol de búsqueda binario, un nodo es mayor que todos sus descendientes izquierdos y menor que todos sus descendientes derechos.

Por ejemplo, la reorganización de la matriz anterior sería

[4 2 6 1 3 5 7]

que corresponde al árbol binario de búsqueda

4 / / 2 6 / / / / 1 3 5 7

Primero notamos que podemos, sin pérdida de generalidad, asumir que tenemos los elementos 1,2,3, ... 2^m-1 en nuestro árbol binario. Entonces, a partir de ahora, asumimos que tenemos estos números.

Entonces, mi intento sería alguna función para convertir una matriz ordenada (es decir, 1 2 3 4 5 ) en una matriz que representa un árbol binario ordenado.

En un árbol binario ordenado con (2^m)-1 elementos siempre tenemos que el "fondo" del árbol consta de todos los números desiguales, por ejemplo, para m=3 :

4 2 6 1 3 5 7

Esto significa que, en la matriz correspondiente, tenemos que los últimos números son todos los números desiguales:

4 2 6 1 3 5 7 ------- ^ uneven numbers!

Así que podemos construir la última "fila" del árbol binario asegurándonos de que los últimos 2^(m-1) números en la matriz correspondiente son todos los números desiguales. Entonces, todo lo que tenemos que hacer para la última fila es construir una función que mueva todos los elementos en posiciones con índices desiguales a la última fila.

Así que asumamos por ahora que tenemos una rutina que, dada una matriz ordenada como entrada, establece la última fila correctamente.

Luego podemos llamar a la rutina para que toda la matriz construya la última fila mientras todos los demás elementos permanecen ordenados. Cuando aplicamos esta rutina en la matriz 1 2 3 4 5 6 7 , tenemos la siguiente situación:

2 4 6 1 3 5 7 ------- ^ correct!

Después de la primera ronda, aplicamos la rutina para el subarreglo restante (es decir, 2 4 6 ) que construye la segunda última "fila" de nuestro árbol binario, mientras dejamos los elementos restantes sin cambios, por lo que obtenemos lo siguiente:

now correct as well! v --- 4 2 6 1 3 5 7 ------- ^ correct from run before

¡Así que todo lo que tenemos que hacer es construir una función que instale la última fila (es decir, la segunda mitad de la matriz) correctamente!

Esto se puede hacer en O(n log n) donde n es el tamaño de entrada de la matriz. Por lo tanto, solo atravesamos la matriz desde el final hasta el principio e intercambiamos las posiciones desiguales de tal manera que la última fila (es decir, la última mitad de la matriz) sea correcta. Esto se puede hacer en el lugar. Después, ordenamos la primera mitad de la matriz (utilizando, por ejemplo, heapsort). Entonces, todo el tiempo de ejecución de esta subrutina es O(n log n) .

Entonces, el tiempo de ejecución para una matriz de tamaño n en total es:

O(n log n) + O(n/2 log n/2) + O(n/4 log n/4) + ... que es lo mismo que O(n log n) . Tenga en cuenta que tenemos que usar un algoritmo de clasificación en el lugar como Heapsort para que todo esto funcione completamente en el lugar.

Lamento no poder explicarlo más, pero creo que puede hacerse una idea.

Sea n = 2 ^m - 1. En tiempo lineal, podemos hacer un max-heap y extraer los elementos de un árbol de búsqueda binario en orden ordenado, por lo que lo mejor que podemos esperar (asumiendo que los algoritmos se basan en la comparación) es O ( n log n) tiempo y O (1) espacio. Aquí hay tal algoritmo.

Para j = n hasta 1, extraiga el elemento max de j-element max-heap y guárdelo en la ubicación j (recientemente desocupada). Esto ordena la matriz.
Convierta la matriz ordenada en un árbol de búsqueda binario con una estrategia de dividir y conquistar. (De manera ingenua, esto es el espacio Omega (log n), pero creo que podemos comprimir la pila para O (1) log (n) palabras de bit.)
a. Treeificar los elementos menos que la raíz.
segundo. Treeificar los elementos mayores que la raíz.
do. Combine los árboles girando las hojas menos que la raíz a la posición (= tres reversas) para dejar un subproblema de la mitad del tamaño (O (n)).
(08 04 12 02 06 10 14 01 03 05 07 09 11 13 15)16(24 20 28 18 22 26 30 17 19 21 23 25 27 29 31)

(08 04 12 02 06 10 14)16(24 20 28 18 22 26 30)01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

(08 04 12)16(24 20 28)02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

(08)16(24)04 12 20 28 02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

16 08 24 04 12 20 28 02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

Sólo algunas ideas básicas:

Un árbol binario de búsqueda es un árbol binario.
Ambos hijos de la raíz son nulos o ellos mismos buscan árboles binarios
Los valores satisfacen la siguiente condición: left child <root <right child

La condición 1 no es problema, el montón también es un árbol binario. La condición 2 es problemática, pero sugiere un enfoque de abajo hacia arriba. La condición 3 no se cumple también.

De abajo hacia arriba significa: - Comenzamos con todas las hojas - esto no es problemático, son árboles de búsqueda binarios. - Ahora continuamos con una caminata recursiva a través de cada nivel de padres hasta la raíz. - Cambie los subárboles si el niño izquierdo es más grande que el niño derecho. - Intercambie la raíz con el valor más grande de los 2 hijos (es el hijo correcto) - Puede que esto no sea suficiente: es posible que deba continuar corrigiendo el subárbol correcto hasta que vuelva a ser un árbol de búsqueda binario.

Esto debería funcionar. Pero aún así, eliminar el elemento superior e insertarlo en un árbol de auto balanceo será el enfoque más rápido / mejor y mucho más fácil de implementar (por ejemplo, usar componentes estándar como std :: map en c ++).

Otra idea: para los árboles de búsqueda binarios tiene la propiedad de que un recorrido de la raíz izquierda derecha a través del árbol obtiene los valores ordenados. Esto podría hacerse a la inversa. Obtener los valores ordenados del montón también debería ser fácil. Solo intente combinar esto: leer del montón y escribir el árbol directamente de los valores ordenados. Esto se puede hacer en O (n), creo, pero no estoy seguro de si se puede hacer en su lugar o no, supongo que no.