Une introduction aux arbres en programmation: l'oxygène d'un codage efficace

Plusieurs fois, vous souhaitez enregistrer des informations dans votre programme et y accéder plusieurs fois. Et vous le stockerez souvent dans une structure de données très simple: un tableau. Et ça marche souvent très bien! Mais parfois, cela prend juste beaucoup de temps pour terminer.

Et donc, pour optimiser ce type de programme, de nombreuses personnes intelligentes ont développé des choses étranges que nous appelons des structures de données . Aujourd'hui, je vais aborder quelques notions de base sur ce sujet, et je vais discuter d'une structure spécifique qui est souvent posée lors des interviews de codage et qui rend tout le monde fou: les arbres.

Je ne plongerai pas beaucoup dans le code, mais uniquement dans la théorie du fonctionnement de tout. Il existe des millions d'exemples de code en ligne, alors jetez-en un coup d'œil après avoir compris le fonctionnement des arbres!

Alors, qu'est-ce qu'une structure de données?

Selon Wikipedia:

"Une structure de données est une organisation et un format de stockage des données qui permet un accès et une modification efficaces"

Cela signifie essentiellement que ce n'est rien de plus qu'un code écrit pour créer une manière complexe de stocker des données. Il existe de nombreuses structures de données que vous pouvez implémenter, et chacune a une tâche spécifique. Ils peuvent aller de structures très simples - comme des listes chaînées - à des structures vraiment complexes - comme des graphiques.

Les arbres sont suffisamment complexes pour être très rapides dans ce qu'ils font, mais suffisamment simples pour qu'ils soient compréhensibles. Et une chose pour laquelle ils sont vraiment doués est de trouver des valeurs avec une utilisation minimale de la mémoire.

Mais comment mesurer l'efficacité d'une structure de données?

Avez-vous déjà vu d'étranges notations que les gens utilisent en ligne comme O (n)? Cela s'appelle Big O Notation, et c'est la méthode standard pour évaluer les performances des structures et des algorithmes. Le grand O que nous utilisons est la représentation du pire des cas: avoir quelque chose qui est O (n) (avec n étant le nombre d'éléments à l'intérieur) signifie que dans le pire des cas, cela prend le temps n , ce qui est vraiment bien.

Entre parenthèses, nous avons écrit n qui est l'équivalent d'écrire l'expression y = x →. Il évolue proportionnellement. Mais parfois, nous avons des expressions différentes:

  • O (1)
  • O (log (n))
  • Sur)
  • O (n²)
  • O (n³)
  • Sur!)
  • O (e ^ n)

Plus le résultat d'une fonction est bas, plus une structure est efficace.

Il existe plusieurs types d'arbres. Nous parlerons de BST (arbres de recherche binaire) et d'arbres AVL (arbres équilibrés automatiquement) qui ont des propriétés différentes:

Ok, vous avez parlé de toute cette notation bizarre… alors comment fonctionnent les arbres?

L'arbre des noms vient de sa représentation réelle: il a une racine, des feuilles et des branches, et est souvent représenté comme ceci:

Il existe quelques dénominations que nous utilisons, à savoir parent et enfant, qui ont une relation unique. Si x est le parent de y alors y est l'enfant de x . Dans cette image, 2 est le parent de 5, puis 5 est l'enfant de 2. Chaque nœud - chaque position avec une valeur - ne peut avoir qu'un parent et 2 enfants.

Mais à part tout cela, il n'y a pas de modèle qui est suivi, donc cet arbre n'est pas vraiment utile… Nous devrions donc ajouter quelques règles supplémentaires pour créer une bonne structure de données.

Arbres de recherche binaires

C'est alors que les arbres de recherche binaire entrent en jeu! Au lieu de simplement placer des nœuds enfants au hasard, ils suivent un ordre spécifique:

  • S'il n'y a pas de nœuds, la première valeur entrée devient la racine de l'arbre.
  • S'il y a des nœuds, l'insertion prend les étapes suivantes: en commençant à la racine, si la valeur que vous entrez est plus petite que le nœud actuel, passez par la branche gauche, sinon passez par la droite. Si vous êtes dans un endroit vide, c'est là que votre valeur appartient!

Cela peut sembler un peu déroutant au début, mais écrivons un pseudo-code pour le simplifier:

//This code won't compile in any language (that I know of) and only serves to demonstrate how the code would look like
def insert(Node n, int v) { if n is NULL: return createNode(v) else if n.value < v: n.right = insert(n.right, v) else: n.left = insert(n.left, v) return n}

Maintenant que se passe-t-il ici? Nous vérifions d'abord si l'endroit où nous nous trouvons actuellement est vide. Si c'est le cas, nous créons un nœud à cet endroit avec la fonction createNode. S'il n'est pas vide, nous devons voir où nous devons placer notre nœud.

Cette démo montre comment cela fonctionne:

De cette façon, nous pouvons rechercher n'importe quelle valeur dans l'arborescence sans avoir à passer par tous les nœuds. Génial!

Mais cela ne va pas toujours aussi bien que dans le gif ci-dessus. Et si nous obtenons quelque chose comme ça?

Dans ce cas, le comportement de l'arbre vous fait passer par tous les nœuds. C'est pourquoi l'efficacité du pire des cas d'un BST est de O (n), ce qui la rend lente.

La suppression du BST est également facile:

  • Si un nœud n'a pas d'enfants → supprimer le nœud
  • Si un nœud a un enfant → connectez le nœud parent à son nœud petit-enfant et supprimez le nœud
  • Si un nœud a 2 enfants → remplacez le nœud par son plus grand enfant (l'enfant le plus à droite à gauche) → voir l'image ci-dessous

Alors maintenant, vous savez tout ce dont vous avez besoin sur les BST. Assez cool hein?

Mais que faire si vous vouliez TOUJOURS avoir un arbre efficace? Qu'est-ce que tu ferais?

Si vous avez cette nécessité, les arbres AVL peuvent très bien le faire pour vous. En échange, ils sont des millions de fois plus complexes que les BST mais suivent la même organisation qu'auparavant.

An AVL tree is a self-balancing tree that has specific operations (called rotations) that allow the tree to stay balanced . This means that each node in the tree will have a difference of height between its two child branches of maximum 1.

With this, the tree will always have a height of log(n) (n being the number of elements) and this allows you to search for elements in a really efficient way.

So now you see how good and perfect balanced trees are. But how to make them is the real question. I have mentioned the word depth before, so let’s first understand it.

Height is what allows us to understand if our tree is balanced or not. And with it we’re able to determine where the problem is and apply the balancing functions: rotations. These are really simple functions that consist of exchanging nodes between each other in order to remove the height difference, but they might look really strange at first.

There are 4 operations:

  • Rotation Left
  • Rotation Right
  • Rotation Left-Right
  • Rotation Right-Left

Wow that was strange… how do rotations work?

Rotations are strange at first, and I suggest checking out some animations of them working.

Try with your own trees on this website: //www.cs.usfca.edu/~galles/visualization/AVLtree.html

It allows you to dynamically see the rotations happening and is a great tool!

There are only four cases, so understanding them will be easy.

That’s all for now!

Trees are pretty easy to understand, and with practice you can work with them easily. Applying them in your code is a major key to make your programs a lot more efficient.

If you have any questions about something you didn’t understand, disagree with, or would like to suggest, feel free to contact me through Twitter or by email!

Email: tiago.melo.antunes [at] tecnico [dot] ulisboa [dot] pt