En el contexto de los gráficos , un árbol es un gráfico en el que cada nodo excepto el nodo "raíz " origen tiene un único nodo primario cuyo linaje se remonta al nodo raíz . El gráfico que forma una estructura similar a la de un árbol de Navidad , gradualmente expansión y la adición de nuevos nodos y los niños en cada nivel . En un árbol, el número de niños que cada nodo tiene es " factor de ramificación . " Del árbol , el número de generaciones en el árbol es el árbol de la " profundidad".
Búsqueda en profundidad
búsqueda en profundidad es un método de búsqueda a través de un árbol, en el que el algoritmo de baja por el árbol hasta que encuentre el nodo de destino . A partir del nodo raíz , el algoritmo camina hasta el próximo hijo y nieto de ese niño , repitiendo el proceso hasta que encuentra un nodo " hoja " sin hijos. Después de que encuentre ese nodo , camina de nuevo hasta que encuentra un nodo sin examinar. Si no hay más nodos examinados , se detiene.
Algoritmo Tiempo Complejidad
La hora de recorrer un árbol a través de la búsqueda en profundidad depende del número de los vértices de la gráfica y los bordes entre ellos. En el peor de los casos , el algoritmo debe viajar a través de cada vértice y a lo largo de cada borde , por lo que el tiempo que se necesita es el número de vértices y el número de bordes , o "V + E. " Para un árbol , el número de bordes es igual a los nodos menos uno , por lo que el tiempo total es " 2V - . 1 " Si cada nodo en el gráfico tiene el mismo número de niños - un factor de ramificación constante - a continuación, este tiempo es igual a ese factor . elevado a la potencia de la profundidad del árbol
Otras consideraciones
al implementar cualquier algoritmo , la velocidad del algoritmo depende de dos factores: el número de cálculos que deben hacer y el tiempo necesario para acceder a los recursos que necesita para funcionar - por lo general la memoria. Cuanta más memoria tenga un programa requiere , más tiempo se tarda en ejecutar . Una búsqueda en profundidad debe recordar los nodos anteriores que visitó , por lo que la cantidad a lo peor de la memoria que requiere es igual al número de nodos en el árbol.