árbol binario en general a la complejidad de conversión árbol

Question

¿Cuál es la complejidad del tiempo y el espacio de la conversión de un árbol en general a uno binario?!

Gracias

Answer 1

No sé qué quiere decir con "árbol general". En cualquier caso, la complejidad tomo de su inserción en un árbol binario equilibrado es O(log n), donde n es el número de elementos que se encuentran en el árbol, por lo que la construcción de un árbol completo de alguna lista de artículos sería O(n log n), donde n es el número total de elementos de insertar.

También tendrá que incluir el tiempo necesario para obtener los elementos desde el otro árbol. Ese tiempo depende del tipo de árbol que tiene. Por el bien del argumento voy a suponer que se puede recorrer en un tiempo lineal, por lo que la obtención de datos desde el árbol existente es O(n).

Eso hace que su O(n + (n log n)) tiempo total complejidad.

El espacio adicional requerido será n * sizeof(node), donde sizeof(node) es el tamaño de su nodo de árbol binario. Tenga en cuenta que, si los artículos se almacenan en los nodos del árbol "en general" son punteros, usted no tendrá que pagar el costo de copiar los objetos reales - sólo la cabeza del nodo de árbol binario, que suele ser de tres puntos: la los datos, el enlace hijo izquierdo, y el vínculo hijo derecho.