Bonjour, j'ai un soucis avec la première question. Doit on utiliser la fonction hauteur btree_height pour définir les arguments du prédicat p ?
Bonjour,
On peut utiliser la fonction btree_height, mais cela risque de conduire à une fonction is_balanced inefficace. En effet, cela demanderait de lancer des calculs de hauteur sur tous les sous-arbres de l'arbre d'entrée. Mais chacun de ces calculs de hauteur provoque lui-même, par ses propres appels récursifs, des calculs de hauteur dans les sous-arbres. Autrement dit, on relancerait plusieurs fois les mêmes calculs.
Pour avoir un algorithme s'exécutant en temps linéaire par rapport à la taille de l'arbre d'entrée, une idée possible est d'écrire une fonction auxiliaire qui calcule un couple (h, b) en chaque noeud de l'arbre, composé de :
- la hauteur h du sous-arbre en ce noeud,
- un booléen b qui dit si le sous-arbre en ce noeud est d'équilibre contrôlé.
On calcule donc la hauteur h (comme pour la fonction btree_height) et, à la fois, l'information b qui nous intéresse. Cela permet de ne faire qu'un seul passage en temps constant sur chaque noeud de l'arbre (et donc un calcul proportionnel à la taille de l'arbre).