Structures de données récursives

Reading time5 min

En bref

Résumé de l’article

Dans cet article, nous vous présentons ce qu’est une structure de données récursive. Une structure de données récursive est une structure qui peut être définie à partir de l’une au moins de ses sous-structures, permettant ainsi de créer des structures complexes à partir d’éléments plus simples. Nous verrons comment les structures de données récursives sont utilisées pour représenter des listes chaînées et des arbres binaires, et comment elles peuvent être implémentées en Python.

Points clés

  • Certaines structures de données peuvent également être définies récursivement.

  • Une liste chaînée est une structure de données où les éléments sont stockés dans des emplacements mémoires séparés et liés entre eux à l’aide de références.

  • Un arbre binaire est une structure de données où chaque nœud a au plus deux enfants, et peut être représenté par des nœuds composés de trois parties : données, lien vers l’enfant gauche et lien vers l’enfant droit. Chaque lien vers un descendant pointe vers un emplacement vide ou un (sous-)arbre binaire.

Contenu de l’article

1 — Structures de données récursives

La récursivité ne s’applique pas seulement aux fonctions mais également à la représentation des données (les classes en programmation). Tout comme dans une méthode récursive, il y a (au moins) un appel à cette méthode,
dans une classe récursive, il y a une (ou plusieurs) variable dont le type est la classe elle-même.

Comme pour les fonctions récursives, deux cas sont nécessaires pour définir une structure de données récursive :

  • Cas de base – La variable de la classe est fixée à une valeur de base (p-ex, None), c’est-à-dire qu’elle ne fait pas référence à une instance du même type.
  • Cas récursif – La variable de la classe est fixée à une instance de la même classe, c’est-à-dire qu’elle fait référence à un objet du même type.
class RecursiveClass:
    """
    A class that demonstrates a recursive structure.
    It can either be empty (base case) or contain a reference to another instance of the same class (recursive case).
    """
    def __init__(self, value=None):
        self.value = value
        self.next = None  # This can point to another instance of RecursiveClass

2 — Liste chaînée

L’exemple le plus courant est la liste chaînée.

Une liste chaînée est une structure de données où les éléments sont stockés dans des emplacements mémoires séparés et liés entre eux à l’aide de références. Chaque nœud a deux parties :

  • Données – L’élément à stocker dans le nœud.
  • Lien – Une référence vers le nœud suivant.

Le cas de base est le nœud qui ne fait référence à aucun autre nœud (sa référence est définie à None), c’est-à-dire qu’il est le dernier de la liste. Le cas récursif est le nœud qui fait référence à un autre nœud du même type, ce qui permet de créer une liste chaînée.

linkedlist.svg
Exemple de liste chaînée (src: wikipedia)

La classe Node

En programmation, pour déclarer une liste chaînée, on utilise une classe Node récursive. Celle-ci contient non seulement des données, mais aussi une référence vers un autre objet de la même classe.

from typing import Any

type Node = Node

class Node:
    """
    A class representing a node in a linked list.
    Each node contains data and a reference to the next node.
    """
    def __init__(self, data: Any):
        """
        Initializes a new node with the given data and no next node.
        :param data: The data to be stored in the node.
        """
        self.data = data
        self.next = None
    
    def get_data(self):
        """
        Returns the data stored in the node.
        :return: The data of the node.
        """
        return self.data
    
    def get_next(self):
        """
        Returns the next node in the linked list.
        :return: The next node, or None if there is no next node.
        """
        return self.next

    def set_next(self, next_node: Node) :
        """
        Sets the next node in the linked list.
        :param next_node: The next node to be linked.
        """
        self.next = next_node

if __name__ == "__main__":
    # Example usage
    node1 = Node(12)
    node2 = Node(99)
    node3 = Node(37)
    node1.set_next(node2)  # node1 points to node2
    node2.set_next(node3)  # node2 points to node3

    print(node1.get_data())  # Output: 12
    print(node1.get_next().get_data())  # Output: 99
    print(node2.get_next().get_data())  # Output: 37

Cette structure est efficace pour insérer et supprimer des éléments car elle ne nécessite pas d’adapter la taille ou de décaler les éléments, comme dans un tableau.

La classe LinkedList

Pour simplifier l’usage des nœuds et en cacher l’existence, on peut créer une classe qui gère la liste chaînée dans son ensemble, en fournissant des méthodes pour ajouter des éléments, supprimer des éléments, et parcourir la liste. La notion de nœud devient alors une implémentation interne de la classe, et l’utilisateur de la classe n’a pas besoin de connaître les détails de sa structure.

