Arbre balancé

Arbre B

Schéma définissant un arbre B.

Un arbre B (appelé aussi B-arbre par analogie au terme anglais « B-tree ») est un arbre équilibré qui est principalement mis en œuvre dans les mécanismes de gestion de bases de données et de systèmes de fichiers. Il stocke les données sous une forme triée et permet une exécution des opérations d'insertion et de suppression en temps amorti logarithmique.

Le principe général est de permettre aux nœuds de posséder plus d'une clé ; cela minimise la taille de l'arbre et réduit le nombre opérations d'équilibrage. De plus un B-arbre grandit à partir de la racine, contrairement à un arbre binaire de recherche qui pousse à partir des feuilles.

Le créateur des arbres B, Rudolf Bayer, n'a pas explicité la signification du "B". L'explication la plus fréquente est que le B correspond au terme anglais "balanced" (en français : équilibré). Cependant il pourrait aussi découler de "Bayer", du nom du créateur, ou de "Boeing", du nom de la firme pour laquelle le créateur travaillait (Boeing Scientific Research Labs).

Sommaire

Structure

Soient L et U deux entiers naturels non nuls tels que L ≤ U. On définit alors un L-U arbre B[1] de la manière suivante : chaque nœud sauf la racine possède au moins L−1 clés (appelées aussi éléments), au plus U−1 clés et au plus U fils[2]. Pour chaque nœud interne – nœud qui n’est pas une feuille –, le nombre de fils est toujours égal au nombre de clés augmenté d’une unité. Si n est le nombre de fils, alors on parle de n-nœud. Un L-U arbre ne contient que des n-nœuds avec L ≤ n ≤ U. Souvent on choisit la configuration L = t et U = 2 × t : t est appelé le degré minimal de l’arbre B.

De plus la construction des arbres B implique qu’un arbre B est toujours équilibré. Chaque clé d’un nœud interne est en fait une borne qui distingue les sous-arbres de ce nœud. Par exemple, si un nœud a 3 fils – lesquels constituent les racines respectives de trois sous-arbres : sous-arbre gauche, sous-arbre du milieu et sous-arbre droit –, alors il a 2 clés notées c1 et c2 qui délimitent les clés de chaque sous-arbre : les clés du sous-arbre gauche seront inférieures à c1 ; les clés du sous-arbre du milieu seront comprises entre c1 et c2 ; les clés du sous-arbre droit seront supérieures à c2.

Opérations

Recherche

La recherche est effectuée de la même manière que dans un arbre binaire de recherche. Partant de la racine, on parcourt récursivement l’arbre ; à chaque nœud, on choisit le sous-arbre fils dont les clés sont comprises entre les mêmes bornes que celles de la clé recherchée.

Insertion

L’insertion nécessite tout d’abord de chercher le nœud où la nouvelle clé devrait être insérée, et l’insérer. La suite se déroule récursivement, selon qu’un nœud ait ou non trop de clés : s’il possède un nombre acceptable de clés, on ne fait rien ; autrement on le transforme en deux nœuds, chacun possédant un nombre minimum de clés, puis on fait « remonter » la clé du milieu qui est alors insérée dans le nœud père. Ce dernier peut du coup se retrouver avec un nombre excessif de fils ; le procédé se poursuit ainsi jusqu’à ce que l’on atteigne la racine. Si celle-ci doit être divisée, on fait « remonter » la clé du milieu dans une nouvelle racine, laquelle génèrera comme nœuds fils les deux nœuds créés à partir de l’ancienne racine, à l’instar de l'étape précédente. Pour que l’opération soit possible, on remarque qu’il faut que U ≥ 2 L ; sinon les nouveaux nœuds ne possèderont pas suffisamment de clés.

Une variante consiste à éclater préventivement chaque nœud « plein » (possédant le nombre maximal de clés) rencontré lors de la recherche du nœud où se réalisera l'insertion. De cette manière on évite une remontée dans l'arbre, puisque l'on assure que le père d'un nœud à scinder en deux peut accueillir une clé supplémentaire. La contrepartie en est un légère augmentation de la hauteur moyenne de l'arbre.

Suppression

On doit d’abord chercher la clé à supprimer, et la supprimer du nœud qui la contient.

  • Si le nœud est interne, on procède de manière similaire aux arbres binaires de recherche en recherchant la clé k la plus à gauche dans le sous-arbre droit de la clé à supprimer ou la plus à droite dans le sous-arbre gauche. Cette clé k appartient à une feuille. On peut la permuter avec la clé à supprimer, que l’on supprime ensuite. Comme elle appartient à une feuille, on se ramène au cas suivant.
  • Si le nœud est une feuille, soit il possède encore suffisamment de clés et l’algorithme termine, soit il dispose de moins de L−1 clés et on se trouve dans l’une des deux situations suivantes :
    • soit un de ses frères à droite ou à gauche possède suffisamment de clés pour pouvoir en "passer" une à la feuille en question : dans ce cas cette clé remplace la clé qui sépare les deux sous-arbres dans l’arbre père, qui va elle même dans la feuille en question ;
    • soit aucun de ses frères n’a suffisamment de clés : dans ce cas, le père fait passer une de ses clés dans un des deux (ou le seul) frères pour permettre à la feuille de fusionner avec celui-ci. Ceci peut cependant conduire le père à ne plus avoir suffisamment de clés. On réitère alors l’algorithme : si le nœud a un frère avec suffisamment de clés, la clé la plus proche va être échangée avec la clé du père, puis la clé du père et ses nouveaux descendants sont ramenés dans le nœud qui a besoin d’une clé ; sinon on effectue une fusion à l’aide d’une clé du père et ainsi de suite. Si l’on arrive à la racine et qu’elle possède moins de L éléments, on fusionne ses deux fils pour donner une nouvelle racine.

