Profondeur en fonction de la hauteur de l'arbre. Rafraîchissant les fondamentaux
je fais une mise à jour des algorithmes et des structures de données.
je suis confus sur le concept de profondeur et hauteur d'un arbre. Dans de nombreux cas, en particulier sur les sites axés sur les entrevues, il me semble que ces termes sont utilisés de façon interchangeable.
il me semble que la littérature de base Les définit comme applicables à un noeud et à un arbre.
Donc la profondeur de la racine (qui est un nœud) est 0. La hauteur de la racine (ou de tout sous-code) est la hauteur maximale de ses enfants.
mais lorsque vous appliquez ces Termes sur un arbre, c'est-à-dire trouver la profondeur maximale d'un arbre, il semble que ces termes sont maintenant "insignifiants" et peuvent être utilisés de façon interchangeable, c'est-à-dire pour trouver la profondeur maximale calculez juste la hauteur maximale.
Par exemple dans ce post Vérifier si l'arbre est équilibré les réponses se concentrent sur la hauteur de l'arbre tandis que la définition de l'équilibre pourrait être sur la profondeur de l'arbre
Est ma compréhension correcte ou suis-je raté sur ces fondamentaux?
9 réponses
Quand on parle d'un arbre, ils signifient la même chose: la longueur du plus long chemin de la racine à un nœud feuille.
profondeur est habituellement utilisé pour décrire une propriété d'un noeud d'arbre, alors que le hauteur est utilisé pour décrire la propriété de l'arbre entier, comme dans les exemples suivants:
- le noeud racine a un profondeur zéro
- le noeud X a un profondeur de N
- hauteur de l'arbre est M
La hauteur d'un arbre est définie comme la profondeur du plus profond de son nœud.
une profondeur est "la profondeur d'un noeud" [ou sa distance par rapport à la racine]. la hauteur est "quelle hauteur de l'arbre est" [ou, quelle est la distance la plus éloignés de la feuille d'elle]
Formellement:
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
EDIT: en se référant au concept de profondeur maximale, il est identique à la hauteur d'un arbre [qui est maximale à la racine], vous pouvez le prouver par induction.
hauteur d'un noeud est la longueur de la plus longue trajectoire descendante vers une feuille à partir de ce noeud. La hauteur de la racine est hauteur de l'arbre.
profondeur d'un noeud est la longueur du chemin vers sa racine (i.e., son chemin de racine). Cela est généralement nécessaire dans la manipulation des différents arbres auto-équilibrants, arbres AVL en particulier. Le noeud de racine a la profondeur zéro, les noeuds de feuille ont la hauteur zéro, et un l'arbre avec un seul noeud (donc à la fois une racine et une feuille) a la profondeur et la hauteur zéro. Conventionnellement, un arbre vide (arbre sans noeuds, si tel est autorisé) a une profondeur et une hauteur -1.
Hauteur d'un arbre est le nombre de nœuds de la racine à la feuille suivant le plus long chemin. Donc, si nous avons un nœud (racine) hauteur=1 Arbre vide: 0
et la profondeur ou le niveau de n'importe quel noeud est le nombre de bords du noeud racine à ce noeud. si..la profondeur de la racine est 0.
de cette façon, la profondeur maximale de l'arbre est inférieure à la hauteur de l'arbre.
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;
}
Profondeur d'un Nœud: est la longueur d'un chemin de la racine à un nœud. Hauteur D'un noeud: Longueur d'un chemin allant du noeud au noeud le plus interne(feuille).
mais la hauteur et la profondeur dans le cas de l'arbre sont les mêmes. Hauteur de l'arbre = profondeur de l'arbre = hauteur maximale = profondeur maximale.
dans l'arbre de recherche binaire
- hauteur d'un noeud: # bords sur la plus longue trajectoire descendante simple du noeud à une feuille
- Hauteur d'un arbre: les hauteur de la racine
- profondeur d'un noeud: Longueur du chemin simple (#arêtes) de la racine au noeud
la hauteur du noeud est en référence à la longueur de la feuille du chemin le plus long au noeud de la feuille à partir du noeud source.
la profondeur du noeud est en référence au noeud racine. - longueur totale du noeud source à la racine
mais quand vous parlez en général de l'arbre entier les deux se réfère à même, il diffère seulement si vous prenez un noeud particulier à l'intérieur de l'arbre