# We suppose that the Node class is defined as above
# and is available in the same file or imported.
class LinkedList:
    """
    A class representing a singly linked list.
    It contains methods to add nodes and traverse the list.
    """
    def __init__(self):
        """
        Initializes an empty linked list with no head node.
        """
        self.head = None

    def add(self, data : Any):
        """
        Adds the given data to the end of the list.
        """
        new_node = Node(data)
        if not self.head: # If the list is empty, set the new node as the head
            self.head = new_node
            return
        current = self.head
        while current.get_next(): # Look for the last node
            current = current.get_next()
        current.set_next(new_node)

    def traverse(self):
        """
        Traverses the list and prints the data of each node.
        """
        current = self.head
        while current:
            print(current.get_data())
            current = current.get_next()

# Example usage
if __name__ == "__main__":
    linked_list = LinkedList()
    linked_list.add("Brest")
    linked_list.add("Nantes")
    linked_list.add("Rennes")
    print("Les campus de l'IMT Atlantique sont :")
    linked_list.traverse()
    # Output:
    # Brest
    # Nantes
    # Rennes

Les méthodes de la classe LinkedList tirent parti de la structure récursive des nœuds pour ajouter des éléments et parcourir la liste.

Cycle

Lorsque le dernier élément pointe vers le premier élément, la liste chaînée devient une liste chaînée circulaire. Les notions de début et de fin de la liste deviennent alors floues, car il n’y a pas de nœud “dernier” qui pointe vers None. En maintenant une référence vers le dernier nœud, on peut toujours ajouter de nouveaux nœuds à la fin ou au début de la liste efficacement. Il faut alors être vigilant pour éviter les boucles infinies lors du parcours de la liste mais cette structure est utile pour représenter des files d’attente circulaires ou des jeux en tour de rôle.

3 — Arbre binaire

Un autre exemple de structure de données récursive est l’arbre binaire. Un arbre binaire est une structure de données où chaque nœud a au plus deux enfants, appelés enfant gauche et enfant droit. Chaque nœud peut être vu comme un sous-arbre, et l’arbre entier est un ensemble de nœuds reliés entre eux.

binarytree.svg
Exemple d’arbre binaire (src: wikipedia)

La classe Node pour un arbre binaire peut être définie comme suit :

from typing import Any
type BinaryTreeNode = BinaryTreeNode

class BinaryTreeNode:
    """
    A class representing a node in a binary tree.
    Each node contains data and references to the left and right children.
    """

    def __init__(self, data : Any):
        """
        Initializes a binary tree node with the given data.
        """
        self.data = data
        self.left = None
        self.right = None

    def get_data(self) -> Any:
        """
        Returns the data stored in the node.
        :return: The data of the node.
        """
        return self.data    
    
    def get_left(self) -> BinaryTreeNode:
        """
        Returns the left child of the node.
        :return: The left child node, or None if there is no left child.
        """
        return self.left

    def get_right(self) -> BinaryTreeNode:
        """
        Returns the right child of the node.
        :return: The right child node, or None if there is no right child.
        """
        return self.right
    
    def set_left(self, left_node : BinaryTreeNode):
        """
        Sets the left child of the node.
        :param left_node: The left child node to be linked.
        """
        self.left = left_node

    def set_right(self, right_node : BinaryTreeNode):
        """
        Sets the right child of the node.
        :param right_node: The right child node to be linked.
        """
        self.right = right_node

if __name__ == "__main__":
    # Example usage
    root = BinaryTreeNode(8)
    left_child = BinaryTreeNode(3)
    right_child = BinaryTreeNode(10)
    root.set_left(left_child)  # Set left child
    root.set_right(right_child)  # Set right child
    # ...
    print("Root data:", root.get_data())

Le parcours d’un arbre représenté de cette manière est simple à exprimer à l’aide d’une fonction récursive. Il est, par exemple, possible de parcourir un arbre binaire en profondeur (DFS) en visitant d’abord le nœud racine, puis en parcourant récursivement l’enfant gauche (et donc son sous-arbre), et enfin l’enfant droit. Ou de le parcourir en largeur (BFS) en visitant d’abord les nœuds de la même profondeur avant de descendre dans l’arbre.

Remarque

L’arbre binaire présenté ci-dessus est particulier puisqu’il est ordonné, c’est-à-dire que les nœuds sont organisés de manière à ce que les valeurs des nœuds de l’enfant gauche soient inférieures à celles du nœud parent, et celles de l’enfant droit soient supérieures. Cette structure est appelée arbre binaire de recherche (ou BST pour Binary Search Tree).

Pour aller plus loin