B-Tree - Pourquoi ne peut-il pas y avoir un noeud avec un nombre pair de clés?

J'essaye d'implémenter un B-Tree selon le chapitre "B-Trees" dans "Introduction to Algorithms".B-Tree - Pourquoi ne peut-il pas y avoir un noeud avec un nombre pair de clés?

Ce que je ne comprends pas bien est le « degré minimal ». Dans le livre, il est indiqué que le degré est un nombre qui exprime la limite inférieure/supérieure pour le nombre de clés d'un nœud peut contenir. Il ne dit plus que:

Chaque nœud stocke non root au moins t - 1 clés et a t enfants.
Chaque nœud stocke au plus 2*t - 1 touches et a 2*t enfants.

Ainsi, vous obtenez pour t = 2:

t - 1 = 1 touches et t = 2 enfants
2*t - 1 = 3 clés et 4 enfants

Pour t = 3

t - 1 = 2 touches et t = 3 ch fants
2*t - 1 = 5 touches et 6 enfants

Maintenant, voici le problème: Il semble que les noeuds dans un certain nombre de clés impair B-Tree ne peut stocker un quand ils sont pleins.

Pourquoi ne peut pas être là un nœud avec, disons au plus 4 clés et 5 enfants? Cela a-t-il quelque chose à voir avec la division du nœud?

Source

2010-08-18 helpermethod

'dans" Introduction aux algorithmes "' - voilà! _Which_ "Introduction aux algorithmes": Auteurs? Éditeurs? La langue? ISBN? Hyperlien? – greybeard

Il semble que les nœuds d'un arbre B ne peuvent stocker qu'un nombre impair de clés?

Certainement pas. Les nombres que vous avez écrits sont respectivement le nombre minimum et maximum de clés, donc pour t = 2, les nœuds avec 1, 2, 3 clés sont autorisés. Pour t = 3, les nœuds avec 2, 3, 4, 5 clés sont autorisés.

De plus, la racine de l'arbre est autorisé à avoir seulement 1 clé.

Il est possible de définir (et mettre en œuvre) des arbres qui ont par exemple. 1 ou 2 clés dans un nœud (ce que l'on appelle 2-3 arbres). La raison pour laquelle les arbres B sont définis pour en accommoder un de plus, c'est que cela conduit à des performances plus rapides. En particulier, cela permet de supprimer et d'insérer les opérations O(1) (comptage des opérations de fractionnement et d'assemblage) amorties.

Source

2010-08-18 22:23:46 jpalecek

Bien sûr, vous avez raison ... ce que je voulais dire était le cas lorsque le nœud est plein - il ne peut alors contenir que des nombres impairs de nœuds. Je ne comprends toujours pas pourquoi cela conduit à de meilleures performances, voir le commentaire de ire_and-curses. – helpermethod

@Helper Méthode: Ok, donc je pense que le deuxième paragraphe répond à votre question - avez-vous besoin d'une preuve formelle? – jpalecek

@jpalecek J'ai édité la question d'origine, mais l'OP m'a demandé quand un nœud est plein: pourquoi un nœud complet ne peut pas avoir un nombre pair de clés? Telle était la question pas si claire du PO, de l'OMI. – nbro

ce n'est pas impossible mais sous-optimal. comment divisez-vous un noeud avec un nombre impair d'enfants?

Source

2010-08-18 21:52:36 Javier

Je ne comprends pas cet argument.Vous prenez l'enfant médian, le déplacez dans le parent, puis affectez tous les enfants à la droite de la médiane à un nouveau sous-noeud du parent. –

@ire_and_curses Je pense que vous vous êtes trompé entre les clés et les nœuds enfants ... – nbro

B-Tree - Pourquoi ne peut-il pas y avoir un noeud avec un nombre pair de clés?

Répondre

Questions connexes