algorithm - data - Profundidad vs Altura de un árbol. Refrescando los fundamentos.
tree data structure (9)
Altura del nodo es con referencia a Hoja: longitud del camino más largo al nodo de hoja desde el nodo de origen.
La profundidad del nodo es con referencia al nodo raíz. - longitud total desde el nodo fuente hasta la raíz
Pero cuando se habla en general de que todo el árbol se refiere al mismo, difiere solo si toma un nodo particular dentro del árbol.
Estoy haciendo una actualización y algoritmos y estructuras de datos.
Estoy confundido sobre el concepto de profundidad contra altura de un árbol. En muchos casos, especialmente en los sitios que se centran en los cuestionarios de las entrevistas, me parece que estos términos se usan indistintamente.
Me parece que la literatura básica los define como aplicables a un nodo y no a un árbol.
Así que la profundidad de la raíz (que es un nodo) es 0 . La altura de la raíz (o cualquier subnodo) es la altura máxima de sus hijos.
Pero cuando aplica estos términos en un árbol, es decir, encuentre la profundidad máxima de un árbol, parece que estos términos ahora no tienen significado y se pueden usar indistintamente, es decir, para encontrar la profundidad máxima, simplemente calcule la altura máxima.
Por ejemplo, en esta publicación, compruebe si el árbol está equilibrado, las respuestas se centran en la altura del árbol, mientras que la definición de equilibrio podría estar en la profundidad del árbol
¿Mi entendimiento es correcto o estoy arruinando estos fundamentos?
Cuando se habla de un árbol, significan lo mismo: la longitud del camino más largo desde la raíz hasta un nodo de hoja.
En árbol de búsqueda binario
- Altura de un nodo: # bordes en la ruta descendente simple más larga del nodo a una hoja
- Altura de un árbol: altura de la raíz.
- Profundidad de un nodo: longitud de la ruta simple (# bordes) desde la raíz hasta el nodo
La profundidad se usa generalmente para describir una propiedad de un nodo de árbol, mientras que la altura se usa para describir la propiedad de todo el árbol, como en los siguientes ejemplos:
- El nodo raíz tiene una profundidad de cero.
- El nodo X tiene una profundidad de N
- La altura del arbol es m
La altura de un árbol se define como la profundidad de su nodo más profundo.
La altura de un nodo es la longitud del camino descendente más largo hacia una hoja desde ese nodo. La altura de la raíz es la altura del árbol .
La profundidad de un nodo es la longitud de la ruta a su raíz (es decir, su ruta raíz). Esto es comúnmente necesario en la manipulación de los diversos árboles de auto-equilibrio, en particular los árboles AVL . El nodo raíz tiene profundidad cero, los nodos hoja tienen altura cero y un árbol con un solo nodo (de ahí que tanto la raíz como la hoja) tengan profundidad y altura cero. Convencionalmente, un árbol vacío (árbol sin nodos, si está permitido) tiene profundidad y altura −1.
La altura de un árbol es el número de nodos desde la raíz a la hoja siguiendo la ruta más larga. Entonces, si tenemos un nodo (la propia raíz) altura = 1 Árbol vacío: 0
Y la profundidad o el nivel de cualquier nodo es el número de bordes desde el nodo raíz a ese nodo. Entonces ... la profundidad de la raíz es 0.
De esta manera, la profundidad máxima del árbol es menor que la altura del árbol.
Profundidad de un nodo: es una longitud de una ruta desde la raíz a un nodo. Altura de un nodo: es la longitud de una ruta desde el nodo hasta el nodo más interno (hoja).
Pero la altura y la profundidad en caso de árbol son las mismas. Altura del árbol = Profundidad de un árbol = Altura máxima = Profundidad máxima.
una profundidad es "qué tan profundo es un nodo" [o qué tan lejos está de la raíz]. la altura es "qué tan alto está el árbol" [o, a qué distancia está la hoja más alejada de él]
Formalmente:
height(v) = 0 v is a leaf
max{height(u)|for every u such that u is a son of v} + 1 else
depth(v) = 0 v root
depth(u) + 1 where u is the parent of v else
EDITAR : cuando se refiere al concepto de profundidad máxima, es idéntico a la altura de un árbol [que es la máxima en la raíz], puede probarlo por inducción.
private static int getHeight(BTreeNode n){
if(n == null)
return 0;
int lHeight = getHeight(n.left);
int rheight = getHeight(n.right);
int height = 1+Math.max(lHeight,rheight);
return height;
}