Preuve de la profondeur de l'arbre de recherche équilibré

Question

Si T est un BST équilibré avec n éléments, L son sous-arbre gauche et R son bon, comment puis-je prouver que sa profondeur est inférieure ou égale à 2log (n) + 1?

Il y a une preuve par induction que j'ai mais je ne comprends pas.

(Je comprends que stackoverflow est principalement axée sur la programmation, mais je l'ai trouvé quelques questions sur les arbres binaires de recherche et a décidé de l'essayer, espère que je ne suis pas en train de faire quelque chose de pas bon.))

Answer 1

Par définition de « équilibrée », les profondeurs de tous les sous-arbres gauche et à droite du même noeud diffèrent au plus d'un. « Profondeur » est normalement défini comme « nombre de l'étape la plus longue marche de la racine de l'arbre vers le bas à feuille », donc par exemple un BST avec une racine et deux feuilles (trois éléments de la seule manière qu'ils peuvent être disposés dans un BST équilibré) est dit avoir de la profondeur d'un (semble que vous utilisez une définition légèrement différente qui lui donnerait la profondeur deux?), tout comme l'un avec une racine et une feuille (si cette feuille est sous-arbre gauche ou à droite de la racine ne fait aucune différence), tandis que l'un avec juste une racine qui est aussi une feuille (un seul élément) aurait la profondeur 0. (Il n'y a pas BST avec zéro éléments).

Donc, pour n <= 3 éléments, appelant D (n), la profondeur de l'arbre comme défini ci-dessus, clairement D(n) < log(n) + 1 (avec log signifiant logarithme en base 2) par l'inspection, depuis 1 = D(2) < log(2) + 1 = 2 (et 1 = D(3) pour lesquels l'ERS de l'inégalité, log(3) + 1, est en fait > 2) et 0 = D(1) < log(1) + 1 = 1 - ce qui nous donne la base d'induction

.

Pour compléter la preuve par induction, nous devons montrer que si D(k) < log(k) + 1 pour tous k < n, il suit aussi que D(n) < log(n) + 1.

Si n est impair sous-arbre, clairement à gauche et à droite ont des éléments (n-1)/2 chacun, et l'arbre a une profondeur 1 plus que les sous-arbres; mais D(n) = 1 + D((n-1)/2) < 1 + 1 + log((n-1)/2) alors (par l'hypothèse d'induction) = 1 + log(n-1) (depuis log((n-1)/2) = log(n-1) - 1) et donc a fortiori < 1 + log(n), QED.

Si n est même vous suivez les mêmes étapes avec log(n) au lieu de log(n-1) et sans la finition « a fortiori », et la preuve en est encore.

Answer 2

Votre réponse est vrai si l'arbre binaire équilibré est terminé, le nombre d'éléments dans l'arbre secondaire à droite et à gauche peut être (n-1) / 2, mais si elle est incomplète, le nombre d'éléments n'a pas besoin d'être (n-1) / 2 en dernier niveau peut avoir différents éléments