Table des matières
xxix
9.5.3 Arbres-B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 392
9.6 Exercices .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 396
A Rappels algorithmiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 399
A.1 Arbres binaires.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 400
A.1.1 Le type de données Arbre binaire . . . . . . . .. . . . . . . . . . . . . . . . . . . . 400
A.1.2 Parcours en profondeur .. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 400
A.1.3 Parcours en largeur, ou hiérarchique.. . . . .. . . . . . . . . . . . . . . . . . . . 402
A.1.4 Rotations d’arbres binaires .. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 404
A.2 Arbres binaires de recherche .. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 405
A.2.1 Recherche .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 406
A.2.2 Insertion aux feuilles . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 407
A.2.3 Suppression d’une clé . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 408
A.2.4 Coupure et insertion à la racine .. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 409
A.2.5 Fusion de deux arbres binaires de recherche
et suppression .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 411
A.2.6 Arbres binaires de recherche randomisés.. . . . . . . . . . . . . . . . . . . . 415
A.3 Arbres-B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 417
A.3.1 Le type de données Arbre-B (prudent) . . .. . . . . . . . . . . . . . . . . . . . 417
A.3.2 Recherche dans un arbre-B.. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 419
A.3.3 Insertion d’une clé . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 419
A.4 Arbres quadrants.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 425
A.5 Tries .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 425
A.5.1 Les types de données . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 425
A.5.2 Insertion .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 429
A.5.3 Recherche .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 430
A.5.4 Parcours d’un trie . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 430
A.5.5 Suppression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 431
A.5.6 Tri radix .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 433
A.6 Tris par comparaisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 437
A.6.1 Tri rapide .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 437
A.6.2 Recherche par rang . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 439
A.6.3 Tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 440
B Rappels mathématiques : combinatoire . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 447
B.1 Structures combinatoires .. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 447
B.1.1 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 447
B.1.2 Classes étiquetées.. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 448
B.2 Méthode symbolique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 449
B.2.1 Constructions sur les classes non étiquetées . . . . . . . . . . . . . . . . . 449
B.2.2 Constructions sur les classes étiquetées . .. . . . . . . . . . . . . . . . . . . . 450
B.3 Analyse complexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 452
B.3.1 Séries de la variable complexe .. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 452
B.3.2 Séries bivariées . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 454
B.3.3 Asymptotique de coefficients et formule de Taylor .. . . . . . . . . 455
xxix
9.5.3 Arbres-B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 392
9.6 Exercices .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 396
A Rappels algorithmiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 399
A.1 Arbres binaires.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 400
A.1.1 Le type de données Arbre binaire . . . . . . . .. . . . . . . . . . . . . . . . . . . . 400
A.1.2 Parcours en profondeur .. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 400
A.1.3 Parcours en largeur, ou hiérarchique.. . . . .. . . . . . . . . . . . . . . . . . . . 402
A.1.4 Rotations d’arbres binaires .. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 404
A.2 Arbres binaires de recherche .. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 405
A.2.1 Recherche .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 406
A.2.2 Insertion aux feuilles . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 407
A.2.3 Suppression d’une clé . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 408
A.2.4 Coupure et insertion à la racine .. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 409
A.2.5 Fusion de deux arbres binaires de recherche
et suppression .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 411
A.2.6 Arbres binaires de recherche randomisés.. . . . . . . . . . . . . . . . . . . . 415
A.3 Arbres-B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 417
A.3.1 Le type de données Arbre-B (prudent) . . .. . . . . . . . . . . . . . . . . . . . 417
A.3.2 Recherche dans un arbre-B.. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 419
A.3.3 Insertion d’une clé . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 419
A.4 Arbres quadrants.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 425
A.5 Tries .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 425
A.5.1 Les types de données . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 425
A.5.2 Insertion .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 429
A.5.3 Recherche .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 430
A.5.4 Parcours d’un trie . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 430
A.5.5 Suppression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 431
A.5.6 Tri radix .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 433
A.6 Tris par comparaisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 437
A.6.1 Tri rapide .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 437
A.6.2 Recherche par rang . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 439
A.6.3 Tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 440
B Rappels mathématiques : combinatoire . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 447
B.1 Structures combinatoires .. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 447
B.1.1 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 447
B.1.2 Classes étiquetées.. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 448
B.2 Méthode symbolique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 449
B.2.1 Constructions sur les classes non étiquetées . . . . . . . . . . . . . . . . . 449
B.2.2 Constructions sur les classes étiquetées . .. . . . . . . . . . . . . . . . . . . . 450
B.3 Analyse complexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 452
B.3.1 Séries de la variable complexe .. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 452
B.3.2 Séries bivariées . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 454
B.3.3 Asymptotique de coefficients et formule de Taylor .. . . . . . . . . 455