Récapitulatif algo

A faire !

A faire !

• Connaître le principe de la recherche en largeur
• Savoir donner l'ordre des noeuds lors de cet exemple
• Etre capable de fournir l'algorithme de cette lecture en utilisant une File
• Pouvoir implémenter cet algorithme en Python en itératif ou en récursif

• Donner le résultat de log2(2^X)
• Dire si la hauteur h est de l'ordre de n ou de l'ordre de log2(n) pour un Arbre binaire complet
• Dire si la hauteur h est de l'ordre de n ou de l'ordre de log2(n) pour un Arbre binaire filiforme
• Pouvoir en déduire un encadrement grossier de la hauteur dans le cas d'un arbre binaire quelconque.
• Connaître le principe de la numérotation binaire des noeuds d'un AB
• Savoir trouver le numéro d'un fils gauche ou d'un fils droite
• Savoir trouver le numéro d'un parent d'un noeud
• Parvenir à implémenter cette numérotation dans un tableau de taille connue

• Que veut dire ABR ?
• Qu'est-ce qu'un ABR complet ?
• Qu'est-ce qu'un ABR équilibré ?
• Comment doivent être les clés de tous les noeuds du sous-arbre gauche d'un ABR ?
• Comment doivent être les clés de tous les noeuds du sous-arbre droite d'un ABR ?
• Pourquoi les recherches sur les clés sont-elles nécessairement ciblées dans un ABR ?
• Quel est le coût en fonction de la hauteur pour une recherche dans un ABR ?
• Quel est le coût en fonction de la taille pour une recherche dans un ABR complet ou équilibré ?
• Comprendre le principe de l'insertion dans un ABR.
• Fournir l'algorithme permettant d'insérer un nouveau noeud dans un ABR.
• Fournir deux versions de l'algorithme de recherche dans un ABR :
  • une version itérative
  • une version récursive