27 septembre 2022
Cette note vient d’un exercice proposé sur Twitter, à propos de la construction d’un arbre binaire de recherche quasi-complet contenant les valeurs d’une liste déjà ordonnée.
Notions intuitives :
Une solution possible est de
La difficulté est de calculer l’indice de la racine à partir de la taille. Ce n’est pas simplement la moitié : pour une liste de taille 5 à 7, cet indice est 3
0 1 1 2 3 3 3
/ / \ / \ / \ / \ / \
0 0 2 1 3 1 4 1 4 1 5
/ / \ / \ / / \ / \
0 0 2 0 2 5 0 2 4 6
arbres binaires quasi-complets pour les listes de 0 à N, pour N=0..6
Dans la mesure où s’intéresse seulement au calcul de l’indice de la racine, on se contente de considérer les “formes” d’arbres binaires, ne contenant pas de valeurs.
Un arbre binaire est
Tree :=
| empty
| cons(left:Tree, right:Tree)
La taille d’un arbre et sa hauteur se définissent aisément par induction
Pour la hauteur, on choisit la convention d’une représentation du nombre de niveaux de sommets
Remarque : il y a un lien entre taille et hauteur
Un arbre t est dit complet de hauteur h (notation : ctree(t,h)) :
Il est évident que
Intuitivement, la dernière rangée d’un arbre quasi-complet de hauteur h
Si on regarde les exemples d’arbres quasi-complets de hauteur h=3 déjà présentés plus haut
1 2 3 3
/ \ / \ / \ / \
0 2 1 3 1 4 1 4
/ / \ / \ / / \ / \
1 0 2 0 2 5 0 2 4 6
on constate - et c’est une propriété générale -
En observant davantage les exemples, on remarque aussi que
Ceci conduit à une caractérisation inductive : un arbre t est quasi-complet de hauteur h - notation qctree(t, h) :
Intuitivement, il y a deux cas parce que les feuilles de la dernière rangée peuvent “commencer à manquer” dans le sous-arbre de gauche (dans ce cas il n’y en n’a pas dans le sous-arbre de droite) ou dans le sous-arbre de droite (et donc le sous-arbre de gauche est complet).
Rappel du problème : il s’agit, à partir d’une liste (qu’on peut supposer non vide) ordonnée de valeurs, de determiner l’indice de la valeur qui sera la racine de l’arbre binaire de recherche quasi-complet contenant les valeurs de la liste.
Ce problème se ramène à déterminer la taille du sous-arbre de gauche de cet arbre, en fonction de la taille de la liste.
Nous avons vu que les arbres quasi-complets de hauteur h étaient de taille comprise entre et .
Inversement, la hauteur d’un arbre quasi-complet de taille n sera donc
Considérons maintenant la taille du sous-arbre gauche d’un arbre binaire quasi-complet de taille n, avec n évidemment strictement supérieur à 1, faute de quoi il n’a pas de sous-arbre gauche.
Premier cas
La première moitié des arbres quasi-complets de hauteur h, sont tels que , et sont composés
La taille de l’arbre de gauche s’obtient en soustrayant de n la taille du sous-arbre de droite et 1 (la racine), soit .
Second cas
Dans le cas où
le sous-arbre de gauche est complet, et est donc de taille
Soit n la taille de la liste (supposée non vide)
Le programme Python ci-dessous produit une table (au format Markdown) des indices des racines en fonction de la taille de la liste
import math
def index_racine(n):
if n == 1:
return 0
= math.floor(math.log(n, 2)) + 1
h # print ( "n = %s, h = %s\n" % (n, h))
if n < 2**(h-1) + 2**(h-2):
return n - 2**(h-2)
else:
return 2**(h-1) - 1
def show_markdown_table(taille_max):
print ("|taille", end = "|")
for i in range(1, taille_max+1):
print ("%s" % i, end = "|" )
print ()
print ("|-", end="|")
for i in range(1, taille_max+1):
print ("-", end = "|" )
print ()
print("|indice", end="|")
for i in range(1, taille_max+1):
print ("%s" % index_racine(i), end="|" )
print ()
16) show_markdown_table(
Résultat affiché
taille | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
indice | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 4 | 5 | 6 | 7 | 7 | 7 | 7 | 7 | 8 |
Le code suivant
print(toString(mkTree([0, 11, 22, 33, 44, 55])))
affiche une représentation textuelle de l’arbre construit à partir de la liste à 6 éléments [0, 11, 22, 33, 44, 55]
Résultat
node(node(node(., 0, .), 11, node(., 22, .)), 33, node(node(., 44, .), 55, .))
Structure de données “arbre”
Cette structure récursive est déclarée comme une classe “Plain Old Data”, sans méthodes, pour ne pas effaroucher les débutants
class Tree:
def __init__(self, value, left, right):
self.value = value
self.left = left
self.right = right
Le calcul de la représentation d’un arbre sous forme de chaîne est récursif:
def toString(t):
if t == None:
return "."
else:
return "node(%s, %s, %s)" % (toString(t.left),
t.value, toString(t.right))
Construction d’un arbre
Pour éviter d’extraire des sous-listes, la fonction mkTree
est un “lanceur” pour une autre (récursive) à qui on indique les indices de début et fin (non comprise) de la portion de liste à considérer
def mkTree(l):
return mkTree_r(l, 0, len(l))
Enfin, la fonction récursive fait le job, en partageant au besoin la sous-liste à traiter
# construit l'ABR quasi-complet de la sous-liste
# de l, d'indices start (inclus) à end (exclus)
def mkTree_r(l, start, end):
if start == end:
return None
= start + index_racine(end - start)
root return Tree(l[root],
mkTree_r(l, start, root),+1, end)) mkTree_r(l, root