Pourquoi la hauteur minimale d'un arbre binaire ?

Dans ma classe Java, nous apprenons la complexité de différents types de collections.

Bientôt, nous discuterons des arbres binaires, que j'ai lus. Le livre déclare que la hauteur minimale d'un arbre binaire est , mais n'offre aucune explication supplémentaire.$\log_2(n+1) - 1$

Quelqu'un peut-il expliquer pourquoi?

Un arbre binaire a 1 ou 2 enfants aux nœuds non foliaires et 0 nœud aux nœuds foliaires. Soit nœuds dans un arbre et nous devons les disposer de telle manière qu'ils forment toujours un arbre binaire valide.$n$

Sans prouver, j'affirme que pour maximiser la hauteur, les nœuds donnés doivent être disposés de façon linéaire, c'est-à-dire que chaque nœud non-feuille doit avoir un seul enfant:

                              O 1
                              |
                              O 2
                              |
                              O 3
                              |
                              O 4
                              |
                              O 5
                              |
                              O 6
                              |
                              O 7
                              |
                              O 8

Ici, la formule pour calculer la relation de hauteur en termes de nombre de nœuds est simple. Si est la hauteur de l'arbre, alors .h = n - $h$$h = n-1$

Maintenant, si nous essayons de construire un arbre binaire de nœuds avec une hauteur minimale (toujours réductible à un arbre binaire complet), nous devons emballer autant de nœuds que possible dans les niveaux supérieurs, avant de passer au niveau suivant. Ainsi, l'arbre prend la forme de l'arbre suivant:$n$

                              O
                              |1
                              |
                       O------+-----O
                       |2           |3
                       |            |
                   O---+---O    O---+----O
                   |4      |5    6        7
                   |       |
               O---+--O    O
                8      9    10

Commençons par un cas particulier, .$n = 2^m - 1$

Nous savons que,

$$2^0 + 2^1 + 2^2 + ... + 2^{m-1} = 2^m - 1$$

De plus, il est facile de prouver qu'un niveau peut contenir au maximum nœuds.2 $i$$2^i$

En utilisant ce résultat dans la somme ci-dessus, nous constatons que pour chaque niveau , de à , il existe un terme correspondant dans l'expansion de . Cela implique qu'un arbre binaire complet nœuds est complètement rempli et a une hauteur, , où hauteur d'un arbre binaire complet avec nœuds.0 m 2 i - 1 2 m - 1 2 m - 1 h ( 2 m - 1 ) = m - 1 h ( n ) = $i$$0$$m$$2^{i-1}$$2^m - 1$$2^m - 1$$h(2^m-1) = m-1$$h(n) =$$n$

En utilisant ce résultat, , car l'arbre avec nœuds est complètement rempli et donc un arbre avec nœuds doit accueillir le nœud supplémentaire au niveau suivant , augmentant la hauteur de 1 de à .2 m - 1 ( 2 m - 1 ) + 1 = 2 m m m - 1 $h(2^m) = m$$2^m-1$$(2^m-1)+1 = 2^m$$m$$m-1$$m$

Jusqu'à présent, nous avons prouvé, ainsi que,h ( 2 m + 1 ) = m + 1 h ( 2 m + 1 - 1 ) =

$$h(2^m) = m,$$ $$h(2^{m+1}) = m+1$$ $$h(2^{m+1} -1) = m$$

Ainsi, m ≤ h ( n ) < m + $\forall n \in \mathbb{Z}, 2^m \leq n < 2^{m+1}$

$$m \leq h(n) < m+1$$

Mais, en prenant log (base 2) des deux côtés, m = ⌊ log 2 ( n )

$$m \leq \log_2(n) < m+1$$ $$m = \lfloor \log_2(n) \rfloor$$

Ainsi,h ( n ) = m = ⌊ log 2 ( n ) $\forall n, n \in [2^m, 2^{m+1})$

$$h(n) = m = \lfloor \log_2(n) \rfloor$$

Et nous pouvons généraliser ce résultat utilisant l'induction.$\forall n \in \mathbb{Z}$

PS: Le livre qui indique la hauteur d'un arbre binaire complet comme n'est pas valide pour tous car donnerait des valeurs non intégrales pour la plupart des entiers (c'est-à-dire pour tous sauf parfait) arbres binaires), mais la hauteur d'un arbre est purement intégrale.$\log_2(n+1)-1$$n$$\log_2(n)$$n$

Je suppose que par , vous voulez dire le nombre total de nœuds dans l'arbre binaire. La hauteur (ou la profondeur) d'un arbre binaire est la longueur du chemin du nœud racine (le nœud sans parents) au nœud feuille le plus profond. Pour rendre cette hauteur minimale, l'arborescence doit être entièrement saturée (sauf pour le dernier niveau), c'est-à-dire que si un niveau spécifique a des nœuds avec des enfants, tous les nœuds du niveau parent doivent avoir deux enfants.$n$

Ainsi, un arbre binaire entièrement saturé à niveaux aura nœuds maximum et aura une profondeur de . Ainsi, si nous avons la profondeur d'un arbre binaire, nous pouvons très facilement trouver le nombre maximum de nœuds (ce qui se produit lorsque l'arbre est complètement saturé). Si vous vous souvenez de vos classes d'algèbre, ce n'est qu'une série géométrique et peut donc être représentée comme ceci:$4$$1+1\cdot2+1\cdot2\cdot2+1\cdot2\cdot2\cdot2$$3$

$$\text{nodes}=1+2+2^{2}+2^{3}+...+2^{\text{depth}}=\sum_{k=0}^{\text{depth}} 2^{k}=\frac{1-2^{\text{depth}+1}}{1-2}.$$

$$\text{nodes}=2^{\text{depth}+1}-1,$$ $$\begin{eqnarray} \text{nodes}+1&=&2^{\text{depth}+1}\\ \log_{2}(\text{nodes}+1)&=&\log_{2}(2^{\text{depth}+1})=\text{depth}+1\\ \log_{2}(\text{nodes}+1)-1&=&\text{depth}. \end{eqnarray}$$

Pour garder la hauteur minimale, il est facile de voir que nous devons remplir tous les niveaux sauf éventuellement le dernier. Pourquoi? sinon, nous pourrions simplement déplacer les nœuds du dernier niveau dans des emplacements vides dans les niveaux supérieurs.

Maintenant, imaginez que j'ai un nombre indéterminé de haricots et que je vous donne un haricot à la fois et vous demande de construire un arbre binaire avec une hauteur minimale possible. Je pourrais manquer de beans au moment où vous avez complètement rempli le dernier niveau ou au moins avoir un bean dans le dernier niveau. Disons que vous avez la hauteur de votre arbre h à ce stade.

$$2^{0}+2^{1}+2^{2}+2^{3}+\dots+2^{h}=2^{h+1}-1 \leq n\,.$$ $$h = \lg(n+1)-1\,.$$