Aller au contenu

Arbre binaire additif⚓︎

Représentation des arbres

On représente les arbres binaires ainsi :

  • l'arbre vide est représenté par None,

  • un arbre non vide est représenté par un tuple (sous-arbre gauche, valeur, sous-arbre droit).

Ainsi le tuple ((None, 6, None), 15, None) représente l'arbre suivant :

graph TD
    R(15) --> A(6)
    R --> B( )
    A --> C( )
    A --> D( )

On souhaite construire des arbres binaires parfaits « additifs ». Dans ces arbres, la valeur d'un nœud intérieur est toujours égale à la somme des valeurs de ses enfants.

graph TD
    R(19) --> A(8)
    R --> B(11)
    A --> C(3)
    A --> D(5)
    B --> E(7)
    B --> F(4)
    C --> G( )
    C --> H( )
    D --> I( )
    D --> J( )
    E --> K( )
    E --> L( )
    F --> M( )
    F --> N( )

Arbre binaire parfait

On rappelle qu'un arbre binaire est dit parfait lorsque tous ses niveaux sont complètement remplis.

On peut en déduire qu'un arbre binaire parfait de hauteur \(h\) compte \(2^{h-1}\) feuilles.

On demande d'écrire la fonction arbre_additif prenant en argument la liste valeurs contenant les valeurs des feuilles et renvoyant l'arbre correspondant.

On garantit que le nombre d'éléments de valeurs est une puissance de \(2\). Ces éléments sont tous des nombres entiers.

Exemples

🐍 Console Python
>>> arbre_additif([6])
(None, 6, None)
>>> arbre_additif([6, 9])
((None, 6, None), 15, (None, 9, None))
>>> arbre_additif([3, 5, 7, 4])
(((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))
# Testsbksl-nlassert arbrepy-undadditif([6]) == (None, 6, None)bksl-nlassert arbrepy-undadditif([6, 9]) == ((None, 6, None), 15, (None, 9, None))bksl-nlassert arbrepy-undadditif([3, 5, 7, 4]) == (bksl-nl ((None, 3, None), 8, (None, 5, None)),bksl-nl 19,bksl-nl ((None, 7, None), 11, (None, 4, None)),bksl-nl)bksl-nlbksl-nlbksl-nl# Tests supplémentairesbksl-nlfrom random import randrangebksl-nlbksl-nldef py-undpy-undarbrepy-undadditifpy-undpy-und(valeurs):bksl-nl noeuds = [(None, x, None) for x in valeurs]bksl-nlbksl-nl while len(noeuds) > 1:bksl-nl prochains = []bksl-nl for i in range(0, len(noeuds), 2):bksl-nl gauche = noeuds[i]bksl-nl droite = noeuds[i + 1]bksl-nl prochains.append((gauche, gauche[1] + droite[1], droite))bksl-nl noeuds = prochainsbksl-nlbksl-nl return noeuds[0]bksl-nlbksl-nlfor py-und in range(10):bksl-nl nbpy-undfeuilles = 2 py-strpy-str randrange(3, 10)bksl-nl valeurs = [randrange(-100, 101) for py-und in range(nbpy-undfeuilles)]bksl-nl attendu = py-undpy-undarbrepy-undadditifpy-undpy-und(valeurs)bksl-nl assert arbrepy-undadditif(valeurs) == attendu, f"Erreur avec {valeurs}"bksl-nl ∞/∞

def arbrepy-undadditif(valeurs):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert arbrepy-undadditif([6]) == (None, 6, None)bksl-nlassert arbrepy-undadditif([6, 9]) == ((None, 6, None), 15, (None, 9, None))bksl-nlassert arbrepy-undadditif([3, 5, 7, 4]) == (bksl-nl ((None, 3, None), 8, (None, 5, None)),bksl-nl 19,bksl-nl ((None, 7, None), 11, (None, 4, None)),bksl-nl)bksl-nlbksl-nldef arbrepy-undadditif(valeurs):bksl-nl noeuds = [(None, x, None) for x in valeurs]bksl-nlbksl-nl while len(noeuds) > 1:bksl-nl prochains = []bksl-nl for i in range(0, len(noeuds), 2):bksl-nl gauche = noeuds[i]bksl-nl droite = noeuds[i + 1]bksl-nl prochains.append((gauche, gauche[1] + droite[1], droite))bksl-nl noeuds = prochainsbksl-nlbksl-nl return noeuds[0]bksl-nlbksl-nl

A

On procède ici de manière itérative en partant des feuilles.

Une autre approche est de procéder de façon récursive :

🐍 Script Python
def arbre_additif_rec(valeurs):
    if len(valeurs) == 1:
        return (None, valeurs[0], None)

    milieu = len(valeurs) // 2
    return (
        arbre_additif_rec(valeurs[:milieu]),
        sum(valeurs),
        arbre_additif_rec(valeurs[milieu:])
        )

Cette façon de procéder présente toutefois plusieurs inconvénients :

  • les différentes tranches valeurs[:milieu] et valeurs[milieu:] occupent de la mémoire,
  • les sommes des valeurs sont calculées à plusieurs reprises (lors du première appel on additionne toutes les valeurs, les deux premiers appels récursifs additionnent à nouveau les valeurs du début et de la fin de la liste, etc).

Z

Retour en haut de la page