06

TD 6

Exo 1

1)

A0

• On insère 8 dans F1 qui n’est pas pleine
• On insère 30 dans F2 qui n’est pas pleine

• On veut insérer 15 dans F2 qui est pleine (max valeurs, ordre )
  débordement:

  • On crée une nouvell feuille F3
  • On répartit les valeurs de F2 et la nouvelle valeur entre F2 et f3
  • On insère la + petite valeur de F3 dans le parent N1
• On insère 30 dans N1 qui n’est pas plein

A1

2)

On Insère 10 dans A1, dans F2 contenant , qui est pleine.

• On crée une nouvelle feuille F2a
• On réparti (10, 15, 20) entre F2 et F2a

• On insère la plus petite valeur de F2a dans NA
  On insère 20 dans N1 qui est pleine, débordement:
  Où va le noeud 20?

  • Créer un nouveau noeud N2
  • On réparti (10, 20, 30) entre N1, N2 et le parent de N1
  • On insère la valeur centrale 20 dans le parent de N1. Si N1 n’a pas de parent, en créer un. Nouveau noeud R.

A2

Exo 2

1)

• Intervalles: n4 doit contenir des valeurs n7 doit contenir des valeurs n6 doit contenir des valeurs n8 doit contenir des valeurs n10 doit contenir des valeurs n15 doit contenir des valeurs

Exo 3

1)

ordre 2,

A1

2)

A2

Bilan L, E:

• lire R, N1, F2
• écrire F2

3)

A3

• On insère 3 dans (1 | 2 | 5 | 6), qui devient (1 | 2 | 3 | 5 | 6),
• Débordement, on sépare en deux noeuds
• On insère la plus petite valeur de F1a: 5 dans dans N1 qui est plein
• On créé N1a
• répartir (5 | 8 | 18 | 32 | 40) entre N1 et N1a et R
• insérer 18 dans R

4)

Suppr 8 dans F2 qui contient seulement valeurs. Redistribution:

• à gauche (d’après l’énoncé). 6 passe de F1 à F2, on adapte N1

en conséquence.

A4

Bilan L, E:

• lire R, N1, F1, F2
• écrire F1, F2, N1

5)

Insertion simple. Suppression: On retire 52 de son bloc. 58 est tout seul. Redistribution à gauche impossible On distribue à droite. , on redistribue.
à gauche: N1 a plus de d valeurs, OK
On peut redistribuer les valeurs entre N1, N2 et R

6)

cf photo, à faire au propre

Page incomplète ou erronée? Contribuez sur le repo