Minimum et maximum de la hauteur des arbres binaires, arbres 2-3-4 et B des arbres

Quelqu'un peut veuillez me dire comment vous trouvez le min/max hauteur de B arbres 2-3-4 arbres binaires de recherche arbres?

Grâce.

PS: Ce n'est pas de devoirs.

Qu'entendez-vous par min hauteur?
Dupe, demandé par la même personne! stackoverflow.com/questions/2574249/...

OriginalL'auteur zorgo | 2010-05-12

  1. 5

    Minimale et Maximale de la hauteur d'un arbre 2-4

    Pour hauteur maximale d'un arbre 2-4, nous allons avoir une clé par nœud, d'où il sera se comporter comme un Arbre de Recherche Binaire.

    clés au niveau 0 = 1

    clés au niveau 1 = 2

    clés au niveau 2 = 4 et ainsi de suite. . . .

    Ajoutant nombre total de clés à chaque niveau, nous obtenons un GP sur des problèmes qui nous permettra d'obtenir la hauteur maximale de l'arbre.

    Donc, hauteur = log2(n+1) - 1

    De le résoudre pour un total de 10^6 touches nous aurons :

    ⇒ 1 * (2^0+ 2^1 + 2^2 + . .. . . . +2^h) = 10^6

    ⇒ 1*(2^(h+1) - 1) = 10^6

    ⇒ h = log2(10^6 + 1) - 1

    ⇒ Hauteur maximale de 2 à 4 de l'arbre avec un total de 10^6 touches est de 19

    Pour hauteur minimale d'un arbre 2-4, nous allons avoir trois clés(nombre maximum possible) par nœud.

    clés au niveau 0 = 3

    clés au niveau 1 = 3*(4)

    clés au niveau 2 = 3*(4^2) et ainsi de suite . . .

    Donc, hauteur = log4(n+1) - 1

    Ajoutant nombre total de clés à chaque niveau, nous allons obtenir un GP sur des problèmes qui nous permettra d'obtenir la hauteur minimale. De le résoudre pour un total de 10^6 touches, nous obtenons:

    ⇒ 3 * (4^0+ 4^1 + 4^2 + . .. . . . +4^h) = 10^6

    ⇒ (4^(h+1) - 1) = 10^6

    ⇒ h = log4(10^6 + 1) - 1

    ⇒ Hauteur minimale de 2 à 4 de l'arbre est de 9

    Binaires De Recherche Arbres

    Pour la hauteur maximale, nous avons une chaîne continue de longueur n(nombre total de nœuds) donc de nous donner une hauteur égale à n-1(comme la hauteur commence à partir de 0).

    Pour un minimum de hauteur, nous aurons un parfait équilibre de l'arbre et comme résolu plus tôt nous aurons une hauteur égale à log2(n+1)-1

    OriginalL'auteur smutneja03

  2. 1

    Si vous voulez savoir la longueur de la plus longue branche que vous avez à parcourir l'ensemble de l'arbre de maintien de la note de "la plus longue branche jusqu'à présent".

    OriginalL'auteur bitc

  3. 0
    1. Démarrer à partir d'un noeud racine et de regarder pour ses enfants

    2. si elle est d'avoir un nœud enfant alors
      Sélectionnez la plus à gauche de l'enfant et de stocker d'autres dans toute une structure de données

      d'autre

      si la hauteur de ce nœud est au maximum jusqu'à maintenant

      définir comme max

      fin de si
      fin si

    3. Boucle par tous les nœuds de l'arbre et de ce que vous obtenez est la hauteur maximale

    Similaire, vous pouvez le faire pour un minimum de

    OriginalL'auteur Himadri

  4. 0

    La hauteur minimale d'un arbre binaire est O(log n), le maximum est de O(n), en fonction de la façon équilibrée, il est.

    Wikipedia a une belle peu sur le B de l'Arbre Hauteurs.

    Je ne suis pas familier avec 2-3-4 arbres, mais selon wikipedia, ils ont les mêmes isométrie rouge-noir et B des arbres, de sorte que le lien ci-dessus devrait vous renseigner.

    OriginalL'auteur Rubys

  5. 0

    Comme pour B, les arbres, les min/max hauteurs dépendent du facteur de branchement de mise en œuvre choisie.

    OriginalL'auteur Daniel Harms

  6. 0

    Arbres binaires ont une hauteur maximale de n quand l'entrée est insérée dans l'ordre, la hauteur minimale est de cours log_2(n) lorsque l'arbre est parfaitement équilibré. Quand l'entrée est insérée dans un ordre aléatoire, la hauteur moyenne est d'environ 1.39 * log_2 n.

    Je ne suis pas trop familier avec les b des arbres, mais la hauteur minimale est de cours log_m(n) parfaitement équilibré (m est le nombre d'enfants par nœud). Selon Wikipédia, la hauteur maximale est de log_(m/2)(n).

    2-3 arbres ont une hauteur maximale de log_2(n) lorsque l'arbre se compose de seulement 2 nœuds et la hauteur minimale est d'environ log_3(n) [~0.631 log_2(n)] lorsque l'arbre se compose de seulement de 3 nœuds.

    OriginalL'auteur Samuel