Deux définitions d'arbres binaires équilibrés

J'ai vu deux définitions d'arbres binaires équilibrés, qui me semblent différentes.

1. Un arbre binaire est équilibré si, pour chaque nœud, il considère que le nombre de nœuds internes dans le sous-arbre gauche et le nombre de nœuds internes dans le sous-arbre droit diffèrent d'au plus 1.

2. Un arbre binaire est équilibré si pour deux feuilles la différence de profondeur est au plus de 1.

Est-ce que chaque arbre qui satisfait def. 1 satisfait également def. 2? Et l'inverse?

La définition 1. est également connue sous le nom d' équilibre pondéral ¹ et la définition 2. d' équilibre taille .

L'équilibre de la taille n'implique pas l'équilibre du poids; des exemples sont à la fois AVL et Red-Black-Trees. Voir ici et ici pour les preuves, respectivement.

L'équilibre du poids implique cependant l'équilibre de la taille. Cela peut être prouvé en montrant le fait plus fort suivant par induction (sur-hauteur): un arbre équilibré en poids est complet à tous les niveaux sauf le plus profond². L'argument essentiel de l'étape inductive est que les sous-arbres ne peuvent pas avoir une différence de hauteur de plus d'un parce que - tous deux ayant la propriété revendiquée par hypothèse d'induction - ils ne seraient alors pas équilibrés en poids.

1. L'article donne une définition différente et plus générale.
2. En d'autres termes, un tel arbre de hauteur sans les feuilles au niveau k est un arbre parfait de hauteur k - 1 .$k$$k$$k-1$