Les arbres binaires de recherche

À la découverte de ces structures de données surprenantes !

a marqué ce sujet comme résolu.

Bonjour à tous,

J'ai commencé (il y a 1 semaine, 4 jours) la rédaction d'un tutoriel dont l'intitulé est Les arbres binaires de recherche.

J'aimerais obtenir un maximum de retour sur celui-ci, sur le fond ainsi que sur la forme, afin de proposer en validation un texte de qualité. Il est à noter que ce tutoriel entrera dans le cadre du Concentré de Savoir sur les arbres.. Il contient probablement encore beaucoup de coquilles, mais je tenais à passer en bêta rapidement afin que tout soit prêt pour le CdS. :)

Si vous êtes intéressé, cliquez ci-dessous

Merci d'avance pour votre aide et bonne lecture ! :D

+0 -0

Intéressant.

Apres avoir survolé tres rapidement le tutoriel:

Par rapport aux arbres AVL, tu pourrais éventuellement ajouter une précision concernant l'amélioration de complexité temporelle obtenue grace a l'arbre AVL par rapport aux arbres binaires ordinaires (dans le pire des cas).

on préserve donc les qualités d'un arbre binaire en termes de performances

En fait je dirais qu'on l'améliore plutot.

+1 -0

Je sais pas trop si ça pourrait constituer un défi en soi. A la limite, si on réussit à trouver un problème concret qui mettrait les arbres en application, pourquoi pas. :)

Ramsey, je suis d'accord avec ta remarque, mais j'ai pas trop voulu m'attarder sur les histoires de complexité : les AVL sont meilleurs que les BST, on s'en rend bien compte. Après, est-ce que c'est la peine de ressortir les termes de complexité, devoir expliquer un "cas moyen", un "pire des cas", et cætera, je pense que ça discute. Mais sachant que je ne fais que survoler la notion…

EDIT : J'ai reformulé la phrase, histoire qu'elle soit plus précise sans trop entrer dans les détails. :)

+0 -0

Généralités

Il serait intéressant d'ajouter le tag "CdS". :)

Concernant le sous-titre, peut-être pourrais-tu le rendre plus explicite, en décrivant très brièvement à quoi sert un ABR ? Là, on apprend juste que c'est une structure de données.

Introduction

Un Concentré de Savoir sur les arbres…

Plutôt que de faire référence au CdS, qui est ponctuel, il me semble préférable de s'appuyer sur le titre. Là, si une personne lit le tutoriel dans un an, elle ne va pas trop comprendre. ^^

les amenant à créer une structure de données révolutionnaire sous la forme des arbres binaires de recherche.

La partie en gras me semble bizarrement formulée. Peut-être pourrais-tu essayer de remplacer "sous la forme" par un simple double-point ?

Qu'est-ce que c'est, comment ça marche, comment les implémenter, comment les améliorer

Aussi : à quoi ça sert. :P

Je ne relève pas les guillemets anglais, qu'il me semble judicieux de remplacer par des français.

Sinon, à qui s'adresse le cours ? Quels en sont les pré-requis ?

Merci ! :)

+0 -0

Définitions

Un bonsaï binaire de recherche

Vu qu'on n'a pas encore vu les termes techniques ("racine", "arête", etc.), il me semble préférable de ne pas les indiquer sur le schéma.

Arbre

Là par contre, tu peux illustrer tes propos en utilisant l'exemple précédent. Tu désignerais donc un noeud, la racine, une feuille et renseignerais la profondeur d'un noeud ainsi que la hauteur ne l'arbre.

La particularité d'un arbre binaire est que chaque nœud ne peut avoir que deux fils : un à gauche et un à droite.

C'est clarifié en-dessous, mais peut-être pourrais-tu remplacer "chaque nœud ne peut avoir que deux fils" par "chaque nœud peut avoir au plus deux fils" ?

Les éléments stockés dans un arbre binaire de recherche doivent posséder une relation d'ordre

Je dirais même plus, une relation d'ordre totale. ^^

Pour placer des valeurs dans un BST, il suffit ensuite de mettre à gauche les éléments plus petits et à droite les éléments plus grands.

Ce n'est pas très clair, puisque tu ne dis pas qu'il faut d'abord fixer la racine.

C'est cette particularité qui rend les BST intéressants : la plupart des opérations réalisées sur les arbres binaires de recherche ont une complexité temporelle logarithmique (O(logn)) dans le cas moyen

Peut-être passes-tu un peu vite là-dessus ? :)

Il me semble en fait qu'il serait préférable d'en parler plus tard. Là, tu définis la structure de données, et ce n'est que dans le second extrait que tu parles de son utilisation (opérations, implémentation et complexité).

Merci.

+0 -0

Implémentation

Je compléterais le titre avec le terme "opérations" : Opérations et implémentation.

On retrouve la structure récursive évoquée précédemment.

