Hauteur moyenne d'un arbre de recherche binaire

Comment calculer la hauteur moyenne d'un arbre de recherche binaire lors de l'ajout de 1000 aléatoire ints? Quelle est la hauteur moyenne?

  • C'est vraiment un problème intéressant - il me fait me demander si il y a une formule pour cela. L'un des facteurs déterminants serait si les entiers sont autorisés à correspondre. Si oui, quelle est la portée de l'ints (la probabilité de leur correspondant). Qui pourrait être un facteur affectant.
  • La réponse dépend du type d'arbre binaire que vous utilisez, bien que l'algorithme pour calculer la réponse, étant donné un arbre spécifique exemple, est le même.
  • Quel est le contexte, devoirs à la maison? Qu'entendez-vous par "random int'?
  • starblue: C'est une question à partir d'un vieux test. Par hasard ints je veux dire entiers aléatoires créés par l'intermédiaire d'un générateur de nombre aléatoire.
  • quel type de moyenne parlez-vous? la moyenne, la médiane ou la plage?
InformationsquelleAutor Mawnster | 2009-05-14
  1. 4

    Vous pouvez calculer la hauteur d'un arbre binaire à l'aide de cette définition récursive:

    height(empty) = 0
height(tree) = 1 + max(height(tree.left), height(tree.right))

    Une façon de mesurer empiriquement la moyenne de la hauteur d'un tel arbre est à plusieurs reprises de créer un arbre vide et ajouter 1000 aléatoire des éléments. Mesurer la hauteur de chaque essai à l'aide de la fonction ci-dessus, et la moyenne.

    Je soupçonne votre tâche est probablement de trouver une formule pour la hauteur moyenne d'un arbre binaire.

    • Ne faut pas de hauteur(à vide) soit -1, et la hauteur d'un arbre avec un seul point zéro?
    • Vous pouvez définir la hauteur de cette façon, si vous voulez, mais je pense que c'est plus naturel pour définir la hauteur d'un arbre vide à zéro.
    InformationsquelleAutor Greg Hewgill
  2. 10

    Cette question m'a demande si l'on peut définitivement faire ce travail sans générer les arbres.

    J'ai réussi à écrire une application qui pourrait calculer la réponse à la moyenne de la hauteur serait si vous avez ajouté tous les possible de permutation de N numéros uniques pour un naïvement mis en œuvre arbre binaire.

    Les réponses que j'ai eu sont dans ce graphique. (L'axe des X est le nombre d'éléments dans l'arbre, la ligne bleue est la moyenne de la hauteur, et la ligne rouge est la meilleure possible de la hauteur)

    Hauteur moyenne d'un arbre de recherche binaire

    N Moyenne Hauteur 
