Arbres binaires complets et quasi-complets

Michel Billaud

27 septembre 2022

1 Motivation

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.

https://twitter.com/traumath/status/1573684526559141890

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

2 Définitions

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.

2.1 Arbres binaires, définitions inductives

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

2.2 Arbres complets

Un arbre t est dit complet de hauteur h (notation : ctree(t,h)) :

Il est évident que

2.3 Arbres quasi-complets

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 -

2.4 Caractérisation inductive des arbres quasi-complets

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).

3 Indice de la racine

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.

3.1 Taille du sous-arbre de gauche d’un arbre quasi-complet

Nous avons vu que les arbres quasi-complets de hauteur h étaient de taille comprise entre 2h12^{h-1} et 2h12^h - 1.

Inversement, la hauteur d’un arbre quasi-complet de taille n sera donc h=log2n+1h = \lfloor log_2 n\rfloor + 1

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 2h1n<2h1+2h22^{h-1} \leq n < 2^{h-1} + 2^{h-2}, 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 n(2h21)1=n2h2n - (2^{h-2} - 1) - 1 = n - 2^{h-2}.

Second cas

Dans le cas où n2h1+2h2n \geq 2^{h-1} + 2^{h-2}

le sous-arbre de gauche est complet, et est donc de taille 2h112^{h-1} - 1

3.2 En résumé

Soit n la taille de la liste (supposée non vide)

3.3 Vérification par programme

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
    h = math.floor(math.log(n, 2)) + 1
    # 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 ()

show_markdown_table(16)

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

4 Programmation

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
    root = start + index_racine(end - start)
    return Tree(l[root],
                mkTree_r(l, start, root),
                mkTree_r(l, root+1, end))