skip to main | skip to sidebar
Code 18
Manuel du savoir-faire à l'usage des geeks et des curieux
RSS
  • Accueil
  • Le web au Québec
  • Liens
  • Twitter
  • Facebook
  • À propos

mardi 6 janvier 2009

Arbre binaire de recherche

Publié par Infinite Loop, à 21 h 57 0 commentaire

En programmation, on peut optimiser la performance des recherches en créant un arbre binaire. Cette technique consiste à maintenir un index des valeurs et peut être représentée sous la forme de branches d'arbre, partant de la racine, où chaque noeud est associé à une valeur unique qui se subdivise en deux éléments enfants. Ainsi, on pourra effectuer très rapidement une recherche dite "dichotomique" (couper en deux) dans un ensemble de valeurs très large.

Comme c'est un cas d'école, je laisserai les livres expliquer en détails tout le concept et je me contenterai de démontrer l'avantage de ce système de classement qui illustre bien ce qui se produit à l'interne. De façon plus concrète, on peut, dans une base de données, appliquer sur des champs des index déjà programmés pour améliorer la performance d'accès aux données, par exemple sur une clé primaire ou dans une jointure.

Pour mieux illustrer ce qui se passe, prenons par exemple un échantillon d'un million de cartes numérotées de 1 à 1 million. Si on recherche une valeur dans le lot sans qu'il y ait d'index, on risque de devoir comparer la valeur recherchée avec la valeur de chaque carte, jusqu'à ce qu'on la trouve (et on arrête de comparer dès qu'on l'a trouvée). Par exemple, si on recherche le nombre 420 003, le nombre nécessaire de comparaisons pourrait osciller entre une seule (si on est très chanceux et qu'on tombe sur la bonne carte dès le premier tour) et 1 million (si on est vraiment malchanceux et que c'est la dernière).

En maintenant un index binaire, c'est un peu comme si on classait les cartes en ordre croissant de valeur. Lorsque vient le temps d'en rechercher une, on prend la carte se trouvant au milieu du paquet et on la compare avec la valeur recherchée. Si elle est plus petite, on poursuivra la recherche avec la première moitié du paquet tandis que si elle est plus grande, on utilisera l'autre moitié, et ainsi de suite.

Nombre recherché : 420 003

  1. Cartes 1 à 1 000 000 (1 million de combinaisons possibles)
    On coupe le paquet en deux pour trouver la carte 500000. Le nombre recherché est plus petit donc on garde la moitié de paquet inférieure
  2. Cartes 1 à 500 000 (500 000 combinaisons)
    On coupe le paquet en deux. Le nombre recherché est plus grand que 250 000, on poursuit avec la moitié de paquet supérieure
  3. Cartes 250 000 à 500 000 (250 000 combinaisons)
    On coupe encore le paquet en deux pour y trouver la carte 375 000. Le nombre recherché est plus grand, on utilise la moitié du paquet supérieure
  4. Cartes 375 000 à 500 000 (125 000 combinaisons)
    On coupe en deux : c'est la carte 437 500. Notre nombre est plus petit...
  5. Cartes 375 000 à 437 500 (62 500)
    On coupe en deux : voilà la carte 406 250. Notre notre est plus grande
  6. Cartes 406 250 à 437 500 (31 250)
    On divise le paquet en deux. La carte du milieu est 421 875. Notre nombre est plus petit
  7. Cartes 406 250 à 421 875 (15 625)
    On divise encore. La carte est 414 063, donc notre nombre est plus grand
  8. Cartes 414 063 à 421 875 (7812)
    On divise toujours... 417 969. Plus grand.

    Ensuite...
  9. Cartes 417 969 à 421 875 (3906)
  10. Cartes 419 922 à 421 875 (1953)
  11. Cartes 419 922 à 420898 (946)
  12. Cartes 419 922 à 420 395 (473)
  13. Cartes 419 922 à 420 159 (237)
  14. Cartes 419 922 à 420 040 (118)
  15. Cartes 419 981 à 420 040 (59)
  16. Cartes 419 981 à 420 011 (30)
  17. Cartes 419 996 à 420 011 (15)
  18. Cartes 419 996 à 420 004 (8)
  19. Cartes 420 000 à 420 004 (4)
  20. Cartes 420 002 à 420 004 (2)
  21. Carte 420 003 trouvée en seulement 21 comparaisons !
Quod erat demonstrandum

À titre d'information, PostgreSQL possède les types d'index suivants :
  • B-tree : un arbre "balancé", similaire à l'arbre binaire, conçu pour un large volume de données
  • R-tree : spécialisé pour les recherches spaciales et multidimentionnelles
  • Hash : indexé comme une table d'hachage et performant avec l'opérateur =
  • GiST : Generalized Search Tree, une infrastructure permettant d'implanter différentes stratégies d'index, comme par exemple un cube de données


Tags: PostgreSQL, Programmation

0 réponse à "Arbre binaire de recherche"


Publier un commentaire

Message plus récent Messages plus anciens Accueil
S'abonner à : Publier des commentaires (Atom)
    Suivre @code18 sur Twitter

    Catégories

    • Apache (21)
    • Citations (167)
    • Club Vidéo (24)
    • Coffre à outils (55)
    • CSS (8)
    • Curiosités (117)
    • Design Pattern (2)
    • Drupal (8)
    • Easter Eggs (22)
    • Extensions Firefox (20)
    • GIMP (7)
    • Histoire (21)
    • HTML (32)
    • Humour (57)
    • Intégration (34)
    • iPod (12)
    • JavaScript (110)
    • Jeu de combat (6)
    • Le coin du geek (128)
    • Liens (12)
    • Linux (56)
    • Livres (78)
    • Lois et principes (46)
    • Marché des saveurs (26)
    • Mathématique (18)
    • Mobile (5)
    • Montréal (32)
    • Musique (112)
    • Pancartes et écriteaux (16)
    • Perl (8)
    • Pérou (1)
    • PHP (130)
    • PostgreSQL (44)
    • Programmation (105)
    • Saviez-vous que (55)
    • Sécurité (22)
    • SEO (5)
    • SQL Server (22)
    • Vieilles publicités (6)
    • Virtualisation (8)
    • Voyages (1)
    • Zend Framework (26)

    Divers

    Archives

    • ►  2015 (6)
      • ►  août 2015 (1)
      • ►  juillet 2015 (1)
      • ►  février 2015 (3)
      • ►  janvier 2015 (1)
    • ►  2014 (8)
      • ►  décembre 2014 (1)
      • ►  novembre 2014 (1)
      • ►  octobre 2014 (1)
      • ►  août 2014 (2)
      • ►  juillet 2014 (2)
      • ►  janvier 2014 (1)
    • ►  2013 (53)
      • ►  décembre 2013 (2)
      • ►  novembre 2013 (1)
      • ►  octobre 2013 (3)
      • ►  septembre 2013 (2)
      • ►  août 2013 (5)
      • ►  juillet 2013 (3)
      • ►  juin 2013 (5)
      • ►  mai 2013 (3)
      • ►  avril 2013 (7)
      • ►  mars 2013 (7)
      • ►  février 2013 (11)
      • ►  janvier 2013 (4)
    • ►  2012 (105)
      • ►  décembre 2012 (8)
      • ►  novembre 2012 (5)
      • ►  octobre 2012 (4)
      • ►  septembre 2012 (1)
      • ►  août 2012 (8)
      • ►  juillet 2012 (7)
      • ►  juin 2012 (7)
      • ►  mai 2012 (10)
      • ►  avril 2012 (13)
      • ►  mars 2012 (15)
      • ►  février 2012 (15)
      • ►  janvier 2012 (12)
    • ►  2011 (146)
      • ►  décembre 2011 (14)
      • ►  novembre 2011 (11)
      • ►  octobre 2011 (12)
      • ►  septembre 2011 (13)
      • ►  août 2011 (15)
      • ►  juillet 2011 (17)
      • ►  juin 2011 (18)
      • ►  mai 2011 (15)
      • ►  avril 2011 (9)
      • ►  mars 2011 (7)
      • ►  février 2011 (3)
      • ►  janvier 2011 (12)
    • ►  2010 (398)
      • ►  décembre 2010 (29)
      • ►  novembre 2010 (28)
      • ►  octobre 2010 (32)
      • ►  septembre 2010 (34)
      • ►  août 2010 (22)
      • ►  juillet 2010 (35)
      • ►  juin 2010 (42)
      • ►  mai 2010 (36)
      • ►  avril 2010 (37)
      • ►  mars 2010 (34)
      • ►  février 2010 (32)
      • ►  janvier 2010 (37)
    • ▼  2009 (429)
      • ►  décembre 2009 (32)
      • ►  novembre 2009 (34)
      • ►  octobre 2009 (33)
      • ►  septembre 2009 (37)
      • ►  août 2009 (37)
      • ►  juillet 2009 (39)
      • ►  juin 2009 (38)
      • ►  mai 2009 (37)
      • ►  avril 2009 (35)
      • ►  mars 2009 (36)
      • ►  février 2009 (32)
      • ▼  janvier 2009 (39)
        • Google peut nuire à votre ordinateur
        • Formulaire Flash pointant vers un autre domaine
        • Gérer la configuration d'un site avec Zend_Config
        • Super Mario Sunshine
        • Candidature de programmeur PHP rejetée
        • Simulateur de vol dans Google Earth
        • Fonctions anonymes dans PHP
        • Échec de conversion de fichier
        • Trouver le chemin de l'interpréteur Perl
        • Citation no. 14 sur les ascenseurs
        • Convertir un objet PHP en JSON
        • Type Serial de PostgreSQL
        • Traiter du code source avec SED
        • Boucle infinie
        • Automatiser YUI Compressor sur Windows
        • Le Principe de Peter
        • Protéger son site web contre les injections SQL
        • Citation no. 13 sur l'Univers
        • Police de caractères Spider-Man au hockey ?
        • Introduction à Greasemonkey
        • YUI Compressor Online
        • 2001, L'Odyssée de l'espace
        • Obtenir la clé primaire d'une table sous SQL Server
        • Créer un log des modifications avec SQL Server
        • Ouverture de compte Delicious
        • Easter eggs dans Firefox
        • Space Invaders dans OpenOffice
        • Citation no. 12 sur la démission
        • Utiliser GeSHi en PHP pour colorer le code source
        • Le Sportnographe à la radio de Radio-Canada
        • Ajouter de la coloration syntaxique au code source...
        • Ajouter au Windows Explorer un raccourci vers le c...
        • Arbre binaire de recherche
        • L'open source s'étend aux produits de la vie quoti...
        • Homestar Runner
        • Citation no. 11 - Spécial fortune cookie
        • Logiciel d'édition graphique gratuit
        • Prononciations d'acronymes en informatique
        • Favicon pour iPod Touch et iPhone
    • ►  2008 (84)
      • ►  décembre 2008 (34)
      • ►  novembre 2008 (39)
      • ►  octobre 2008 (11)

    Abonnés

Copyright © All Rights Reserved. Code 18 | Converted into Blogger Templates by Theme Craft