Le degré et l'ordre sont-ils la même chose lorsque l'on se réfère à un arbre B

8

Je connais l' ordre des termes d'un arbre B. Récemment, j'ai entendu un nouveau terme: arbre B avec un degré minimum de 2.

Nous savons que le degré est lié à un nœud mais quel est le degré d'un arbre?
Le degré impose-t-il une sorte de restriction sur la hauteur d'un arbre B?

Deb
la source

Réponses:

10

Je ne pense pas que le degré d'un arbre soit un terme standard dans la théorie des graphes ni dans les structures de données. Un degré est généralement une propriété d'un nœud / sommet d'un graphe, qui indique le nombre de ses arêtes incidentes. Pour les arbres, vous ne considérez parfois que les bords pour les enfants.

Je suppose que "B-tree avec un degré minimum de 2" signifie que chaque nœud a au moins deux enfants. En d'autres termes, il s'agit d'une limite inférieure pour le nombre d'enfants. D'un autre côté, l'ordre d'un arbre B désigne le degré de nœud maximal, et est donc une borne supérieure.

A.Schulz
la source
2
Ouais. C'était le point. Degreereprésente la limite inférieure du nombre d'enfants. c'est-à-dire le nombre minimum possible. Alors que le Orderreprésente la limite supérieure du nombre d'enfants. c'est à dire. le nombre maximum possible. Merci.
h8pathak
1
Le degré est absolument un terme standard dans la théorie des graphes: le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes.
David Richerby
9

Un nœud B-Tree peut contenir plusieurs valeurs clés tandis qu'un nœud BST n'en contient qu'une. Il existe des limites inférieures et supérieures sur le nombre de clés qu'un nœud peut contenir. Ces bornes peuvent être exprimées en termes d'un entier fixe t>=2appelé degré minimum de l'arbre B.

  • Chaque nœud autre que la racine doit avoir au moins des t-1clés. Chaque nœud interne autre que la racine a donc au moins des tenfants.
  • Chaque nœud peut contenir au plus des 2t-1clés. Par conséquent, un nœud interne peut avoir au plus des 2tenfants. Nous disons qu'un nœud est plein s'il contient exactement des 2t-1clés.

Veuillez cliquer sur Ce lien pour avoir une excellente base sur B-Tree et Ce lien pour un algorithme de suivi et le plus facilement écrit des opérations de B-Tree.

Nasir
la source
5

Jusqu'à présent, j'ai vu trois façons de caractériser l'arbre B:

  1. Avec degré de l'arbre B t(soit minimum, comme dans le livre CLRS Algorithms , ou maximum comme dans B-tree Visualizer ).

    L'arbre B le plus simple se produit lorsque t=2. Chaque nœud interne a alors 2, 3 ou 4 enfants, et nous avons un arbre 2-3-4 .

    Le texte référencé dans la réponse de Nasir suit de près la définition de l'arbre B donnée dans les algorithmes avec une explication détaillée des propriétés minimales des degrés.

  2. Avec L et U paramètres, avec une borne inférieure (supérieure) sur le nombre d'enfants, le nœud interne est censé avoir (par exemple, un arbre B avec L=3,U=6 est équivalent à B-tree avec t=3 (les deux autorisant de 2 à 5 clés par nœud),

  3. Avec ordre de l'arbre B m, donnée par Knuth dans TAOCP, Vol. 3 de sorte que tout nœud interne ait entrem2 et m les enfants.

Résumer:

  • Avec la caractérisation des degrés, le nombre d'enfants autorisé est inévitablement [t,2t] intervalle,
  • tandis que L et U permet une spécification plus précise du nombre d'enfants (c'est-à-dire le nombre de clés par nœud autorisé).

En ce qui concerne la deuxième partie de la question d'OP, il y a le théorème 18.1 dans les algorithmes:

Si n1, alors pour tout n-arbre B clé T de hauteur h et diplôme minimum t2, hlogtn+12.

M. Tao
la source
4

L'ordre (m) de l'arbre B définit (max et min) no. d'enfants pour un nœud particulier.

Le degré (t) de l'arbre B définit (max et min) no. de clés pour un nœud particulier. Le degré est défini comme le degré minimum d'arbre B.

Un arbre B d'ordre m: Tous les nœuds internes à l'exception de la racine ont au plus m enfants non vides et au moins ⌈m / 2⌉ enfants non vides.

Un arbre B de degré (minimum) t:

  1. chaque nœud a au plus 2t-1 clés
  2. si le nœud n'est pas root, il a au moins t-1 clés.
nrj
la source
Bienvenue en informatique ! Notez que vous pouvez utiliser LaTeX ici pour composer les mathématiques d'une manière plus lisible. Voir ici pour une courte introduction.
FrankW
1

Degreereprésente la limite inférieure du nombre d'enfants qu'un nœud dans l'arbre B peut avoir (à l'exception de la racine). c'est-à-dire le nombre minimum d'enfants possible. Alors que le Orderreprésente la limite supérieure du nombre d'enfants. c'est à dire. le nombre maximum possible.

B Propriétés de l'arborescence par rapport à l'Ordre

B Propriétés de l'arborescence par rapport à l'ordre.

NOTE: Wikipedia indique également ces

Propriétés de l'arborescence B par rapport au degré

Propriétés de l'arbre B par rapport au degré

NOTE: These can also be found in the CLRS book

h8pathak
la source
1
Si vous souhaitez modifier votre réponse, veuillez utiliser le lien de modification et ne pas republier. De plus, veuillez ne pas utiliser les images comme contenu principal de votre message, car elles sont inaccessibles aux moteurs de recherche et aux malvoyants. Si vous allez utiliser une image, vous devez citer sa source.
David Richerby
1
Appuyé, veuillez transcrire votre image en texte.
Evil
0

Arbre B d'ordre 5 OU m = 5

max enfants = 5

enfants min = plafond (m / 2) = 3


Arbre B de degré 5 OU t = 5

touches max = 2t-1

touches min = t-1

Muhammad Rehan Qadri
la source
3
Veuillez ne pas simplement écrire une liste d'équations. Expliquez votre réponse pour qu'elle soit utile à la personne qui a posé la question.
David Richerby
1
Cette réponse m'a vraiment aidé.
h8pathak
0

Les terminologies des arbres B ne sont pas définies uniformément partout où je lis , mais la question ambiguë est quel est l'ordre d'un arbre B? et pas beaucoup sur le degré d'un B-Tree . Le degré provient de la théorie des graphes qui le définit comme la somme des degrés en degré et en dehors de ce nœud.

On peut en déduire que le degré est plus étroitement lié au nombre de pointeurs / enfant qu'un nœud B-Tree peut avoir au lieu des valeurs clés dans le nœud.

Selon Knuth et Michael J. Folk , un arbre B d'ordre m est un arbre dont chaque nœud a au plus m enfants. Donc, très vaguement, nous pouvons dire que les deux sont des termes plus ou moins équivalents dans le contexte de B-Tree.

Ritwik
la source