time-complexity - preorden - recorrido de un arbol matematicas discretas

Complejidades de los recorridos de árboles binarios.

Question

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

Answer 1

Los recorridos en orden, previos y posteriores son los primeros en profundidad.

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

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

Como el número de bordes que pueden originarse desde 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).

Answer 2

O (n), diría yo. Lo estoy haciendo por un árbol equilibrado, aplicable para todos los árboles. Suponiendo que usas recursión,

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 en orden anticipada o posterior) es de orden O (n).

Answer 3

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 4

O(n) , porque atraviesas 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).