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

26

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?

Forrest Gump
la source
2
Avez-vous essayé de prouver l'une ou l'autre direction? Quelles sont vos conclusions?
Raphael

Réponses:

17

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 .kkk1
Raphael
la source
Je viens de réaliser que le fait le plus fort peut être utilisé pour simplifier de manière inutile les preuves auxquelles je fais un lien.
Raphael
C'est peut-être une bonne idée d'incorporer cette réalisation dans votre réponse.
Lézard discret
@Discretelizard Vous voulez dire, les autres réponses?
Raphael
Oh, je ne savais pas que ces liens étaient des réponses en informatique ou qu'ils étaient vos réponses. Eh bien, en tout cas, tout ce que je voulais dire, c'est que ce pourrait être une bonne idée d'écrire les preuves simplifiées. Vos réponses liées semblent alors être l'endroit approprié.
Lézard discret