Preuve que la hauteur d'un arbre de recherche binaire équilibré est log (n)

Binaire de l'algorithme de recherche prend log(n) le temps, en raison du fait que la hauteur de l'arbre (avec n nœuds) serait log(n).

Comment voulez-vous prouver?

source d'informationauteur Igor L.

  1. 8

    Supposons tout d'abord que l'arbre est complet il dispose de 2^N nœuds feuilles. Nous essayons de prouver que vous avez besoin de N étapes récursives pour une recherche binaire.

    À chaque récursion étape permet de réduire le nombre de candidats nœuds feuilles exactement par moitié (parce que notre arbre est complet). Cela signifie qu'après la N de moitié d'opérations il y a exactement un nœud candidat de gauche.

    Comme chaque récursion étape de notre algorithme recherche binaire correspond exactement à un niveau de hauteur la hauteur est exactement N.

    Généralisation à l'ensemble des arbres binaires équilibrés: Si l'arbre a moins de nœuds que 2^N nous pour vous ne pas besoin plus halvings. Nous pourrions avoir besoin de moins ou la même quantité, mais jamais plus.

  2. 12

    Maintenant, ici, je ne donne pas de démonstration mathématique. Essayer de comprendre le problème à l'aide du journal de la base 2. Journal2 est le sens normal de journal en informatique.

    Tout d'abord, comprenez qu'il est binaire logarithme (log2n) (logarithme à base 2).
    Par exemple,

    • le logarithme binaire de 1 est 0
    • le logarithme binaire de 2 est 1
    • le logarithme binaire de 3 est 1
    • le logarithme binaire de 4 est 2
    • le logarithme binaire de 5, 6, 7 est 2
    • le logarithme binaire de 8 à 15 est 3
    • le logarithme binaire de 16-31 est 4 et ainsi de suite.

    Pour chaque hauteur, le nombre de nœuds dans un arbre équilibré sont 

     Hauteur Nœuds Journal de calcul 
0 1 log21 = 0 
1 3 log23 = 1 
2 7 log27 = 2 
3 15 log215 = 3

    Envisager l'équilibre de l'arbre avec entre 8 et 15 nœuds (n'importe quel nombre, disons 10). Il va toujours à la hauteur de 3 log2 de n'importe quel nombre de 8 à 15 est 3.

    Dans un arbre binaire équilibré de la taille du problème à résoudre est divisé par deux à chaque itération. Donc à peu près log2n itérations sont nécessaires pour obtenir un problème de taille 1.

    J'espère que cette aide.

  3. 4

    En supposant que nous avons une arborescence complète pour travailler, nous pouvons dire qu'à la profondeur k, il y a 2k les nœuds. Vous pouvez le prouver à l'aide de simple induction, basée sur l'intuition que l'ajout d'un niveau supplémentaire à l'arbre va augmenter le nombre de nœuds dans l'arbre tout entier par le nombre de nœuds qui ont été dans le niveau précédent fois deux.

    La hauteur k de l'arbre est log(N), où N est le nombre de nœuds. Cela peut être déclaré comme

    log2(N) = k,

    et il est équivalent à

    N = 2k

    Pour le comprendre, voici un exemple:

    16 = 24 => log2(16) = 4

    La hauteur de l'arbre et le nombre de nœuds sont liés de façon exponentielle. En prenant le logarithme du nombre de nœuds permet simplement de revenir en arrière pour trouver la hauteur.

  4. 0

    Il suffit de regarder la preuve rigoureuse dans Knuth, Volume 3 - le Tri et la Recherche d'Algorithmes ... il le fait beaucoup plus rigoureux que quelqu'un d'autre je pense.

    http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming

    Vous pouvez le trouver dans toute bonne Science de l'Ordinateur de la bibliothèque et sur les étagères de nombreux (très) vieux geeks.