Complejidades de recorridos de árbol binario

Question

¿Cuál es la complejidad temporal de inorder, postorder y preorden transversal de árboles binarios en estructuras de datos? ¿Es O (n) u O (log n) o O (n^2)?

Answer 1

O(n), porque atraviesa cada nodo una vez. O más bien, la cantidad de trabajo que realiza para cada nodo es constante (no depende del resto de los nodos).

Answer 2

Travesal es O (n) para cualquier orden, porque está golpeando cada nodo una vez. La búsqueda es donde puede ser menor que O (n) SI el árbol tiene algún tipo de esquema de organización (es decir, árbol de búsqueda binario).

Answer 3

O (n), yo diría. Estoy haciendo un árbol equilibrado, aplicable a todos los árboles. Suponiendo que utiliza la recursividad,

T (n) = 2 * T (n/2) + 1 ----------> (1)

T (n/2) para el subárbol izquierdo y T (n/2) para el subárbol derecho y '1' para verificar el caso base.

Al simplificar (1) puede probar que el recorrido (ya sea en orden o preorden o pedido posterior) es de orden O (n).

Answer 4

Los recorridos en orden, pedidos por adelantado y posteriores a la orden son recorridos en profundidad.

Para un gráfico, la complejidad de un primer recorrido de profundidad es O (n + m), donde n es el número de nodos, y m es el número de bordes.

Dado que un árbol binario es también un gráfico, lo mismo se aplica aquí. La complejidad de cada uno de estos recorridos en profundidad es O (n + m).

Dado que el número de bordes que pueden originarse de un nodo está limitado a 2 en el caso de un árbol binario, el número máximo de bordes totales en un árbol binario es n-1, donde n es el número total de nodos .

La complejidad se convierte en O (n + n-1), que es O (n).