Moyenne par Niveau dans un Arbre Binaire : Question d’Entretien en Python

Introduction

Les arbres binaires sont des structures de données fondamentales en informatique, jouant un rôle crucial dans de nombreux algorithmes et applications. Un arbre binaire est une structure hiérarchique où chaque nœud a au maximum deux enfants, connus sous le nom de gauche et de droite. Ces arbres sont appréciés pour leur capacité à fournir un accès rapide et organisé aux données.

Une question courante en entretien technique consiste à calculer la moyenne des valeurs par niveau dans un arbre binaire. Ce type de problème évalue non seulement la compréhension des structures de données, mais aussi la capacité à appliquer les bons algorithmes pour traverser un arbre de manière efficace.

Comprendre l’Arbre Binaire

Structure d’un Arbre Binaire

Un arbre binaire est composé de plusieurs composants essentiels :

• Nœuds : Chaque unité de l’arbre contenant une valeur et des références à ses enfants.
• Racine : Le nœud de départ de l’arbre.
• Feuilles : Les nœuds qui n’ont pas d’enfants.
• Branches : Les connexions entre les nœuds.

Types d’Arbres Binaires

• Arbre Binaire Complet : Tous les niveaux, sauf éventuellement le dernier, sont complètement remplis, et tous les nœuds sont le plus à gauche possible.
• Arbre Binaire Parfait : Tous les nœuds internes ont exactement deux enfants et toutes les feuilles sont au même niveau.
• Arbre Binaire Équilibré : La différence de hauteur entre les sous-arbres gauche et droite de n’importe quel nœud est au maximum de un.

Représentation en Python

Pour commencer, définissons une classe Node pour représenter chaque nœud de notre arbre binaire.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Ensuite, une structure d’arbre binaire pourrait être mise en place ainsi :

class BinaryTree:
    def __init__(self, root_value):
        self.root = Node(root_value)

Approche pour Calculer la Moyenne par Niveau

Explication des Méthodes Possibles

• Traversée en largeur (BFS) : Parcourt l’arbre niveau par niveau, le candidat idéal pour ce problème, car il permet de traiter chaque niveau indépendamment.
• Traversée en profondeur (DFS) : Explore autant que possible un chemin descendant avant de revenir en arrière, moins pratique pour ce problème.

Choix de la Méthode Optimale

La méthode BFS est idéale ici car elle permet de maintenir la séparation des niveaux lors de la traversée, ce qui est essentiel pour calculer la moyenne des valeurs de chaque niveau.

Implémentation en Python

Mise en Place de la Structure de Données

Tout d’abord, établissons la classe pour notre arbre binaire et ajoutons une méthode pour ajouter des nœuds :

class BinaryTree:
    def __init__(self, root_value):
        self.root = Node(root_value)

    def insert(self, value):
        # Exemple simple d'insertion qui pourrait être raffiné selon vos besoins
        new_node = Node(value)
        queue = [self.root]
        while queue:
            current = queue.pop(0)
            if not current.left:
                current.left = new_node
                return
            else:
                queue.append(current.left)
            if not current.right:
                current.right = new_node
                return
            else:
                queue.append(current.right)

Implémentation de la Solution

Nous allons maintenant implémenter l’algorithme BFS pour calculer la moyenne par niveau.

from collections import deque

def average_of_levels(root):
    if not root:
        return []

    queue = deque([root])
    averages = []

    while queue:
        level_length = len(queue)
        level_sum = 0

        for _ in range(level_length):
            node = queue.popleft()
            level_sum += node.value

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        averages.append(level_sum / level_length)

    return averages

Code Complet avec Commentaires

Voici le code complet avec des commentaires expliquant chaque étape :

from collections import deque

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root_value):
        self.root = Node(root_value)

    def insert(self, value):
        new_node = Node(value)
        queue = [self.root]
        while queue:
            current = queue.pop(0)
            if not current.left:
                current.left = new_node
                return
            else:
                queue.append(current.left)
            if not current.right:
                current.right = new_node
                return
            else:
                queue.append(current.right)

def average_of_levels(root):
    if not root:
        return []

    queue = deque([root])
    averages = []

    while queue:
        level_length = len(queue)
        level_sum = 0

        for _ in range(level_length):
            node = queue.popleft()
            level_sum += node.value
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        averages.append(level_sum / level_length)

    return averages

# Exemple d'utilisation
bt = BinaryTree(3)
bt.insert(9)
bt.insert(20)
bt.insert(15)
bt.insert(7)
print(average_of_levels(bt.root))  # Résultat attendu: [3, 14.5, 11]

Analyse de Complexité

• Complexité Temporelle : L’algorithme parcourt chaque nœud une seule fois, ce qui donne une complexité de (O(n)), où (n) est le nombre de nœuds dans l’arbre.
• Complexité Spatiale : L’utilisation de la file d’attente nécessite (O(w)) espace supplémentaire, où (w) est la largeur maximale de l’arbre, ce qui correspond au nombre maximal de nœuds à n’importe quel niveau.

Tests et Validation

Pour assurer le bon fonctionnement de notre implémentation, nous devons tester différents scénarios :

import unittest

class TestAverageOfLevels(unittest.TestCase):

    def test_empty_tree(self):
        bt = BinaryTree(None)
        self.assertEqual(average_of_levels(bt.root), [])

    def test_single_node(self):
        bt = BinaryTree(1)
        self.assertEqual(average_of_levels(bt.root), [1])

    def test_balanced_tree(self):
        bt = BinaryTree(3)
        bt.insert(9)
        bt.insert(20)
        bt.insert(15)
        bt.insert(7)
        self.assertEqual(average_of_levels(bt.root), [3, 14.5, 11])

if __name__ == '__main__':
    unittest.main()

Conseils pour les Entrevues Techniques

• Approchez méthodiquement : Expliquez clairement vos actions, par exemple pourquoi BFS est préféré à DFS dans ce cas.
• Divisez et Conquérez : Commencez par construire la structure de données avant d’aborder l’algorithme, en expliquant chaque étape de votre processus.
• Soyez Prêt aux Questions Supplémentaires : Les intervieweurs peuvent changer les conditions ou ajouter des contraintes supplémentaires à votre problème.

Conclusion

Comprendre et manipuler les arbres binaires est essentiel pour de nombreux problèmes algorithmiques. En pratiquant avec différentes structures et approches, vous améliorerez vos compétences en résolution de problèmes et en programmation. Continuez à explorer et à développer votre compréhension des structures de données pour devenir un développeur plus efficace.

Ressources

• Visualisation des Structures de Données
• Automate votre Routine avec Python
• Introduction aux Algorithmes