Je ne comprends pas comment tu désignes une feuille avec ta représentation. En Ocaml, par exemple, on aurait un truc du genre (la syntaxe n'est pas exacte) :

1
2
3
4
type bst =
  | Leaf of int
  | Node of bst * bst * int (* fils droit, fils gauche, valeur *)
;;

L'arbre est alors simplement constitué d'un nœud, sa racine.

Je ne comprends pas ce que tu veux dire par là.

Comme nous l'avons vu précédemment on peut ajouter un nouveau nœud à l'arbre très simplement à l'aide d'une fonction récursive :

J'ai eu un peu de mal à comprendre la procédure du fait que tu parles d'ajouter un noeud à un arbre, mais que tu as des arguments nommés node et element, i.e. que tu sembles ajouter un élément à un noeud.

On va simplement appliquer function à tous les nœuds de l'arbre par récursivité

Vu le pseudo code, plutôt une procédure qu'une fonction. Mais bon, j'ai jamais compris le but des premières. ^^

Si on veut supprimer le 10 de l'arbre, comment faire ?

Ce serait bien, je pense, de désigner le 10 sur le schéma, qu'on puisse le comprendre sans lire la légende.

Je n'ai pas regardé les codes en C. Concernant le pseudo-code, il serait peut-être intéressant de le remplacer par du vrai code, dans un langage aisément compréhensible (lequel ?). Non seulement tu bénéficierais de la coloration syntaxique, mais ça éviterait les phrases du genre "node de type bst_node". Notamment, j'ai eu du mal à suivre la fonction de suppression.

Concernant les illustrations, elles sont très bien, mais tu pourrais encore améliorer le truc en proposant des animations représentant le déroulement pas à pas des algorithmes. :)

Inconvénients et évolutions

RAS. :P

Merci !

+0 -0

Je n'ai pas regardé les codes en C. Concernant le pseudo-code, il serait peut-être intéressant de le remplacer par du vrai code, dans un langage aisément compréhensible (lequel ?). Non seulement tu bénéficierais de la coloration syntaxique, mais ça éviterait les phrases du genre "node de type bst_node". Notamment, j'ai eu du mal à suivre la fonction de suppression.

L'intérêt du pseudo-code à la base était justement de se détacher complètement de la syntaxe d'un langage et de ses contraintes techniques, pour permettre à tout le monde de s'approprier les algos à sa manière.

Concernant les illustrations, elles sont très bien, mais tu pourrais encore améliorer le truc en proposant des animations représentant le déroulement pas à pas des algorithmes. :)

Vayel

Malheureusement, j'ai peur que ce soit compliqué à mettre en œuvre. J'ai utilisé Dia pour les diagrammes, et à moins d'exporter un diagramme pour chaque étape de l'animation, puis tout ouvrir sous Gimp pour en extraire un GIF (ce qui prendrait un temps considérable, pour ne pas dire absurde), je sais pas trop si le jeu en vaut la chandelle. :/

+0 -0

Je refais un tour sur l'ensemble pour pointer les petits détails. :)

Introduction

Les arbres ont effectivement inspiré les algorithmiciens

Petite répétition de "inspiré" avec la phrase précédente. Peut-être pourrais-tu remplacer le premier par "se retrouvent" ? :)

les amenant à créer une structure de données révolutionnaire : les arbres binaires de recherche.

"révolutionnaire : les arbres binaires de recherche" ?

ce sont autant de questions qui seront abordées dans cet article qui va

Peut-être mettre une virgule après "article" ?

Un mot sur les prérequis

Peut-être préciser que la lecteur n'a pas besoin de connaître la notion d'arbre binaire ?

Par la suite, j'utiliserai à tort et à travers les expressions

Je chipote, mais peut-être plutôt "sans distinction" que "à tort et à travers" ? :P

«arbres»

Normalement, on met des espaces pour séparer le mot des guillemets : « arbres ». :)

Définitions

Afin de tirer les choses au clair, reprenons le petit arbre de tout à l'heure, et voyons comment les différents éléments s'insèrent à l'intérieur.

Il me semble préférable de prendre un exemple concret, ce qui permettrait de montrer un cas d'utilisation des ABR. De plus, on pourrait, avec l'exemple que tu donnes, se demander pourquoi insérer 10 en premier, c'est-à-dire ne pas prendre en compte le fait que les valeurs arrivent souvent une à une.

Ca demanderait du travail, mais une manière intéressante de présenter la structure serait de partir d'un problème concret. Tu construirais alors l'ABR avec les données du problème, puis décrirais le résultat. Par exemple, dans les grandes lignes :

Explication de ce qu'est un arbre binaire. Voire le mettre en pré-requis.

Je viens d'ouvrir une clinique vétérinaire, et veut stocker les fiches des animaux que je soigne. Je souhaite les trier par ordre alphabétique. Pour ce faire, je pourrais utiliser une liste, mais aurais alors une complexité linéaire. Je vais donc procéder de la manière suivante.

  • Je reçois le premier client et stocke la première fiche (pas besoin de trier, vu qu'il n'y a qu'une seule donnée)
  • Je reçois le deuxième client et ranger sa fiche comme fils gauche de la première si le nom est plus petit d'après l'ordre lexicographique, comme fils droit sinon.
  • Je reçois le troisième client…
  • etc.

On construit ce qu'on appelle un ABR. Puis détails techniques : relation d'ordre, complexité, etc.

On part avec une seule donnée pour ne pas se poser la question de l'équilibrage de l'arbre.

+1 -0

Je me permets le double-post :)

J'ai effectué les corrections que tu as suggéré, Vayel, mais je ne rédigerai l'exemple que demain, je suis pas vraiment dans mon assiette ce soir. En plus, j'ai vu que le tutoriel est passé à "en cours de validation par Taurre" ; je ne sais pas s'il est judicieux de mettre à jour la version à valider maintenant.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte