Je vais faire mon pinailleur mais les arbres rouge/noir ne sont pas des b-tree.
Dans un b-arbre, toutes les feuilles ont la même profondeur. En revanche, les nœuds ont un nombre variable de fils.
Dans un arbre binaire de recherche, tous les nœuds internes ont exactement deux fils mais les feuilles n'ont pas la même profondeur.
Les arbres rouge/noir sont des arbres binaires de recherche qui codent certaines classes de b-arbres (les 2-4 arbres).
Pour répondre à patrickg, les arbres binaires de recherche et les b-arbres de base sont des _dictionnaires. On veut pouvoir chercher, ajouter et retirer des éléments identifiés par une clef. Dans ces implémentations, les feuilles ne sont pas liées entre elles.
Mais on peut aussi vouloir faire des choses supplémentaires comme accéder efficacement
- au k-ième élément ;
- à un élément médiant ;
- à l'élément immédiatement après ou avant un élément donné.
Pour cela, on enrichi la structure et notamment pour accéder au prédécesseur ou au suivant, on relie les feuilles entre elles.
[^] # Re: Arbre B et B+
Posté par fmaz fmaz . En réponse à la dépêche Le noyau Linux est disponible en version 3.0. Évalué à 10.
Je vais faire mon pinailleur mais les arbres rouge/noir ne sont pas des b-tree.
Dans un b-arbre, toutes les feuilles ont la même profondeur. En revanche, les nœuds ont un nombre variable de fils.
Dans un arbre binaire de recherche, tous les nœuds internes ont exactement deux fils mais les feuilles n'ont pas la même profondeur.
Les arbres rouge/noir sont des arbres binaires de recherche qui codent certaines classes de b-arbres (les 2-4 arbres).
Pour répondre à patrickg, les arbres binaires de recherche et les b-arbres de base sont des _dictionnaires. On veut pouvoir chercher, ajouter et retirer des éléments identifiés par une clef. Dans ces implémentations, les feuilles ne sont pas liées entre elles.
Mais on peut aussi vouloir faire des choses supplémentaires comme accéder efficacement
- au k-ième élément ;
- à un élément médiant ;
- à l'élément immédiatement après ou avant un élément donné.
Pour cela, on enrichi la structure et notamment pour accéder au prédécesseur ou au suivant, on relie les feuilles entre elles.