¿Cuál es la diferencia entre la profundidad y la altura del árbol?

262

Esta es una pregunta simple de la teoría de algoritmos.
La diferencia entre ellos es que, en un caso, cuenta el número de nodos y en el otro número de bordes en la ruta más corta entre el nodo raíz y el nodo concreto.
¿Cual es cual?

Gabriel Ščerbák
fuente
78
Consejo: para evitar confusiones entre terminologías: 1. Altura: Imagine que mide la altura de una persona, lo hacemos de la punta a la cabeza (de la hoja a la raíz). 2. Profundidad: imagina medir la profundidad de un mar, lo hacemos desde la superficie de la tierra hasta el lecho oceánico (raíz a hoja).
Yesh
@ Sí. Esta es una gran analogía.
Carácter especial
1
Para agregar a @Yesh una excelente analogía: para algún nodo interno en el medio del árbol, su profundidad es cuántos niveles está debajo del nodo raíz, y su altura es cómo niveles está por encima de su nodo secundario más inferior.
Thomas Nguyen

Respuestas:

664

Aprendí que la profundidad y la altura son propiedades de un nodo :

  • los profundidad de un nodo es el número de aristas desde el nodo hasta el nodo raíz del árbol.
    Un nodo raíz tendrá una profundidad de 0.

  • La altura de un nodo es el número de aristas en la ruta más larga desde el nodo hasta una hoja.
    Un nodo 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 equivalente, la profundidad de su nodo más profundo.

  • El diámetro (o ancho ) de un árbol es el número de nodos en la ruta más larga entre dos nodos de hoja. El árbol de abajo tiene un diámetro de 6 nodos.

Un árbol, con altura y profundidad de cada nodo.

Daniel AA Pelsmaeker
fuente
21
+1 estaba a punto de agregar una cita con el mismo contenido desde aquí: en.wikipedia.org/wiki/Tree_%28data_structure%29
Péter Török
2
es eso significa altura == profundidad máxima
roottraveller
66
@rkm_Hodor: Sí, la altura de un árbol siempre es igual a la profundidad del nodo más profundo.
Daniel AA Pelsmaeker
1
¿Podría citar una fuente para su afirmación de que el diámetro de un árbol cuenta nodos en lugar de bordes? Esto entra en conflicto con la definición habitual del diámetro de un gráfico (véase, por ejemplo, en.wikipedia.org/wiki/Distance_(graph_theory) ) que solicita el camino más largo.
j_random_hacker
1
@j_random_hacker Es una cuestión de definición, elige la más útil para ti. Para pasar del número de vértices al número de aristas, solo resta 1. Prefiero contar el número de vértices, ya que esto da como resultado un gráfico con un solo nodo que tiene ancho 1, y un gráfico vacío que tiene ancho 0. mundo matemático. wolfram.com/GraphDiameter.html
Daniel AA Pelsmaeker
44

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 atravesando desde el nodo dado hasta la hoja más profunda posible.

la profundidad se calcula a partir del recorrido desde la raíz hasta el nodo dado .....

Praveen_Shukla
fuente
44
"la altura se calcula atravesando desde la hoja hasta el nodo dado" no es correcto, la hoja debe ser la más profunda entre todas las hojas del nodo dado.
mightyWOZ
14

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 aristas) desde el nodo raíz de T a X. La altura de un nodo Y es el número de bordes en el más largo camino simple descendente desde Y hasta 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 vértices repetidos.

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 Figura B.6 de la 3ra Edición de Cormen et al. para una ilustración de estos conceptos.

A veces he visto problemas pidiéndole a uno que cuente nodos (vértices) en lugar de bordes, así que solicite una aclaración si no está seguro de que debe contar nodos o bordes durante un examen o una entrevista de trabajo.

glaciar
fuente
¿Hay alguna diferencia en contar los nodos y bordes? Parece que ambos darán el mismo resultado. Corrígeme si estoy equivocado.
VINOTH ENERGETIC
@jdhao, ¿cómo puede ser la profundidad de la raíz 2? Es 0 (si se consideran los bordes) o 1 (si se consideran los nodos).
neowulf33
@ neowulf33, sí, estoy terriblemente equivocado. La profundidad del nodo raíz debe ser 0. Eliminaré mi comentario para no confundir a las personas.
jdhao
2

Respuesta simple:
Profundidad:
1. Árbol : el número de aristas / arco desde el nodo raíz hasta el nodo hoja del árbol se denomina Profundidad del árbol.
2. Nodo : el número de aristas / arco desde el nodo raíz hasta ese nodo se llama Profundidad de ese nodo.

Akshay Sahu
fuente
2

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 tierra. Por lo tanto, 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 nodos externos, que son la hoja del árbol y cuentan hacia arriba.

Wilson Zhang
fuente
2

Quería hacer esta publicación porque soy un estudiante universitario de CS y cada vez más usamos OpenDSA y otros libros de texto de código abierto. Parece que, según la respuesta mejor calificada, la forma en que se enseña la altura y la profundidad ha cambiado de una generación a la siguiente, y estoy publicando esto para que todos sepan que esta discrepancia ahora existe y es de esperar que no cause 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 de modo que n i es el padre de n i +1 para 1 <= i <k, entonces esta secuencia se llama ruta desde n 1 to n k . La longitud del camino 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 ancestro 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 uno 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

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 constituyen 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 trayectoria 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.

Fresno
fuente
Para lo que vale, la definición en este enlace se ha cambiado a: "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 la profundidad del nodo más profundo en el árbol ".
kaya3