Remarques

  • La plupart du temps, la configuration est telle que U = 2 L. On parle alors d’arbre B d'ordre L.
  • Les arbres 2-3-4 sont les structures de données d’arbre B les plus utilisées : ils correspondent en fait à des 2-4 arbres B ou arbres B d’ordre 2.

Variantes

L’arbre B+ diffère légèrement de l’arbre B, en ceci que toutes les données sont stockées exclusivement dans des feuilles. D’autres variantes existent également, telles que l’arbre B*.

Annexes

Bibliographie

  • (en) Rudolf Bayer, Binary B-Trees for Virtual Memory, ACM-SIGFIDET Workshop 1971, San Diego, California, Session 5B, p. 219-235.
  • (en) Rudolf Bayer et McCreight, E. M. Organization and Maintenance of Large Ordered Indexes. Acta Informatica 1, 173-189, 1972.

Notes et références

  1. Lire : « L U arbre B ». L-U représente une expression de liaison, et non de soustraction, entre bornes numériques.
  2. « L−1 » et « U−1 » figurent ici des expressions de soustraction.

Voir aussi

Articles connexes

Liens externes

  • (en) Slady.net : animation sous forme d’applet Java permettant de construire visuellement des arbres B.
  • (it)(en)B-tree GUI : Spataro Fabrizio e Todaro Michelangelo – Emulatore Java BTree – BTree Java Emulator.
  • Portail de l’informatique Portail de l’informatique

Ce document provient de « Arbre B ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Arbre balancé de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • ARBRE — La distinction entre arbre et herbe remonte à une antiquité éloignée. Théophraste (vers 300 av. J. C.) en avait déjà fait la base de sa classification des végétaux, non sans quelque raison à en croire d’actuels botanistes. On sait que Hutchinson… …   Encyclopédie Universelle

  • ARBRE — s. m. Végétal ligneux dont la tige, plus ou moins élevée, ne se garnit ordinairement de branches et de feuilles qu à une certaine hauteur. Grand arbre. Gros arbre. Arbre haut et droit. Arbre tortu, branchu, touffu. Arbre sec. Arbre mort. Arbre… …   Dictionnaire de l'Academie Francaise, 7eme edition (1835)

  • ARBRE — n. m. Végétal ligneux dont la tige, plus ou moins élevée, ne se garnit ordinairement de branches et de feuilles qu’à une certaine hauteur. Grand arbre. Bel arbre. Arbre haut et droit. Arbre branchu, touffu. Arbre mort. Arbre qui se dépouille.… …   Dictionnaire de l'Academie Francaise, 8eme edition (1935)

  • arbre — (ar br ) s. m. 1°   Grand végétal ligneux, et, dans le langage spécial de la botanique, végétal dont le tronc ligneux s élève à plus de six mètres. •   Le troisième tomba d un arbre Que lui même il voulut enter, LA FONT. Fabl. XI, 8. •   On peut… …   Dictionnaire de la Langue Française d'Émile Littré

  • balance — (ba lan s ) s. f. 1°   Instrument composé de deux bassins ou plateaux suspendus à un fléau, et destiné à faire connaître le poids d un corps. Les bassins, la languette, l arbre d une balance. •   Grands compositeurs de riens, pesant gravement des …   Dictionnaire de la Langue Française d'Émile Littré

  • BALANCE — s. f. Instrument dont on se sert pour peser : il est composé de deux bassins ou plateaux suspendus à un fléau, et destinés, l un à recevoir le poids, l autre l objet que l on veut peser. Balance juste. Fausse balance. De bonnes balances. Les… …   Dictionnaire de l'Academie Francaise, 7eme edition (1835)

  • BALANCE — n. f. Instrument dont on se sert pour peser, composé de deux bassins ou plateaux suspendus à un fléau et destinés, l’un à recevoir le poids, l’autre l’objet que l’on veut peser. Balance juste. Fausse balance. De bonnes balances. Les bassins, les… …   Dictionnaire de l'Academie Francaise, 8eme edition (1935)

  • Olivier (arbre) — Olivier européen Pour les articles homonymes, voir Olivier …   Wikipédia en Français

  • Maison de l'Arbre d'Or — (Maison des Brasseurs) Présentation Période ou style Architecture baroque Type Maison de corporation Architecte …   Wikipédia en Français

  • Maison de la Balance — Présentation Période ou style Architecture baroque Type Maison particulière Date de construction 1704 …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”