2 2 
16 7.039 
32 9.280 
64 11.679 
256 16.783 
343 17.896

    Granitebolshevik est juste: c'est possible, mais statistiquement peu probable qu'un naïvement mis en œuvre arbre sera à la hauteur optimale, sans supplément de l'équilibrage de la fonctionnalité.

    L'algorithme a une complexité de O(N^2), et il n'est pas assez rapide pour calculer réellement grand nombre.

    • Beau travail. Avez-vous essayé toute sorte d'extrapolation à partir des valeurs que vous avez obtenu pour N=1000? Brut extrapolation linéaire basée sur H = 14 (à propos de N=120) et H = 18 (à propos de N=350) suggère H = 29 (~ 560/230 * 4 + 19) à N=1000. La courbe est plus plat que cela, elle est probablement plus proche de la plage de 25 à 27, il me semble.
    • S'adapte à la 4.311 * ln(N) - 1.953 ln(ln(N)) + C très bien avec C environ -3. Formule à partir de goo.gl/cZMZoY.
    InformationsquelleAutor Andrew Shepherd
  3. 4

    Cela dépend si vous êtes en utilisant toute sorte d'équilibre de la structure en arborescence (comme un rouge-l'arbre noir). Depuis que vous êtes à l'insertion des nombres aléatoires dans un arbre binaire, il serait raisonnable de s'attendre à ce que la profondeur moyenne est d'environ log2(1000) - les valeurs 10 et 11 serait "normal". Je ne suis pas certain dans quelle mesure elle pourrait s'écarter de cela; pas d'une profondeur inférieure à 10 niveaux, éventuellement un peu plus profonde. Un cas extrême avec pas d'équilibrage serait 1000 profondes; il est peu probable de se produire avec des nombres aléatoires.

    InformationsquelleAutor Jonathan Leffler
  4. 3

    Il ne semble pas être une réponse simple à cette question, bien qu'il existe un certain nombre d'approximations numériques, par exemple:

    Devroye, Luc. "Une remarque sur la hauteur des arbres binaires." Journal de l'ACM (JACM) 33.3 (1986): 489-498.

    Reed, Bruce. "La hauteur d'un arbre de recherche binaire aléatoire." Journal de l'ACM (JACM) 50.3 (2003): 306-332.

    http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap13.htm

    Ces approximations prennent généralement la forme: A ln n - B ln ln n + C

    Où A~4.311 et B~1.953

    Donc probablement la chose la plus utile à dire, c'est que la taille moyenne d'insertions aléatoires est O(log n), mais si vous avez réellement besoin d'une approximation numérique je pense que (4.311 ln n - 1.953 ln ln n) serait assez proche pour n grand.

    Pour n=1000, qui donne sur 26 - ce qui correspond aux résultats expérimentaux rapportés ailleurs tout à fait bien.

    • Suivant @andré berger ci-dessus, il semble que C est autour de -3.
    InformationsquelleAutor Robert Ollington
  5. 1

    Cette question est en fait, délicat. La réponse ne sera pas 1000, parce que c'est improbable, mais log2(1000) est également improbable, mais plus encore en fonction de la façon dont l'arbre est cultivé.

    Si vous ajoutez un int en marchant si l'arbre alors naïvement ajoutant l'arbre sera pratiquement toujours être plus grand que log2(1000).

    Parler à un statisticien, parce que cela semble lié à la normale des distributions de probabilité. Ceux-ci sont générés par beaucoup de itéré événements aléatoires( à la tête de l'unité de droit, des queues idem à gauche), et la valeur d'un entier aléatoire parcourt l'arbre tel qu'il s'installe dans une feuille.

    InformationsquelleAutor user106822
  6. 0

    il dépend de l'ordre le sont ajoutés. Si vous commencez avec la plus petite valeur, alors l'arbre sera encore plus profond, car toutes les nouvelles valeurs seront ajoutées au droit de l'enfant de la STB. Si vous ajoutez de la valeur la plus grande d'abord, puis la gauche de l'enfant sera profonde tandis que la droite est vide.

    InformationsquelleAutor Josh Curren
  7. -2

    Peu importe de quel arbre vous êtes à l'aide de la hauteur moyenne sera log2(1000), comme quelqu'un l'a mentionné avant. Il est vrai que, selon l'ordre des numéros inséré la hauteur réelle peut varier, mais en supposant distribués au hasard des numéros, que vous mentionnez, alors la valeur réelle sera, le plus souvent, se rapproche de la valeur attendue (Qui, encore une fois, est log2(1000))

    • C'est incorrect. Pour un arbre binaire équilibré, la médiane de l'élément doit être le premier nœud ajouté. Il n'y aura qu'un 1/N de chance pour que cette prédiction, pour commencer, et même après cela, les sous-arbres de chaque côté doivent être équilibrés. Il est en fait une très faible probabilité qu'il sera log2(1000) par hasard, une petite fraction de 1/1000.
    • La hauteur moyenne sera O(log_2(1000)) -- les chiffres réels sont plus comme 4.3 ln(1000) - 1.9 ln(ln(n)) - 3. goo.gl/cZMZoY
    InformationsquelleAutor jrcalzada