Quelle est la hauteur d'un BST vide lors de son utilisation dans un contexte d'équilibre?

Question

Supposons que le type de données pour un BST est défini comme suit (en SML)

datatype 'a bst_Tree =
   Empty
 | Node of (int * 'a) * 'a bst_Tree * 'a bst_Tree;

Donc, il y a deux cas dans lesquels un BST est Empty ou il peut avoir une (clé, valeur), ainsi que deux enfants.

Maintenant, pour le cas d'un AVL où la condition est

  

Dans un arbre AVL, les hauteurs des deux sous-arbres de l'enfant d'un nœud diffèrent d'au plus un
   _{- AVL arbre Wikipedia}

Je veux pouvoir créer une fonction de la hauteur pour vérifier si l'arbre est équilibré. Ma configuration actuelle est la suivante

fun height (Empty) = ~1
  | height (Node(v, Empty, Empty)) = 0 (* Redundant matching because of third case *)
  | height (Node(v, L, R)) = 1 + Int.max(height(L),height(R))

J'ai essayé de séparer l'arbre en trois conditions

1. Un vide Arbre
2. Un arbre avec un nœud racine
3. Un arbre peuplé

La raison est qu'il ne semble pas être une source canonique sur ce que la valeur est la hauteur d'un arbre Empty par opposition à celui qui a seulement une racine. Aux fins de ma fonction de l'équilibre, il a fait le travail, mais j'essaie plutôt de comprendre pourquoi il n'y a pas une réponse canonique pour la hauteur d'un arbre Empty.

Il y a une réponse canonique, dans une affaire de parler sur Wikipédia mais en d'abord faire des recherches sur ce débordement de la pile je suis arrivé à de nombreux commentaires disant que cela tort / incorrect / non conventionnel

  

Classiquement, la valeur -1 correspond à un sous-arbre, sans noeuds, alors que zéro correspond à un sous-arbre avec un noeud.)

Je saisi la question à partir de laquelle est apparu mon incertitude

Quelle est la définition de la hauteur d'un arbre

  

Je pense que vous devriez jeter un oeil à la Dictionnaire des structures et algorithmes de données sur le site Web du NIST. Il définition pour la hauteur, dit un seul nœud est la hauteur 0.

     

Le définition d'un arbre valide fait inclure une structure vide. Le site ne mentionne pas la hauteur d'arbre un tel, mais en fonction de la définition de la hauteur, il devrait également être 0.

Answer 1

hauteur d'un arbre dont la racine est défini comme longueur de la plus longue chemin simple feuille à racine

Dans le cas d'un arbre 2 nœud, il est clair que cette longueur est 1.

Dans le cas d'un 1 arbre de nœud (un arbre avec juste la racine), la longueur doit être égale à 0. (Il y a 0 bords sur le chemin de la feuille à la racine.)

Dans le cas d'un arbre 0 nœud, bien -1 n'a pas de sens. Il est un distance et doit avoir une valeur $ \ geq 0 $, mais ni est-il logique d'essayer de mesurer la longueur de null.

-1 est parfois choisie en raison de sa cohérence avec cette relation de récurrence pour la hauteur des noeuds: (qui est essentiellement le même que ce que vous avez publié ci-dessus)

height(null) = -1
height((v, left, right)) = max(height(left), height(right)) + 1

mais nous pourrions tout aussi facilement définir:

height((v, null, null)) = 0
height(null) = 0
height((v, left, right)) = max(height(left), height(right)) + 1

Answer 2

Toute constante fonctionne comme la hauteur de Empty, car seule la différence des hauteurs est important pour l'équilibre. Alors, pourquoi ne pas choisir 0?