algorithm - trees - tree structures
¿Cuál es la diferencia entre la profundidad y la altura del árbol? (6)
Esta es una pregunta simple de la teoría de algoritmos. La diferencia entre ellos es que en un caso se cuenta el número de nodos y en otro número de bordes en el camino más corto entre el nodo raíz y el nodo concreto. ¿Cual es cual?
Aprendí que la profundidad y la altura son propiedades de un nodo :
La profundidad de un nodo es la cantidad de bordes desde el nodo al nodo raíz del árbol.
Un nodo raíz tendrá una profundidad de 0.La altura de un nodo es la cantidad de aristas en la ruta más larga desde el nodo hasta una hoja.
Un nodo de hoja tendrá una altura de 0.
Propiedades de un árbol :
La altura de un árbol sería la altura de su nodo raíz,
o de manera equivalente, la profundidad de su nodo más profundo.El diámetro (o ancho ) de un árbol es la cantidad de nodos en la ruta más larga entre dos nodos de hoja. El árbol de abajo tiene un diámetro de 6 nodos.
De acuerdo con Cormen et al. Introducción a los algoritmos (Apéndice B.5.3), la profundidad de un nodo X en un árbol T se define como la longitud de la ruta simple (número de bordes) desde el nodo raíz de T a X. La altura de un nodo Y es el número de aristas en el camino simple más largo hacia abajo desde Y a una hoja. La altura de un árbol se define como la altura de su nodo raíz.
Tenga en cuenta que una ruta simple es una ruta sin repetir vértices.
La altura de un árbol es igual a la profundidad máxima de un árbol . La profundidad de un nodo y la altura de un nodo no son necesariamente iguales. Ver la Figura B.6 de la 3ª Edición de Cormen et al. para una ilustración de estos conceptos.
A veces he visto problemas al pedirle a uno que cuente los nodos (vértices) en vez de los bordes, así que solicite una aclaración si no está seguro de contar los nodos o bordes durante un examen o una entrevista de trabajo.
Otra forma de entender esos conceptos es la siguiente: Profundidad: dibuje una línea horizontal en la posición raíz y trate esta línea como terreno. Entonces, la profundidad de la raíz es 0, y todos sus hijos crecen hacia abajo, por lo que cada nivel de nodos tiene la profundidad actual + 1.
Altura: la misma línea horizontal, pero esta vez la posición del suelo son los nodos externos, que es la hoja del árbol y cuentan hacia arriba.
Quería hacer esta publicación porque soy estudiante de pregrado de CS y cada vez utilizo más OpenDSA y otros libros de texto de código abierto. Parece que la forma en que se enseña la altura y la profundidad ha cambiado de una generación a otra, y estoy publicando esto para que todos sepan que esta discrepancia ahora existe y que con suerte no causará errores en ninguna programas! Gracias.
Del libro OpenDSA Data Structures & Algos :
Si n 1 , n 2 , ..., n k es una secuencia de nodos en el árbol tal que n i es el padre de n i +1 para 1 <= i <k, esta secuencia se llama ruta desde n 1 a n k . La longitud de la ruta es k-1. Si hay una ruta desde el nodo R al nodo M, entonces R es un ancestro de M, y M es un descendiente de R. Por lo tanto, todos los nodos en el árbol son descendientes de la raíz del árbol, mientras que la raíz es el antecesor de todos los nodos La profundidad de un nodo M en el árbol es la longitud del camino desde la raíz del árbol hasta M. La altura de un árbol es una más que la profundidad del nodo más profundo del árbol. Todos los nodos de profundidad d están en el nivel d en el árbol. La raíz es el único nodo en el nivel 0, y su profundidad es 0.
Figura 7.2.1: Un árbol binario. El nodo A es la raíz. Los nodos B y C son hijos de A. Los nodos B y D juntos forman un subárbol. El nodo B tiene dos hijos: su hijo izquierdo es el árbol vacío y su hijo derecho es D. Los nodos A, C y E son ancestros de G. Los nodos D, E y F componen el nivel 2 del árbol; el nodo A está en el nivel 0. Los bordes de A a C a E a G forman una ruta de longitud 3. Los Nodos D, G, H e I son hojas. Los nodos A, B, C, E y F son nodos internos. La profundidad de I es 3. La altura de este árbol es 4.
Respuesta simple:
Profundidad:
1. Árbol : el número de aristas / arco desde el nodo raíz al nodo hoja del árbol se denomina Profundidad del árbol.
2. Nodo : el número de aristas / arco desde el nodo raíz a ese nodo se llama como la Profundidad de ese nodo.
la altura y la profundidad de un árbol es igual ...
pero la altura y la profundidad de un nodo no son iguales porque ...
la altura se calcula al atravesar desde el nodo dado hasta la hoja más profunda posible.
la profundidad se calcula desde el cruce desde la raíz hasta el nodo dado .....