IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Arbre binaire de recherche, impressions


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    172
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2006
    Messages : 172
    Points : 99
    Points
    99
    Par défaut Arbre binaire de recherche, impressions
    Bonjour/Bonsoir individus de toute ethnie et sexe confondus.

    Je suis en train d'apprendre de ma propre initiative quand et comment utiliser les structures de données ainsi que leur inconvénients et avantages.
    Les liste chainées, les tableaux et les structures c'est fait (j'ignore si ce dernier est vraiment une structure de donnée cela dit ou si c'est inhérent à certains langages, comme le C).

    Je pense un jour avoir l'utilité d'un arbre binaire de recherche.
    J'ai quelques interrogations à propos de cette structure de donnée cependant.
    J'ai lu ce tutoriel.

    1) Est ce une convention (inter)nationale de construire un ABR de la sorte :


    Ou simplement arbitrairement choisie par l'auteur du tutoriel ?
    Ou encore en vigueur uniquement dans les pays où lit de gauche à droite ?

    2) Arrêtez moi si je me trompe mais idéalement la racine doit avoir la valeur intermédiaire, mais cela implique aussi que l'on connaisse plus ou moins les données qui entreront dans l'arbre.
    A moins que l'on soit plus ou moins obligé de redéfinir la racine à chaque ajout/suppression de nœud ?
    Mais dans ce cas se pose définitivement la question du temps de l'ajout/suppression d'un nœud, même si un arbre de recherche ne se soucie pas de cela comme son nom l'indique.

  2. #2
    Futur Membre du Club
    Inscrit en
    Septembre 2006
    Messages
    8
    Détails du profil
    Informations personnelles :
    Âge : 38

    Informations forums :
    Inscription : Septembre 2006
    Messages : 8
    Points : 8
    Points
    8
    Par défaut
    Citation Envoyé par AnozerOne Voir le message
    1) Est ce une convention (inter)nationale de construire un ABR de la sorte :
    Il n'y a aucunement de convention pour la construction d'un arbre de recherche. Que tu mettes les plus grandes feuilles à gauche ou à droite, peu importe du moment que tu en tiens compte lors de la recherche. La seule convention qui prévaudra, est celle que tu as décidé d'implémenter. L'auteur à utiliser ce sens par soucis de compréhension.

    Citation Envoyé par AnozerOne Voir le message
    2) Arrêtez moi si je me trompe mais idéalement la racine doit avoir la valeur intermédiaire
    Idéalement oui, pour profiter pleinement du principe de dichotomie. Mais dans la pratique tu prends généralement pour racine, la première valeur à insérer dans l'arbre. Ton arbre sera surement déséquilibré, mais je ne pense pas que ce soit significatif en temps de parcours lors de la recherche d'un neud.

    Citation Envoyé par AnozerOne Voir le message
    A moins que l'on soit plus ou moins obligé de redéfinir la racine à chaque ajout/suppression de nœud ?.
    Redéfinir la racine à chaque insertion paraît très très compliqué à mettre en oeuvre pour le peu d'avantage que ça pourrait apporter.

    En espérant avoir pu aider.

  3. #3
    Membre habitué
    Inscrit en
    Avril 2010
    Messages
    99
    Détails du profil
    Informations personnelles :
    Âge : 41

    Informations forums :
    Inscription : Avril 2010
    Messages : 99
    Points : 143
    Points
    143
    Par défaut
    Une catégorie d'arbres binaires de recherche s'appelle les arbres de recherche équilibrés (ou AVL).

    Le principe consiste à maintenir en permanence un arbre quasi-équilibré, c'est-à-dire que pour chaque sous-arbre, le nombre de nœuds à gauche est égale au nombre de nœuds à droite (à plus ou moins 1 près).

    L'avantage est de cette approche est que la hauteur de l'arbre est petite (logarithmique en le nombre de sommets) ce qui est le critère important dans la recherche d'un élément puisque la complexité de celle-ci est linéaire en la hauteur.

    Donc à chaque insertion et suppression d'un élément, on va rééquilibrer l'arbre (et changer sa racine éventuellement) mais sans que ce cout ne soit très important (encore logarithmique en le nombre de sommets).

    Pour plus de détails, tu peux aller voir ce cours par exemple:
    http://www.enseignement.polytechniqu...in4/node8.html

  4. #4
    Membre régulier
    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    172
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2006
    Messages : 172
    Points : 99
    Points
    99
    Par défaut
    Merci à vous deux.

    @nonifier : C'est limpide.

    @Biribibi : Hélas les liens d'images du cours que tu as donné en lien ne semblent pas valides, ce qui ne rend pas la lecture très agréable.
    Toutefois grâce a ce mot clef que tu m'as appris, j'ai pu trouver ceci :
    http://fr.wikipedia.org/wiki/Arbre_%C3%A9quilibr%C3%A9
    Dans un arbre AVL, la hauteur du SAG et celle du SAD diffèrent au plus de un. Le nombre de réorganisations maximum est en O(log N), c'est-à-dire la hauteur de l'arbre. L'insertion, la recherche et la suppression sont en O(log N).
    Erf, donc si on a pas de chance on doit réorganiser l'arbre en entier, j'avoue que ca me refroidit.

    Existe t'il un autre type d'arbre binaire avec peut être moins de performance pour la recherche d'un élément, mais avec un ajout/suppression d'élément moins couteux ?
    Bref un meilleur compromis entre temps de recherche et gestion de la structure de l'arbre.

  5. #5
    Membre habitué
    Inscrit en
    Avril 2010
    Messages
    99
    Détails du profil
    Informations personnelles :
    Âge : 41

    Informations forums :
    Inscription : Avril 2010
    Messages : 99
    Points : 143
    Points
    143
    Par défaut
    Salut,

    non, tu n'as jamais besoin de réorganiser l'arbre en entier.
    Comme je disais, c'est de l'ordre de log(n) éléments (par exemple 10 éléments pour un arbre à 1000 sommets, 20 éléments pour un arbre à 1 million de sommets) et cela dans le pire des cas.
    Les AVL font partie des structures avec le meilleur compromis recherche/modification.
    Il existe aussi les arbres rouge/noir basés un peu sur le même principe (maintenir un arbre équilibré) et donc la complexité des opérations est la même (à un facteur près). Je crois qu'ils sont plus efficaces en pratique mais à vérifier.
    http://fr.wikipedia.org/wiki/Arbre_bicolore

    Citation de Wikipédia (même si ce n'est pas forcement une source très fiable.
    Les arbres bicolores, ainsi que les arbres AVL, offrent la meilleure garantie sur le temps d'insertion, de suppression et de recherche dans les cas défavorables.
    Sinon, tu peux regarder du coté des tables de hash qui sont basés sur un tout autre concept.
    http://fr.wikipedia.org/wiki/Table_de_hachage

  6. #6
    Membre régulier
    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    172
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2006
    Messages : 172
    Points : 99
    Points
    99
    Par défaut
    Autant pour moi, j'avais mal lu la phrase que j'ai cité.
    J'ai déjà en effet vu plusieurs fois cité ces "arbres rouges", il faudrait que je me renseigne plus à ce sujet.

    Au sujet de wikipedia je sais qu'il ne faut pas prendre cela pour argent comptant, et privilégier les documents avec des sources référencées, mais j'ai un vague souvenir comme quoi il y aurait moins d'erreur ou équivalence entre une encyclopédie classique que l'on peut acheter.
    Cela se tient car potentiellement c'est le monde entier qui peut lire n'importe quel sujet et corriger les erreurs éventuelles.

    Donc à priori plus l'article est "vieux", plus il est fiable, à l'inverse d'une encyclopédie papier ou bien évidemment l'erreur perdurera, mais d'un autre côté il y a peu de chances qu'une erreur soit produite.
    Et wikipedia reste à la traine par rapport à des encyclopédies minutieuses.

    Je vais regarder de plus prés les tables de hachage, et je suis aussi totalement ouvert à toute autre structure de donnée.

  7. #7
    Membre habitué
    Inscrit en
    Avril 2010
    Messages
    99
    Détails du profil
    Informations personnelles :
    Âge : 41

    Informations forums :
    Inscription : Avril 2010
    Messages : 99
    Points : 143
    Points
    143
    Par défaut
    Wikipédia anglais est relativement fiable je trouve (du moins, pour les articles scientifiques) mais la version française l'est beaucoup moins.

  8. #8
    Membre émérite
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    Juin 2007
    Messages
    1 704
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : Juin 2007
    Messages : 1 704
    Points : 2 990
    Points
    2 990
    Par défaut Avant de poser une question on lit la FAQ


    C'est le bouton "FAQ ALGO" en haut dans la barre de menu.
    Du même auteur: mon projet, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

  9. #9
    Membre régulier
    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    172
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2006
    Messages : 172
    Points : 99
    Points
    99
    Par défaut
    Même si la FAQ est relativement complète elle ne répond pas néanmoins à mes questions précises.
    Ce qui n'est de toute façon pas le but d'une FAQ.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Arbre Binaire De Recherche
    Par dream_lover dans le forum C
    Réponses: 4
    Dernier message: 20/05/2007, 00h45
  2. Suppression dans un arbre binaire de recherche
    Par zeine77 dans le forum Langage
    Réponses: 1
    Dernier message: 11/05/2007, 21h40
  3. Réponses: 3
    Dernier message: 31/12/2005, 13h30
  4. Réponses: 11
    Dernier message: 07/04/2004, 14h06
  5. [Arbre binaire de Recherche]
    Par Giovanny Temgoua dans le forum Algorithmes et structures de données
    Réponses: 11
    Dernier message: 06/02/2004, 12h45

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo