Français
Menu

Structures de données et algorithmes

Un tas binaire est stocké dans un tableau a[0], a[1], a[2], … avec la racine en a[0], en remplissant chaque niveau de gauche à droite à partir du haut. Quels sont les enfants et le parent de a[4] ?

  1. AEnfants a[9] et a[10] ; parent a[1]
  2. BEnfants a[8] et a[9] ; parent a[2]
  3. CEnfants a[9] et a[10] ; parent a[2]
Afficher la réponse et l'explication

Réponse : A. Enfants a[9] et a[10] ; parent a[1]

Avec la racine en a[0], les enfants de a[i] sont a[2i+1] et a[2i+2], et son parent est a[(i−1) ÷ 2, arrondi à l'entier inférieur]. Pour i = 4, les enfants sont a[9] et a[10], et le parent est a[(4−1) ÷ 2] = a[1]. Avec la racine en a[1], les enfants sont a[2i] et a[2i+1] et le parent est a[i ÷ 2] : il est donc important de vérifier quelle convention est utilisée. Comme un tas est un arbre binaire complet, il peut être stocké dans un tableau sans pointeurs, et les parents et les enfants se trouvent par simple calcul d'indices.

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

Autres questions sur Structures de données et algorithmes

  1. 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 ?
  2. 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.
  3. 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) ?
  4. 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 ?
  5. 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 ?