Comprendre les structures de données non linéaires en 5 minutes

Les structures de données non linéaires sont grandement sous-estimées, voire complètement ignorées, par beaucoup de développeurs. C’est vraiment une erreur. On avait discuté des structures de données linéaires la semaine dernière, c’était le bien. Aujourd’hui, on fait un saut de l’ange dans les structures de données non linéaires.

Toujours plus

La semaine dernière, on a tout compris des stacks, des queues ou encore des linked lists. Si tu as pas suivi le premier article, va jeter un œil au moins 5 minutes. Ça va être galère à suivre sinon celui d’aujourd’hui.

C’est légèrement plus complexe, mais je réitère ce que je te disais dans l’article précédent. Tu as, ou tu vas avoir, un véritable avantage à maîtriser tout ça le plus rapidement possible. Les structures de données non linéaires, spécifiquement, vont te permettre de résoudre des problèmes encore plus pointus.

C’est quoi la différence entre structure de données linéaires et non linéaires déjà ? Excellente question.

Coté linéaire, la donnée est organisée de façon séquentielle. Dans un array par exemple, chaque élément du tableau vient l’un après l’autre. C’est facile à mettre en oeuvre et tu peux consulter tous les éléments en un passage (une boucle).

Côté non linéaire, la donnée n’est pas organisée de façon séquentielle. Tu vas avoir des liens hiérarchiques, ou simplement des liens spéciaux, qui relient les éléments qui composent la structure. Tu ne pourras pas parcourir toutes les données en une boucle et c’est pas le but d’ailleurs. C’est pas clair ? OK, regardons notre premier exemple.

Tree (arbre)

C’est quoi ?

Un arbre c’est un ensemble de nœuds qui sont liés de façon hiérarchique. Il y a le nœud racine au sommet qui est lié à ses nœuds enfants. Nœuds enfants qui peuvent eux-mêmes avoir autant d’enfants qu’ils veulent et ainsi de suite. Chaque nœud ne peut avoir qu’un seul parent. D’où le côté hiérarchique de cette structure de données.

Comme image mentale tu peux tout de suite imaginer un vrai arbre, comme dans la nature, mais à l’envers. La racine au-dessus, les branches représentant les nœuds enfants et les feuilles représentant les nœuds à l’extrémité. Allez, je me lance dans mon art maison.

Concernant cet arbre, on dit qu’il a une taille de 9, car il a 9 nœuds. On dit qu’il a une hauteur de 4, car il a quatre niveaux de profondeur. On dit aussi que cet arbre est sublime, car esthétiquement c’est bien dessiné.

Les arbres sont utilisés partout. De l’arbre hiérarchique de ta boite jusqu’à arborescence de tes fichiers en passant par les systèmes de tournois, ça donne le tournis tellement ils sont partout.

Y’a plein d’arbres différents, c’est la jungle informatique. Tu te doutes bien, on va pas tous les faire. Aujourd’hui, on va se concentrer seulement sur les arbres binaires pour la bonne raison que c’est la version la plus simple. La particularité d’un arbre binaire c’est que chaque nœud ne peut avoir que deux enfants maximum. OK, comment on code cette affaire ?

Représentation

Ici côté représentation, on va simplement regarder la création d’un arbre binaire. Comme d’habitude en C++, Python et Javascript comme ça tout le monde est content.

C++

#include <iostream>

using namespace std;

struct Node
{
    int value;
    struct Node* left;
    struct Node* right;
};

int main() 
{
    Node *Russia = new Node();
    Russia->value = 2018;

    Node *Germany = new Node();
    Germany->value = 2006;

    Node *France = new Node();
    France->value = 1998;

    Node *Mexico = new Node();
    Mexico->value = 1986;

    Russia->left = Germany;
    Russia->right = France;
    France->left = Mexico;

    //    "2018"   
    //     /   \   
    // "2006" "1998"
    //        /
    //     "1986"

    return 0;
}

Python (3.6.9)

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


Russia = Node(2018)
Germany = Node(2006)
France = Node(1998)
Mexico = Node(1986)

Russia.left = Germany
Russia.right = France
France.left = Mexico

#    '2018'   
#     /   \   
#  '2006' '1998'
#          /
#       '1986'

Javascript (NodeJS 12.14.0)

class Node {
    constructor (value = null) {
        this.value = value
        this.left = null
        this.right = null
    }
}

const Russia = new Node(2018)
const Germany = new Node(2006)
const France = new Node(1998)
const Mexico = new Node(1986)

Russia.left = Germany
Russia.right = France
France.left = Mexico

//    '2018'   
//     /   \   
//  '2006' '1998'
//          /
//       '1986'

Et donc ici c’est bien un arbre binaire que je te montre. En fait, plus particulièrement, c’est une Heap (tas). C’est une heap car les éléments sont triés du plus grand (root => 2018) au plus petit (leaf => 1986).

