Français
Menu

Structures de données et algorithmes

Un tas max, dans lequel la valeur de chaque parent est supérieure ou égale à celles de ses enfants, est stocké dans un tableau avec la racine en a[0]. On ajoute 45 au tas 50, 30, 40, 10, 20, 35 en le plaçant à la fin, puis en l'échangeant avec son parent tant qu'il est plus grand que celui-ci. Quel est le tableau obtenu ?

  1. A50, 30, 40, 10, 20, 35, 45
  2. B45, 30, 50, 10, 20, 35, 40
  3. C50, 30, 45, 10, 20, 35, 40
Afficher la réponse et l'explication

Réponse : C. 50, 30, 45, 10, 20, 35, 40

45 est placé en a[6], dont le parent est a[(6−1) ÷ 2] = a[2] = 40. Comme 45 > 40, ils sont échangés et 45 passe en a[2]. Son nouveau parent, a[0] = 50, est plus grand que 45, et le processus s'arrête, ce qui donne 50, 30, 45, 10, 20, 35, 40. Le nombre d'échanges est au plus égal à la hauteur de l'arbre : l'insertion se fait donc en O(log n), et le retrait du maximum aussi. C'est pourquoi les tas binaires servent couramment à implémenter les files de priorité.

S'entraîner sur ce thème Retour au thème

Autres questions sur Structures de données et algorithmes

  1. Quand on parcourt un arbre binaire de recherche dans l'ordre infixe (sous-arbre gauche, puis le nœud, puis sous-arbre droit), dans quel ordre se présentent les valeurs des nœuds visités ? On suppose toutes les valeurs distinctes.
  2. On insère dans cet ordre les valeurs 50, 30, 70, 20, 40, 60, 80 dans un arbre binaire de recherche vide. Dans quel ordre les nœuds sont-ils visités quand on parcourt l'arbre dans l'ordre postfixe (sous-arbre gauche, sous-arbre droit, puis le nœud) ?
  3. On insère dans cet ordre les valeurs 1, 2, 3, …, 1000 dans un arbre binaire de recherche vide (sans aucun rééquilibrage). Lors de la recherche de 1000 dans cet arbre, combien de nœuds sont comparés, à partir de la racine, avant de le trouver ?
  4. Quelle est la raison principale pour laquelle les arbres B (y compris les arbres B+), plutôt que les arbres binaires de recherche, sont largement utilisés pour les index des bases de données et des systèmes de fichiers ?
  5. Quelle est une façon appropriée de stocker en mémoire un graphe creux, c'est-à-dire un graphe ayant peu d'arêtes par rapport à son nombre de sommets, comme un réseau routier d'environ 1 million de sommets et 3 millions d'arêtes ?