Je t’avais dit que c’était la jungle. On se focus sur un cas particulier pour que tu comprennes comment ça marche concrètement au lieu de rester dans l’abstrait. Les techniques de recherche, de tri et d’insertion sur ces structures seront pour des articles sur les algorithmes plus tard cet été. Je veux juste que tu aies en tête comment ça fonctionne de façon basique pour le moment.

Y’a une autre structure de données non linéaire que tu dois absolument avoir en tête pour certains entretiens.

Graph (Graphe)

C’est quoi ?

Un graphe c’est un ensemble de nœuds (ou sommets) fini reliés par des arêtes (ou arcs). Chaque nœud porte une valeur, chaque arête fait le lien entre les nœuds. Les liens n’ont pas d’origine hiérarchique, juste relationnelle.

Coté image mentale tu peux imaginer une carte de métro. Les arrêts de métro sont les nœuds qui portent la valeur de nom de station. Toutes les stations sont liées à une ou plusieurs stations via des arêtes. Et il y a aucune hiérarchie particulière, seulement des liens. Check le dump de ce que je vois dans ma tête quand je pense à un graphe.

Ouais les termes sont en anglais, je parle anglais dans ma tête. Tu vas tout le temps voir ces termes en anglais, autant s’habituer.

Les graphes c’est peut-être ce qui est le plus utilisé pour représenter des systèmes réels en informatique. Par exemple on les utilise pour les réseaux informatiques ou pour la cartographie comme google map. L’utilisation des graphes est encore plus grande que celle des arbres !

Et d’ailleurs c’est la même histoire qu’avec les arbres. Je te parle ici de la forme la plus simple de graphe. Mais y’a beaucoup d’autres types de graphes avec des particularités propres à des problématiques particulières.

Représentation

Il y a plusieurs manières de représenter un graphe. Aujourd’hui on va utiliser une matrice d’adjacence pour représenter tout ça. Si tu te rappelles de tes cours de maths, tu vois à peu près de quoi je parle. Sinon t’inquiètes, je te fais un petit dessin.

Si un chemin existe entre deux sommets alors on le représente avec un boolean true. Sinon c’est false. Facile ! Allez, codons ça.

C++

#include <iostream>

using namespace std;

class Graph {
    private:
        int vertices;
        int** adjacencyMatrix;

    public:
        Graph(int vertices) {
            this->vertices = vertices;
            adjacencyMatrix = new int*[vertices];

            for (int i = 0; i < vertices; i++) {
                adjacencyMatrix[i] = new int[vertices];
                for (int j = 0; j < vertices; j++)
                    adjacencyMatrix[i][j] = false;
            }
        }

    void addEdge(int i, int j) {
        adjacencyMatrix[i][j] = true;
        adjacencyMatrix[j][i] = true;
    }

    void display() {
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++)
                cout << adjacencyMatrix[i][j] << " ";
            cout << "\n";
        }
    }
};

int main() {
    Graph myGraph(4);

    myGraph.addEdge(0, 2);
    myGraph.addEdge(1, 3);
    myGraph.addEdge(2, 3);

    myGraph.display();
    // 0 0 1 0
    // 0 0 0 1
    // 1 0 0 1
    // 0 1 1 0
}

Python (3.6.9)

class Graph():
    def __init__(self, vertices):
        self.vertices = vertices
        self.adjacencyMatrix = []

        for _ in range(self.vertices):
            self.adjacencyMatrix.append([0 for i in range(self.vertices)])


    def add_edge(self, i, j):
        self.adjacencyMatrix[i][j] = 1
        self.adjacencyMatrix[j][i] = 1


    def display(self):
        for row in self.adjacencyMatrix:
            displayRow = ''
            for value in row:
                displayRow += str(value) + ' '
            print(displayRow)


myGraph = Graph(4)

myGraph.add_edge(0, 2)
myGraph.add_edge(1, 3)
myGraph.add_edge(2, 3)

myGraph.display()
# 0 0 1 0
# 0 0 0 1
# 1 0 0 1
# 0 1 1 0

Javascript (NodeJS 12.14.0)

class Graph {
    constructor(vertices) {
        this.vertices = vertices
        this.adjacencyMatrix = []

        for (var i = 0; i < this.vertices; i++) { 
            this.adjacencyMatrix[i] = new Array(this.vertices).fill(0) 
        }
    }

    addEdge(i, j) {
        this.adjacencyMatrix[i][j] = 1
        this.adjacencyMatrix[j][i] = 1
    }

    display() {
        for(const row of this.adjacencyMatrix) {
            let displayRow = ''
            for(const value of row) {
                displayRow += value + ' '
            }
            console.log(displayRow)
        }
    }
}

myGraph = new Graph(4)

myGraph.addEdge(0, 2)
myGraph.addEdge(1, 3)
myGraph.addEdge(2, 3)

myGraph.display()
// 0 0 1 0
// 0 0 0 1
// 1 0 0 1
// 0 1 1 0

Épilogue

Et ainsi se termine notre introduction dans le monde des structures de données. Le truc avec les structures de données c’est que c’est bien de les savoir, c’est encore mieux de connaître les algorithmes qui vont avec. Ça tombe bien on va bientôt parler de ça !