CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="fr" dir="ltr"> <head> <meta charset="UTF-8"> <title>Arbre binaire de recherche — Wikipédia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )frwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":[",\t."," \t,"],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","janvier","février","mars","avril","mai","juin","juillet","août","septembre","octobre","novembre","décembre"],"wgRequestId":"39fa23b6-6593-422f-8f89-b51baefdc13d","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Arbre_binaire_de_recherche","wgTitle":"Arbre binaire de recherche","wgCurRevisionId":219902427,"wgRevisionId":219902427,"wgArticleId":329785,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Page utilisant P61","Page utilisant P575","Page utilisant P31","Page utilisant P3755","Page utilisant P3757","Page utilisant P18","Article utilisant l'infobox Algorithme","Article utilisant une Infobox","Article contenant un appel à traduction en anglais","Portail:Informatique théorique/Articles liés","Portail:Informatique/Articles liés","Projet:Mathématiques/Articles","Bon article en anglais","Arbre (structure de données)"],"wgPageViewLanguage":"fr", "wgPageContentLanguage":"fr","wgPageContentModel":"wikitext","wgRelevantPageName":"Arbre_binaire_de_recherche","wgRelevantArticleId":329785,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":true,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"fr","pageLanguageDir":"ltr","pageVariantFallbacks":"fr"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":10000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q623818","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform", "platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","ext.pygments":"ready","ext.cite.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.pygments.view","ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ArchiveLinks","ext.gadget.Wdsearch","ext.urlShortener.toolbar" ,"ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=fr&modules=ext.cite.styles%7Cext.math.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=fr&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=fr&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.16"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/1200px-Binary_search_tree.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1000"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/800px-Binary_search_tree.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="667"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/640px-Binary_search_tree.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="533"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Arbre binaire de recherche — Wikipédia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//fr.m.wikipedia.org/wiki/Arbre_binaire_de_recherche"> <link rel="alternate" type="application/x-wiki" title="Modifier" href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipédia (fr)"> <link rel="EditURI" type="application/rsd+xml" href="//fr.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://fr.wikipedia.org/wiki/Arbre_binaire_de_recherche"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr"> <link rel="alternate" type="application/atom+xml" title="Flux Atom de Wikipédia" href="/w/index.php?title=Sp%C3%A9cial:Modifications_r%C3%A9centes&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Arbre_binaire_de_recherche rootpage-Arbre_binaire_de_recherche skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Aller au contenu</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Menu principal" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Menu principal" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Menu principal</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Menu principal</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">masquer</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Accueil_principal" title="Accueil général [z]" accesskey="z"><span>Accueil</span></a></li><li id="n-thema" class="mw-list-item"><a href="/wiki/Portail:Accueil"><span>Portails thématiques</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Page_au_hasard" title="Affiche un article au hasard [x]" accesskey="x"><span>Article au hasard</span></a></li><li id="n-contact" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Contact"><span>Contact</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Pages_sp%C3%A9ciales"><span>Pages spéciales</span></a></li> </ul> </div> </div> <div id="p-Contribuer" class="vector-menu mw-portlet mw-portlet-Contribuer" > <div class="vector-menu-heading"> Contribuer </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-aboutwp" class="mw-list-item"><a href="/wiki/Aide:D%C3%A9buter"><span>Débuter sur Wikipédia</span></a></li><li id="n-help" class="mw-list-item"><a href="/wiki/Aide:Accueil" title="Accès à l’aide"><span>Aide</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Accueil_de_la_communaut%C3%A9" title="À propos du projet, ce que vous pouvez faire, où trouver les informations"><span>Communauté</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Modifications_r%C3%A9centes" title="Liste des modifications récentes sur le wiki [r]" accesskey="r"><span>Modifications récentes</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Wikip%C3%A9dia:Accueil_principal" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipédia" src="/static/images/mobile/copyright/wikipedia-wordmark-fr.svg" style="width: 7.4375em; height: 1.125em;"> <img class="mw-logo-tagline" alt="l'encyclopédie libre" src="/static/images/mobile/copyright/wikipedia-tagline-fr.svg" width="120" height="13" style="width: 7.5em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Sp%C3%A9cial:Recherche" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Rechercher sur Wikipédia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Rechercher</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Rechercher sur Wikipédia" aria-label="Rechercher sur Wikipédia" autocapitalize="sentences" title="Rechercher sur Wikipédia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Spécial:Recherche"> </div> <button class="cdx-button cdx-search-input__end-button">Rechercher</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Outils personnels"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Apparence"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Modifier l'apparence de la taille, de la largeur et de la couleur de la police de la page" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Apparence" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Apparence</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=fr.wikipedia.org&uselang=fr" class=""><span>Faire un don</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Sp%C3%A9cial:Cr%C3%A9er_un_compte&returnto=Arbre+binaire+de+recherche" title="Nous vous encourageons à créer un compte utilisateur et vous connecter ; ce n’est cependant pas obligatoire." class=""><span>Créer un compte</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Sp%C3%A9cial:Connexion&returnto=Arbre+binaire+de+recherche" title="Nous vous encourageons à vous connecter ; ce n’est cependant pas obligatoire. [o]" accesskey="o" class=""><span>Se connecter</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Plus d’options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Outils personnels" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Outils personnels</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="Menu utilisateur" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=fr.wikipedia.org&uselang=fr"><span>Faire un don</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Cr%C3%A9er_un_compte&returnto=Arbre+binaire+de+recherche" title="Nous vous encourageons à créer un compte utilisateur et vous connecter ; ce n’est cependant pas obligatoire."><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Créer un compte</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Connexion&returnto=Arbre+binaire+de+recherche" title="Nous vous encourageons à vous connecter ; ce n’est cependant pas obligatoire. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Se connecter</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages pour les contributeurs déconnectés <a href="/wiki/Aide:Premiers_pas" aria-label="En savoir plus sur la contribution"><span>en savoir plus</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Mes_contributions" title="Une liste des modifications effectuées depuis cette adresse IP [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Mes_discussions" title="La page de discussion pour les contributions depuis cette adresse IP [n]" accesskey="n"><span>Discussion</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Sommaire" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Sommaire</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">masquer</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">Début</div> </a> </li> <li id="toc-Définition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Définition"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Définition</span> </div> </a> <button aria-controls="toc-Définition-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Afficher / masquer la sous-section Définition</span> </button> <ul id="toc-Définition-sublist" class="vector-toc-list"> <li id="toc-Définition_générale" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Définition_générale"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>Définition générale</span> </div> </a> <ul id="toc-Définition_générale-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Définitions_spécifiques" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Définitions_spécifiques"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.2</span> <span>Définitions spécifiques</span> </div> </a> <ul id="toc-Définitions_spécifiques-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Opérations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Opérations"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Opérations</span> </div> </a> <button aria-controls="toc-Opérations-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Afficher / masquer la sous-section Opérations</span> </button> <ul id="toc-Opérations-sublist" class="vector-toc-list"> <li id="toc-Recherche" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Recherche"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Recherche</span> </div> </a> <ul id="toc-Recherche-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Insertion" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Insertion"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>Insertion</span> </div> </a> <ul id="toc-Insertion-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Suppression" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Suppression"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Suppression</span> </div> </a> <ul id="toc-Suppression-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Applications</span> </div> </a> <button aria-controls="toc-Applications-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Afficher / masquer la sous-section Applications</span> </button> <ul id="toc-Applications-sublist" class="vector-toc-list"> <li id="toc-Parcours_ordonné" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Parcours_ordonné"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Parcours ordonné</span> </div> </a> <ul id="toc-Parcours_ordonné-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Tri" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Tri"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Tri</span> </div> </a> <ul id="toc-Tri-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Files_de_priorité" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Files_de_priorité"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>Files de priorité</span> </div> </a> <ul id="toc-Files_de_priorité-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Equilibrage" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Equilibrage"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Equilibrage</span> </div> </a> <ul id="toc-Equilibrage-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Extensions" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Extensions"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Extensions</span> </div> </a> <ul id="toc-Extensions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes_et_références" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes_et_références"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Notes et références</span> </div> </a> <ul id="toc-Notes_et_références-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Liens_externes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Liens_externes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Liens externes</span> </div> </a> <ul id="toc-Liens_externes-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Sommaire" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Table des matières" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Basculer la table des matières" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Basculer la table des matières</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Arbre binaire de recherche</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Aller à un article dans une autre langue. Disponible en 34 langues." > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-34" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">34 langues</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%B4%D8%AC%D8%B1%D8%A9_%D8%A8%D8%AD%D8%AB_%D8%AB%D9%86%D8%A7%D8%A6%D9%8A%D8%A9" title="شجرة بحث ثنائية – arabe" lang="ar" hreflang="ar" data-title="شجرة بحث ثنائية" data-language-autonym="العربية" data-language-local-name="arabe" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE_%D0%B4%D1%8A%D1%80%D0%B2%D0%BE_%D0%B7%D0%B0_%D1%82%D1%8A%D1%80%D1%81%D0%B5%D0%BD%D0%B5" title="Двоично дърво за търсене – bulgare" lang="bg" hreflang="bg" data-title="Двоично дърво за търсене" data-language-autonym="Български" data-language-local-name="bulgare" class="interlanguage-link-target"><span>Български</span></a></li><li class="interlanguage-link interwiki-bs mw-list-item"><a href="https://bs.wikipedia.org/wiki/Binarno_stablo_pretra%C5%BEivanja" title="Binarno stablo pretraživanja – bosniaque" lang="bs" hreflang="bs" data-title="Binarno stablo pretraživanja" data-language-autonym="Bosanski" data-language-local-name="bosniaque" class="interlanguage-link-target"><span>Bosanski</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Arbre_binari_de_cerca" title="Arbre binari de cerca – catalan" lang="ca" hreflang="ca" data-title="Arbre binari de cerca" data-language-autonym="Català" data-language-local-name="catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Bin%C3%A1rn%C3%AD_vyhled%C3%A1vac%C3%AD_strom" title="Binární vyhledávací strom – tchèque" lang="cs" hreflang="cs" data-title="Binární vyhledávací strom" data-language-autonym="Čeština" data-language-local-name="tchèque" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Bin%C3%A6rt_s%C3%B8getr%C3%A6" title="Binært søgetræ – danois" lang="da" hreflang="da" data-title="Binært søgetræ" data-language-autonym="Dansk" data-language-local-name="danois" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum" title="Binärer Suchbaum – allemand" lang="de" hreflang="de" data-title="Binärer Suchbaum" data-language-autonym="Deutsch" data-language-local-name="allemand" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-en badge-Q17437798 badge-goodarticle mw-list-item" title="bon article"><a href="https://en.wikipedia.org/wiki/Binary_search_tree" title="Binary search tree – anglais" lang="en" hreflang="en" data-title="Binary search tree" data-language-autonym="English" data-language-local-name="anglais" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/%C3%81rbol_binario_de_b%C3%BAsqueda" title="Árbol binario de búsqueda – espagnol" lang="es" hreflang="es" data-title="Árbol binario de búsqueda" data-language-autonym="Español" data-language-local-name="espagnol" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C_%D8%AF%D9%88%D8%AF%D9%88%DB%8C%DB%8C" title="درخت جستجوی دودویی – persan" lang="fa" hreflang="fa" data-title="درخت جستجوی دودویی" data-language-autonym="فارسی" data-language-local-name="persan" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Bin%C3%A4%C3%A4rinen_hakupuu" title="Binäärinen hakupuu – finnois" lang="fi" hreflang="fi" data-title="Binäärinen hakupuu" data-language-autonym="Suomi" data-language-local-name="finnois" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A2%D7%A5_%D7%97%D7%99%D7%A4%D7%95%D7%A9" title="עץ חיפוש – hébreu" lang="he" hreflang="he" data-title="עץ חיפוש" data-language-autonym="עברית" data-language-local-name="hébreu" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-hy mw-list-item"><a href="https://hy.wikipedia.org/wiki/%D4%B2%D5%AB%D5%B6%D5%A1%D6%80_%D5%B8%D6%80%D5%B8%D5%B6%D5%B4%D5%A1%D5%B6_%D5%AE%D5%A1%D5%BC" title="Բինար որոնման ծառ – arménien" lang="hy" hreflang="hy" data-title="Բինար որոնման ծառ" data-language-autonym="Հայերեն" data-language-local-name="arménien" class="interlanguage-link-target"><span>Հայերեն</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Pohon_Pencarian_Biner" title="Pohon Pencarian Biner – indonésien" lang="id" hreflang="id" data-title="Pohon Pencarian Biner" data-language-autonym="Bahasa Indonesia" data-language-local-name="indonésien" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Albero_binario_di_ricerca" title="Albero binario di ricerca – italien" lang="it" hreflang="it" data-title="Albero binario di ricerca" data-language-autonym="Italiano" data-language-local-name="italien" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8" title="二分探索木 – japonais" lang="ja" hreflang="ja" data-title="二分探索木" data-language-autonym="日本語" data-language-local-name="japonais" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-kn mw-list-item"><a href="https://kn.wikipedia.org/wiki/%E0%B2%AC%E0%B3%88%E0%B2%A8%E0%B2%B0%E0%B2%BF_%E0%B2%B8%E0%B2%B0%E0%B3%8D%E0%B2%9A%E0%B3%8D_%E0%B2%9F%E0%B3%8D%E0%B2%B0%E0%B3%80_(%E0%B2%AC%E0%B3%88%E0%B2%A8%E0%B2%B0%E0%B2%BF_%E0%B2%B9%E0%B3%81%E0%B2%A1%E0%B3%81%E0%B2%95%E0%B2%BE%E0%B2%9F%E0%B2%A6_%E0%B2%9F%E0%B3%8D%E0%B2%B0%E0%B3%80)" title="ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ (ಬೈನರಿ ಹುಡುಕಾಟದ ಟ್ರೀ) – kannada" lang="kn" hreflang="kn" data-title="ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ (ಬೈನರಿ ಹುಡುಕಾಟದ ಟ್ರೀ)" data-language-autonym="ಕನ್ನಡ" data-language-local-name="kannada" class="interlanguage-link-target"><span>ಕನ್ನಡ</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC" title="이진 탐색 트리 – coréen" lang="ko" hreflang="ko" data-title="이진 탐색 트리" data-language-autonym="한국어" data-language-local-name="coréen" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-lmo mw-list-item"><a href="https://lmo.wikipedia.org/wiki/Alber_binari_de_ricerca" title="Alber binari de ricerca – lombard" lang="lmo" hreflang="lmo" data-title="Alber binari de ricerca" data-language-autonym="Lombard" data-language-local-name="lombard" class="interlanguage-link-target"><span>Lombard</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Binaire_zoekboom" title="Binaire zoekboom – néerlandais" lang="nl" hreflang="nl" data-title="Binaire zoekboom" data-language-autonym="Nederlands" data-language-local-name="néerlandais" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Binarne_drzewo_poszukiwa%C5%84" title="Binarne drzewo poszukiwań – polonais" lang="pl" hreflang="pl" data-title="Binarne drzewo poszukiwań" data-language-autonym="Polski" data-language-local-name="polonais" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/%C3%81rvore_bin%C3%A1ria_de_busca" title="Árvore binária de busca – portugais" lang="pt" hreflang="pt" data-title="Árvore binária de busca" data-language-autonym="Português" data-language-local-name="portugais" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Arbore_binar_de_c%C4%83utare" title="Arbore binar de căutare – roumain" lang="ro" hreflang="ro" data-title="Arbore binar de căutare" data-language-autonym="Română" data-language-local-name="roumain" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0" title="Двоичное дерево поиска – russe" lang="ru" hreflang="ru" data-title="Двоичное дерево поиска" data-language-autonym="Русский" data-language-local-name="russe" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Binarno_stablo_pretrage" title="Binarno stablo pretrage – serbo-croate" lang="sh" hreflang="sh" data-title="Binarno stablo pretrage" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="serbo-croate" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Bin%C3%A1rny_vyh%C4%BEad%C3%A1vac%C3%AD_strom" title="Binárny vyhľadávací strom – slovaque" lang="sk" hreflang="sk" data-title="Binárny vyhľadávací strom" data-language-autonym="Slovenčina" data-language-local-name="slovaque" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/Binarno_stablo_pretrage" title="Binarno stablo pretrage – serbe" lang="sr" hreflang="sr" data-title="Binarno stablo pretrage" data-language-autonym="Српски / srpski" data-language-local-name="serbe" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Bin%C3%A4rt_s%C3%B6ktr%C3%A4d" title="Binärt sökträd – suédois" lang="sv" hreflang="sv" data-title="Binärt sökträd" data-language-autonym="Svenska" data-language-local-name="suédois" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%95%E0%B9%89%E0%B8%99%E0%B9%84%E0%B8%A1%E0%B9%89%E0%B8%84%E0%B9%89%E0%B8%99%E0%B8%AB%E0%B8%B2%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B8%97%E0%B8%A7%E0%B8%B4%E0%B8%A0%E0%B8%B2%E0%B8%84" title="ต้นไม้ค้นหาแบบทวิภาค – thaï" lang="th" hreflang="th" data-title="ต้นไม้ค้นหาแบบทวิภาค" data-language-autonym="ไทย" data-language-local-name="thaï" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/%C4%B0kili_arama_a%C4%9Fac%C4%B1" title="İkili arama ağacı – turc" lang="tr" hreflang="tr" data-title="İkili arama ağacı" data-language-autonym="Türkçe" data-language-local-name="turc" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%94%D0%B2%D1%96%D0%B9%D0%BA%D0%BE%D0%B2%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D1%88%D1%83%D0%BA%D1%83" title="Двійкове дерево пошуку – ukrainien" lang="uk" hreflang="uk" data-title="Двійкове дерево пошуку" data-language-autonym="Українська" data-language-local-name="ukrainien" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n" title="Cây tìm kiếm nhị phân – vietnamien" lang="vi" hreflang="vi" data-title="Cây tìm kiếm nhị phân" data-language-autonym="Tiếng Việt" data-language-local-name="vietnamien" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9" title="二元搜尋樹 – chinois" lang="zh" hreflang="zh" data-title="二元搜尋樹" data-language-autonym="中文" data-language-local-name="chinois" class="interlanguage-link-target"><span>中文</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9" title="二元搜尋樹 – cantonais" lang="yue" hreflang="yue" data-title="二元搜尋樹" data-language-autonym="粵語" data-language-local-name="cantonais" class="interlanguage-link-target"><span>粵語</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q623818#sitelinks-wikipedia" title="Modifier les liens interlangues" class="wbc-editpage">Modifier les liens</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Espaces de noms"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Arbre_binaire_de_recherche" title="Voir le contenu de la page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Discussion:Arbre_binaire_de_recherche" rel="discussion" title="Discussion au sujet de cette page de contenu [t]" accesskey="t"><span>Discussion</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Modifier la variante de langue" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">français</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Affichages"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Arbre_binaire_de_recherche"><span>Lire</span></a></li><li id="ca-ve-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit" title="Modifier cette page [v]" accesskey="v"><span>Modifier</span></a></li><li id="ca-edit" class="collapsible vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit" title="Modifier le wikicode de cette page [e]" accesskey="e"><span>Modifier le code</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=history" title="Historique des versions de cette page [h]" accesskey="h"><span>Voir l’historique</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Outils de la page"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Outils" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Outils</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Outils</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">masquer</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="Plus d’options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Arbre_binaire_de_recherche"><span>Lire</span></a></li><li id="ca-more-ve-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit" title="Modifier cette page [v]" accesskey="v"><span>Modifier</span></a></li><li id="ca-more-edit" class="collapsible vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit" title="Modifier le wikicode de cette page [e]" accesskey="e"><span>Modifier le code</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=history"><span>Voir l’historique</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> Général </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Pages_li%C3%A9es/Arbre_binaire_de_recherche" title="Liste des pages liées qui pointent sur celle-ci [j]" accesskey="j"><span>Pages liées</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Suivi_des_liens/Arbre_binaire_de_recherche" rel="nofollow" title="Liste des modifications récentes des pages appelées par celle-ci [k]" accesskey="k"><span>Suivi des pages liées</span></a></li><li id="t-upload" class="mw-list-item"><a href="//fr.wikipedia.org/wiki/Aide:Importer_un_fichier" title="Téléverser des fichiers [u]" accesskey="u"><span>Téléverser un fichier</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Arbre_binaire_de_recherche&oldid=219902427" title="Adresse permanente de cette version de cette page"><span>Lien permanent</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=info" title="Davantage d’informations sur cette page"><span>Informations sur la page</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Citer&page=Arbre_binaire_de_recherche&id=219902427&wpFormIdentifier=titleform" title="Informations sur la manière de citer cette page"><span>Citer cette page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:UrlShortener&url=https%3A%2F%2Ffr.wikipedia.org%2Fwiki%2FArbre_binaire_de_recherche"><span>Obtenir l'URL raccourcie</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:QrCode&url=https%3A%2F%2Ffr.wikipedia.org%2Fwiki%2FArbre_binaire_de_recherche"><span>Télécharger le code QR</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Imprimer / exporter </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-create_a_book" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Livre&bookcmd=book_creator&referer=Arbre+binaire+de+recherche"><span>Créer un livre</span></a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:DownloadAsPdf&page=Arbre_binaire_de_recherche&action=show-download-screen"><span>Télécharger comme PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Arbre_binaire_de_recherche&printable=yes" title="Version imprimable de cette page [p]" accesskey="p"><span>Version imprimable</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> Dans d’autres projets </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Binary_search_trees" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q623818" title="Lien vers l’élément dans le dépôt de données connecté [g]" accesskey="g"><span>Élément Wikidata</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Outils de la page"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Apparence"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Apparence</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">masquer</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">Un article de Wikipédia, l'encyclopédie libre.</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="fr" dir="ltr"><div class="bandeau-container metadata homonymie hatnote"><div class="bandeau-cell bandeau-icone" style="display:table-cell;padding-right:0.5em"><span class="noviewer" typeof="mw:File"><a href="/wiki/Aide:Homonymie" title="Aide:Homonymie"><img alt="Page d’aide sur l’homonymie" src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png" decoding="async" width="20" height="15" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/30px-Logo_disambig.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/40px-Logo_disambig.svg.png 2x" data-file-width="512" data-file-height="375" /></a></span></div><div class="bandeau-cell" style="display:table-cell;padding-right:0.5em"> <p>Pour les articles homonymes, voir <a href="/wiki/ABR" class="mw-disambig" title="ABR">ABR</a>, <a href="/wiki/Arbre_(homonymie)" class="mw-disambig" title="Arbre (homonymie)">Arbre (homonymie)</a> et <a href="/wiki/BST" class="mw-disambig" title="BST">BST</a>. </p> </div></div> <style data-mw-deduplicate="TemplateStyles:r222901683">.mw-parser-output .infobox hr{height:2px;background-color:#E1E1E1}.mw-parser-output .infobox_v3 .row1col{padding:4px;text-align:center;background-color:var(--background-color-neutral-subtle,#f8f9fa);color:var(--color-emphasized,#000000)}</style><div class="infobox_v3 infobox infobox--frwiki noarchive large"><div class="entete icon informatique" style="background-color:#ddd;color:#000"><div>Arbre binaire de recherche<style data-mw-deduplicate="TemplateStyles:r188801372">.mw-parser-output .entete.informatique{background-image:url("//upload.wikimedia.org/wikipedia/commons/a/ae/Picto-infoboxinfo.png")}</style></div></div><div><div class="images" style="padding:2px 0"><span class="mw-default-size" typeof="mw:File/Frameless"><a href="/w/index.php?title=Fichier:Binary_search_tree.svg&lang=fr" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/langfr-260px-Binary_search_tree.svg.png" decoding="async" width="260" height="217" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/langfr-390px-Binary_search_tree.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/langfr-520px-Binary_search_tree.svg.png 2x" data-file-width="300" data-file-height="250" /></a></span></div></div><table><tbody><tr class=""><th scope="row">Découvreur ou inventeur</th><td class=""><div> <span class="wd_p61"><a href="/wiki/Andrew_Booth" title="Andrew Booth">Andrew Donald Booth</a><span class="noprint wikidata-linkback skin-invert"><span class="mw-valign-baseline noviewer" typeof="mw:File"><a href="https://www.wikidata.org/wiki/Q623818?uselang=fr#P61" title="Voir et modifier les données sur Wikidata"><img alt="Voir et modifier les données sur Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/15px-Blue_pencil.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/20px-Blue_pencil.svg.png 2x" data-file-width="600" data-file-height="600" /></a></span></span></span></div></td></tr><tr class=""><th scope="row">Date de découverte</th><td class=""><div> <span class="wd_p575"><time datetime="1960" data-sort-value="1960" class="date-lien"><a href="/wiki/1960" title="1960">1960</a></time><span class="noprint wikidata-linkback skin-invert"><span class="mw-valign-baseline noviewer" typeof="mw:File"><a href="https://www.wikidata.org/wiki/Q623818?uselang=fr#P575" title="Voir et modifier les données sur Wikidata"><img alt="Voir et modifier les données sur Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/15px-Blue_pencil.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/20px-Blue_pencil.svg.png 2x" data-file-width="600" data-file-height="600" /></a></span></span></span></div></td></tr><tr class=""><th scope="row">Problème lié</th><td class=""><div> <span class="wd_p31"><a href="/wiki/Structure_de_donn%C3%A9es" title="Structure de données">Structure de données</a><span class="noprint wikidata-linkback skin-invert"><span class="mw-valign-baseline noviewer" typeof="mw:File"><a href="https://www.wikidata.org/wiki/Q623818?uselang=fr#P31" title="Voir et modifier les données sur Wikidata"><img alt="Voir et modifier les données sur Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/15px-Blue_pencil.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/20px-Blue_pencil.svg.png 2x" data-file-width="600" data-file-height="600" /></a></span></span></span></div></td></tr></tbody></table><table><caption style="color:#000;text-align:center;background-color:#ddd"><a href="/wiki/Complexit%C3%A9_en_espace" title="Complexité en espace">Complexité en espace</a></caption><tbody><tr class=""><th scope="row">Pire cas</th><td class=""><div> <span class="wd_p3755"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34109fe397fdcff370079185bfdb65826cb5565a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}"></span><span class="noprint wikidata-linkback skin-invert"><span class="mw-valign-baseline noviewer" typeof="mw:File"><a href="https://www.wikidata.org/wiki/Q623818?uselang=fr#P3755" title="Voir et modifier les données sur Wikidata"><img alt="Voir et modifier les données sur Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/15px-Blue_pencil.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/20px-Blue_pencil.svg.png 2x" data-file-width="600" data-file-height="600" /></a></span></span></span></div></td></tr><tr class=""><th scope="row">Moyenne</th><td class=""><div> <span class="wd_p3757"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(log(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>l</mi> <mi>o</mi> <mi>g</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(log(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c0bedb281b1771b1dad14e5916d4979f3b57c6b8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.724ex; height:2.843ex;" alt="{\displaystyle O(log(n))}"></span><span class="noprint wikidata-linkback skin-invert"><span class="mw-valign-baseline noviewer" typeof="mw:File"><a href="https://www.wikidata.org/wiki/Q623818?uselang=fr#P3757" title="Voir et modifier les données sur Wikidata"><img alt="Voir et modifier les données sur Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/15px-Blue_pencil.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/20px-Blue_pencil.svg.png 2x" data-file-width="600" data-file-height="600" /></a></span></span></span></div></td></tr></tbody></table><p class="navbar noprint bordered navigation-not-searchable" style="border-top:1px solid#ddd"><span class="plainlinks" style="text-align:left"><a class="external text" href="https://fr.wikipedia.org/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=0">modifier</a> - <a class="external text" href="https://fr.wikipedia.org/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=0">modifier le code</a> - <a href="https://www.wikidata.org/wiki/Q623818" class="extiw" title="d:Q623818">modifier Wikidata</a></span><span style="text-align:right"><span typeof="mw:File"><a href="/wiki/Mod%C3%A8le:Infobox_Algorithme" title="Documentation du modèle"><img alt="Documentation du modèle" src="//upload.wikimedia.org/wikipedia/commons/thumb/3/38/Info_Simple.svg/12px-Info_Simple.svg.png" decoding="async" width="12" height="12" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/38/Info_Simple.svg/18px-Info_Simple.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/38/Info_Simple.svg/24px-Info_Simple.svg.png 2x" data-file-width="512" data-file-height="512" /></a></span></span></p></div> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/Fichier:Binary_search_tree.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/245px-Binary_search_tree.svg.png" decoding="async" width="245" height="204" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/368px-Binary_search_tree.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/490px-Binary_search_tree.svg.png 2x" data-file-width="300" data-file-height="250" /></a><figcaption>Exemple d'un arbre binaire de recherche contenant 9 clés.</figcaption></figure> <p>En <a href="/wiki/Informatique" title="Informatique">informatique</a>, un <b>arbre binaire de recherche</b> ou <b>ABR</b> (en anglais, <i>binary search tree </i> ou <i>BST</i>) est une <a href="/wiki/Structure_de_donn%C3%A9es" title="Structure de données">structure de données</a> représentant un <a href="/wiki/Ensemble_(informatique)" title="Ensemble (informatique)">ensemble</a> ou un <a href="/wiki/Tableau_associatif" title="Tableau associatif">tableau associatif</a> dont les clés appartiennent à un <a href="/wiki/Ensemble_totalement_ordonn%C3%A9" title="Ensemble totalement ordonné">ensemble totalement ordonné</a>. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Définition"><span id="D.C3.A9finition"></span>Définition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=1" title="Modifier la section : Définition" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=1" title="Modifier le code source de la section : Définition"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Définition_générale"><span id="D.C3.A9finition_g.C3.A9n.C3.A9rale"></span>Définition générale</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=2" title="Modifier la section : Définition générale" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=2" title="Modifier le code source de la section : Définition générale"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Un arbre binaire de recherche est un <a href="/wiki/Arbre_(informatique)" class="mw-redirect" title="Arbre (informatique)">arbre</a> <a href="/wiki/Arbre_binaire" title="Arbre binaire">binaire</a> dans lequel chaque nœud possède une <a href="/wiki/Cl%C3%A9_(structure_de_donn%C3%A9es)" title="Clé (structure de données)">clé</a>, telle que chaque nœud du sous-arbre <i>gauche</i> ait une clé inférieure ou égale à celle du nœud considéré, et que chaque nœud du sous-arbre <i>droit</i> possède une clé supérieure ou égale à celle-ci — selon la mise en œuvre de l'ABR, on pourra interdire ou non des clés de valeur égale. Les nœuds que l'on ajoute deviennent des feuilles de l'arbre. </p> <div class="mw-heading mw-heading3"><h3 id="Définitions_spécifiques"><span id="D.C3.A9finitions_sp.C3.A9cifiques"></span>Définitions spécifiques</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=3" title="Modifier la section : Définitions spécifiques" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=3" title="Modifier le code source de la section : Définitions spécifiques"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>Un arbre binaire de recherche est dit complet si tous les niveaux de l'arbre sont remplis, sauf éventuellement le dernier, sur lequel les nœuds sont à gauche.</li></ul> <ul><li>Un arbre binaire parfait est un arbre complet dont toutes les feuilles sont à la même hauteur (le dernier niveau est complètement occupé).</li></ul> <ul><li>Un arbre binaire est dit dégénéré si chacun de ses nœuds a au plus un fils.</li></ul> <ul><li>Un arbre binaire est équilibré si tous les chemins de la racine aux feuilles ont la même longueur.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Opérations"><span id="Op.C3.A9rations"></span>Opérations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=4" title="Modifier la section : Opérations" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=4" title="Modifier le code source de la section : Opérations"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Recherche">Recherche</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=5" title="Modifier la section : Recherche" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=5" title="Modifier le code source de la section : Recherche"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Fichier:BinaryTreeRotations.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/4/43/BinaryTreeRotations.svg/220px-BinaryTreeRotations.svg.png" decoding="async" width="220" height="122" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/43/BinaryTreeRotations.svg/330px-BinaryTreeRotations.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/43/BinaryTreeRotations.svg/440px-BinaryTreeRotations.svg.png 2x" data-file-width="405" data-file-height="224" /></a><figcaption>La rotation est une opération permettant d'équilibrer les arbres.</figcaption></figure> <p>La recherche dans un arbre binaire d'un nœud ayant une clé particulière est un <a href="/wiki/Algorithme_r%C3%A9cursif" title="Algorithme récursif">procédé récursif</a>. On commence par examiner la racine. Si sa clé est la clé recherchée, l'algorithme se termine et renvoie la racine. Si elle est strictement inférieure, alors elle est dans le sous-arbre gauche, sur lequel on effectue alors récursivement la recherche. De même si la clé recherchée est strictement supérieure à la clé de la racine, la recherche continue dans le sous-arbre droit. Si on atteint une feuille dont la clé n'est pas celle recherchée, on sait alors que la clé recherchée n'appartient à aucun nœud, elle ne figure donc pas dans l'arbre de recherche. On peut comparer l'exploration d'un arbre binaire de recherche avec la <a href="/wiki/Recherche_par_dichotomie" class="mw-redirect" title="Recherche par dichotomie">recherche par dichotomie</a> qui procède à peu près de la même manière sauf qu'elle accède directement à chaque élément d'un tableau au lieu de suivre des liens. La différence entre les deux algorithmes est que, dans la recherche dichotomique, on suppose avoir un critère de découpage de l'espace en deux parties que l'on n'a pas dans la recherche dans un arbre. </p><p><br /> ‎ </p> <table class="wikitable alternance"> <caption> </caption> <tbody><tr> <td><b>Entrée = </b>Un arbre binaire de recherche A, une clé e.<br /><b>Sortie = </b>Vrai si la clé est dans l’arbre, faux sinon </td></tr> <tr> <td width="90%"><span style="color:blue"><b>fonction</b></span> Recherche(A,e)<br />        <span style="color:darkviolet"><b>si</b></span> A <span style="color:green"><b>=</b></span> .<br />            <span style="color:green"><b>renvoyer</b></span> Faux<br />        <span style="color:darkviolet"><b>sinon</b></span> A <span style="color:green"><b>=</b></span> (x,FilsGauche,FilsDroit)<br />            <span style="color:darkviolet"><b>si</b></span> x <span style="color:green"><b>=</b></span> e<br />                <span style="color:green"><b>renvoyer</b></span> Vrai<br />            <span style="color:darkviolet"><b>sinon</b></span> <span style="color:darkviolet"><b>si</b></span> e <span style="color:green"><b><</b></span> x<br />                <span style="color:green"><b>renvoyer</b></span> Recherche(FilsGauche,e)<br />            <span style="color:darkviolet"><b>sinon</b></span><br />                <span style="color:green"><b>renvoyer</b></span> Recherche(FilsDroit,e) </td></tr></tbody></table> <p><br /> </p><p>Cette opération requiert un temps en <i>O(log(n))</i> dans le cas moyen, mais <i>O(n)</i> dans le cas critique où l'arbre est complètement <a href="/wiki/Arbre_%C3%A9quilibr%C3%A9" title="Arbre équilibré">déséquilibré</a> et ressemble à une liste chaînée. Ce problème est écarté si l'arbre <a href="/wiki/Rotation_d%27un_arbre_binaire_de_recherche" title="Rotation d'un arbre binaire de recherche">est équilibré par rotation</a> au fur et à mesure des insertions pouvant créer des listes trop longues. </p> <div class="mw-heading mw-heading3"><h3 id="Insertion">Insertion</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=6" title="Modifier la section : Insertion" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=6" title="Modifier le code source de la section : Insertion"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>L'insertion d'un nœud commence par une recherche : on cherche la clé du nœud à insérer ; lorsqu'on arrive à une feuille, on ajoute le nœud comme fils de la feuille en comparant sa clé à celle de la feuille : si elle est inférieure, le nouveau nœud sera à gauche ; sinon il sera à droite. </p> <div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span>fonction Insertion(A,e) Si A = . retourner (e,.,.) Sinon A = (x,FilsGauche,FilsDroit) Si e < x retourner (x,Insertion(FilsGauche,e),FilsDroit) Sinon retourner (x,FilsGauche,Insertion(FilsDroit,e)) </pre></div> <p>La complexité est la même que pour la recherche : <i>O(log n)</i> dans le cas moyen et <i>O(n)</i> dans le cas critique. </p><p>Il est aussi possible d'écrire une procédure d'ajout d'élément à la racine d'un arbre binaire. Cette opération requiert la même complexité mais est meilleure en termes d'accès aux éléments. </p> <div class="mw-heading mw-heading3"><h3 id="Suppression">Suppression</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=7" title="Modifier la section : Suppression" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=7" title="Modifier le code source de la section : Suppression"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>On commence par rechercher la clé du noeud à supprimer dans l'arbre. Plusieurs cas sont à considérer, une fois que le nœud à supprimer a été trouvé à partir de sa clé : </p> <ul><li><i>Suppression d'une feuille</i> : Il suffit de l'enlever de l'arbre puisqu'elle n'a pas de fils.</li> <li><i>Suppression d'un nœud avec un enfant</i> : Il faut l'enlever de l'arbre en le remplaçant par son fils.</li> <li><i>Suppression d'un nœud avec deux enfants</i> : Supposons que le nœud à supprimer soit appelé <i>N</i> (le nœud de valeur 7 dans le graphique ci-dessous). On échange le nœud N avec son successeur le plus proche (le nœud le plus à gauche du sous-arbre droit, ci-dessous, le nœud de valeur 9) ou son plus proche prédécesseur (le nœud le plus à droite du sous-arbre gauche, ci-dessous, le nœud de valeur 6). Cela permet de garder à la fin de l'opération une structure d'arbre binaire de recherche. Puis on applique à nouveau la procédure de suppression à <i>N</i>, qui est maintenant une feuille ou un nœud avec un seul fils.</li></ul> <center> <p><span class="mw-default-size" typeof="mw:File"><a href="/wiki/Fichier:Suppresion_dans_ABR.png" class="mw-file-description" title="Suppression d'un nœud interne avec deux enfants dans un arbre binaire de recherche"><img alt="Suppression d'un nœud interne avec deux enfants dans un arbre binaire de recherche" src="//upload.wikimedia.org/wikipedia/commons/4/4d/Suppresion_dans_ABR.png" decoding="async" width="400" height="124" class="mw-file-element" data-file-width="400" data-file-height="124" /></a></span> </p> </center> <div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span>fonction Suppression(A,e) si A = . retourner . sinon A = (x,FilsGauche,FilsDroit) si e > x retourner (x,FilsGauche,Suppression(FilsDroit,e)) si e < x retourner (x,Suppression(FilsGauche,e),FilsDroit) sinon x = e si FilsGauche = . et FilsDroit = . retourner . si FilsGauche = . retourner FilsDroit si FilsDroit = . retourner FilsGauche sinon y = Max(FilsGauche) retourner (y,Suppression(FilsGauche,y),FilsDroit) </pre></div> <p>Ce choix d'implémentation peut contribuer à <a href="/wiki/Arbre_%C3%A9quilibr%C3%A9" title="Arbre équilibré">déséquilibrer</a> l'arbre. En effet, puisque ce sont toujours des feuilles du sous-arbre gauche qui sont supprimées, une utilisation fréquente de cette fonction amènera à un arbre plus lourd à droite qu'à gauche. On peut remédier à cela en alternant successivement la suppression du minimum du fils droit avec celle du maximum du fils gauche, plutôt que toujours choisir ce dernier. Il est par exemple possible d'utiliser un facteur aléatoire : le programme aura une chance sur deux de choisir le fils droit et une chance sur deux de choisir le fils gauche. </p><p>Dans tous les cas cette opération requiert de parcourir l'arbre de la racine jusqu'à une feuille : le temps d'exécution est donc proportionnel à la profondeur de l'arbre qui vaut <i>n</i> dans le pire des cas, d'où une complexité maximale en <i>O(n)</i>. </p> <div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=8" title="Modifier la section : Applications" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=8" title="Modifier le code source de la section : Applications"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Parcours_ordonné"><span id="Parcours_ordonn.C3.A9"></span>Parcours ordonné</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=9" title="Modifier la section : Parcours ordonné" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=9" title="Modifier le code source de la section : Parcours ordonné"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Il est possible de parcourir en profondeur un arbre binaire de recherche de trois manières : un parcours infixe, préfixe ou postfixe. Ces trois algorithmes fonctionnent usuellement<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite_crochet">[</span>1<span class="cite_crochet">]</span></a></sup> de manière <a href="/wiki/Algorithme_r%C3%A9cursif" title="Algorithme récursif">récursive</a>. Le parcours infixe consiste à, dans l'ordre, faire le parcours infixe du sous-arbre de gauche, récupérer la valeur du nœud, puis faire le parcours infixe du sous-arbre de droite. Alors que le parcours préfixe commence par récupérer la valeur du nœud, puis parcourt le sous-arbre de gauche, puis le sous-arbre de droite. Le parcours postfixe commence par le sous-arbre de gauche, puis le sous-arbre de droite, et récupère la valeur du nœud. Dans les trois cas, le parcours de l'arbre se fait en temps linéaire, puisqu'il doit passer par chaque nœud une seule fois. </p> <div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span>fonction ParcoursInfixe(A): si A = . retourner [] sinon A = (x,FilsGauche,FilsDroit) retourner ParcoursInfixe(FilsGauche) + [x] + ParcoursInfixe(FilsDroit) </pre></div> <div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span>fonction ParcoursPréfixe(A): si A = . retourner [] sinon A = (x,FilsGauche,FilsDroit) retourner [x] + ParcoursPréfixe(FilsGauche) + ParcoursPréfixe(FilsDroit) </pre></div> <div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span>fonction ParcoursPostfixe(A): si A = . retourner [] sinon A = (x,FilsGauche,FilsDroit) retourner ParcoursPostfixe(FilsGauche) + ParcoursPostfixe(FilsDroit) + [x] </pre></div> <div class="mw-heading mw-heading3"><h3 id="Tri">Tri</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=10" title="Modifier la section : Tri" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=10" title="Modifier le code source de la section : Tri"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>On peut dès lors créer un <a href="/wiki/Algorithme_de_tri" title="Algorithme de tri">algorithme de tri</a> simple mais peu efficace, en insérant toutes les clés que l'on veut trier dans un nouvel arbre binaire de recherche puis en parcourant de manière ordonnée cet arbre comme ci-dessus. </p> <div class="mw-highlight mw-highlight-lang-text mw-content-ltr" dir="ltr"><pre><span></span>A = . pour e dans L faire A = Insertion(A,e) ListeTriee = ParcoursInfixe(A) </pre></div> <p>Le pire temps d'exécution est en <i>O(n²)</i> où <i>n</i> est le nombre de clés de l'arbre, obtenu lorsque les clés sont déjà ordonnées : on a alors une liste chaînée. Par exemple, si on donne dans cet ordre les clés 1, 2, 3, 4, 5, on obtient l'arbre <i>(Vide, 1, (Vide, 2, (Vide, 3, (Vide, 4, (Vide, 5, Vide)))))</i>. Il y a de nombreuses façons d'éviter ce problème, la plus commune étant l'arbre équilibré. On peut alors arriver à un pire cas en <i>O(n*ln(n)).</i> </p> <div class="mw-heading mw-heading3"><h3 id="Files_de_priorité"><span id="Files_de_priorit.C3.A9"></span>Files de priorité</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=11" title="Modifier la section : Files de priorité" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=11" title="Modifier le code source de la section : Files de priorité"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Les arbres binaires de recherche peuvent servir d’implémentation au <a href="/wiki/Type_abstrait" title="Type abstrait">type abstrait</a> de <a href="/wiki/File_de_priorit%C3%A9" title="File de priorité">file de priorité</a>. en effet, les opérations d’insertion d’une clé et de test au vide se font avec des complexités avantageuses (respectivement en <i>O(log(n))</i> et en <i>O(1)</i> où <i>n</i> est le nombre de clés représentées dans l’arbre). Pour l’opération de suppression de la plus grande clé, il suffit de parcourir l’arbre depuis sa racine en choisissant le fils droit de chaque noeud, et supprimer la feuille terminale. cela demande un nombre d’opérations égal à la hauteur de l’arbre, donc une complexité logarithmique en le nombre de clés. L’avantage notoire de cette représentation d’une file de priorité est qu’avec un processus similaire, on dispose d'une opération de suppression de la plus petite clé en temps logarithmique également. </p> <div class="mw-heading mw-heading2"><h2 id="Equilibrage">Equilibrage</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=12" title="Modifier la section : Equilibrage" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=12" title="Modifier le code source de la section : Equilibrage"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>L'insertion et la suppression s'exécutent en <i>O(h)</i> où <i>h</i> est la hauteur de l'arbre. Cela s'avère particulièrement coûteux quand l'arbre est très déséquilibré (un arbre peigne par exemple, dont la hauteur est linéaire en le nombre de clés), et on gagne donc en efficacité à équilibrer les arbres au cours de leur utilisation. Il existe des techniques pour obtenir des <a href="/wiki/Arbre_%C3%A9quilibr%C3%A9" title="Arbre équilibré">arbres équilibrés</a>, c'est-à-dire pour garantir une hauteur logarithmique en nombre d'éléments : </p> <ul><li>Les <a href="/wiki/Arbre_AVL" title="Arbre AVL">arbres AVL</a></li> <li>les <a href="/wiki/Arbre_rouge-noir" class="mw-redirect" title="Arbre rouge-noir">arbres rouge-noir</a></li> <li>les arbres 2-3</li> <li>les <a href="/wiki/Arbre_2-3-4" title="Arbre 2-3-4">arbres 2-3-4</a></li> <li>les <a href="/wiki/Arbre_B" title="Arbre B">B-arbres</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Extensions">Extensions</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=13" title="Modifier la section : Extensions" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=13" title="Modifier le code source de la section : Extensions"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Un <i><a href="/wiki/Arbre_splay" title="Arbre splay">arbre splay</a></i> est un arbre binaire de recherche qui rapproche automatiquement de la racine les éléments utilisés fréquemment. Dans un <i><a href="/wiki/Treap" title="Treap">treap</a></i>, chaque nœud possède aussi une priorité supérieure à chacun de ses fils.<br /> </p> <div class="mw-heading mw-heading2"><h2 id="Notes_et_références"><span id="Notes_et_r.C3.A9f.C3.A9rences"></span>Notes et références</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=14" title="Modifier la section : Notes et références" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=14" title="Modifier le code source de la section : Notes et références"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="references-small decimal" style=""><div class="mw-references-wrap"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a> </span><span class="reference-text">On peut en faire une version impérative en manipulant explicitement une pile, présente implicitement pour les appels récursifs.</span> </li> </ol></div> </div> <div class="mw-heading mw-heading2"><h2 id="Liens_externes">Liens externes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Arbre_binaire_de_recherche&veaction=edit&section=15" title="Modifier la section : Liens externes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Arbre_binaire_de_recherche&action=edit&section=15" title="Modifier le code source de la section : Liens externes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a rel="nofollow" class="external text" href="http://cslibrary.stanford.edu/110/">Une introduction aux arbres binaires de recherche</a></li></ul> <div class="navbox-container" style="clear:both;"> <table class="navbox collapsible noprint autocollapse" style=""> <tbody><tr><th class="navbox-title" colspan="2" style=""><div style="float:left; width:6em; text-align:left"><div class="noprint plainlinks nowrap tnavbar" style="padding:0; font-size:xx-small; color:var(--color-emphasized, #000000);"><a href="/wiki/Mod%C3%A8le:Palette_Arbres_informatiques" title="Modèle:Palette Arbres informatiques"><abbr class="abbr" title="Voir ce modèle.">v</abbr></a> · <a class="external text" href="https://fr.wikipedia.org/w/index.php?title=Mod%C3%A8le:Palette_Arbres_informatiques&action=edit"><abbr class="abbr" title="Modifier ce modèle. Merci de prévisualiser avant de sauvegarder.">m</abbr></a></div></div><div style="font-size:110%"><a href="/wiki/Arbre_enracin%C3%A9" title="Arbre enraciné">Arbre enraciné</a></div></th> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Arbre_binaire" title="Arbre binaire">Arbre binaire</a></th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a class="mw-selflink selflink">Arbre binaire de recherche</a></li> <li><a href="/wiki/Arbre_de_fouille" title="Arbre de fouille">Arbre de fouille</a></li> <li><a href="/wiki/Arbre_cart%C3%A9sien" title="Arbre cartésien">Arbre cartésien</a></li> <li><a href="/w/index.php?title=MVP_Tree&action=edit&redlink=1" class="new" title="MVP Tree (page inexistante)">MVP Tree</a> <a href="https://en.wikipedia.org/wiki/MVP_Tree" class="extiw" title="en:MVP Tree"><span class="indicateur-langue" title="Article en anglais : « MVP Tree »">(en)</span></a></li> <li><a href="/w/index.php?title=Top_tree&action=edit&redlink=1" class="new" title="Top tree (page inexistante)">Top tree</a> <a href="https://en.wikipedia.org/wiki/Top_tree" class="extiw" title="en:Top tree"><span class="indicateur-langue" title="Article en anglais : « Top tree »">(en)</span></a></li> <li><a href="/w/index.php?title=T-tree&action=edit&redlink=1" class="new" title="T-tree (page inexistante)">T-tree</a> <a href="https://en.wikipedia.org/wiki/T-tree" class="extiw" title="en:T-tree"><span class="indicateur-langue" title="Article en anglais : « T-tree »">(en)</span></a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Arbre_%C3%A9quilibr%C3%A9" title="Arbre équilibré">Arbre équilibré</a></th> <td class="navbox-list navbox-even" style=""><div class="liste-horizontale"> <ul><li><a href="/w/index.php?title=AA_tree&action=edit&redlink=1" class="new" title="AA tree (page inexistante)">AA tree</a> <a href="https://en.wikipedia.org/wiki/AA_tree" class="extiw" title="en:AA tree"><span class="indicateur-langue" title="Article en anglais : « AA tree »">(en)</span></a></li> <li><a href="/wiki/Arbre_AVL" title="Arbre AVL">Arbre AVL</a></li> <li><a href="/w/index.php?title=LLRB_tree&action=edit&redlink=1" class="new" title="LLRB tree (page inexistante)">LLRB tree</a> <a href="https://en.wikipedia.org/wiki/LLRB_tree" class="extiw" title="en:LLRB tree"><span class="indicateur-langue" title="Article en anglais : « LLRB tree »">(en)</span></a></li> <li><a href="/wiki/Arbre_bicolore" title="Arbre bicolore">Arbre bicolore</a></li> <li><a href="/wiki/Arbre_bouc-%C3%A9missaire" title="Arbre bouc-émissaire">Arbre bouc-émissaire</a></li> <li><a href="/wiki/Arbre_splay" title="Arbre splay">Arbre splay</a></li> <li><a href="/wiki/Treap" title="Treap">Treap</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Arbre_B" title="Arbre B">Arbre B</a></th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a href="/w/index.php?title=B*-tree&action=edit&redlink=1" class="new" title="B*-tree (page inexistante)">B*-tree</a> <a href="https://en.wikipedia.org/wiki/B*-tree" class="extiw" title="en:B*-tree"><span class="indicateur-langue" title="Article en anglais : « B*-tree »">(en)</span></a></li> <li><a href="/w/index.php?title=Bx-tree&action=edit&redlink=1" class="new" title="Bx-tree (page inexistante)">Bx-tree</a> <a href="https://en.wikipedia.org/wiki/Bx-tree" class="extiw" title="en:Bx-tree"><span class="indicateur-langue" title="Article en anglais : « Bx-tree »">(en)</span></a></li> <li><a href="/w/index.php?title=UB-tree&action=edit&redlink=1" class="new" title="UB-tree (page inexistante)">UB-tree</a> <a href="https://en.wikipedia.org/wiki/UB-tree" class="extiw" title="en:UB-tree"><span class="indicateur-langue" title="Article en anglais : « UB-tree »">(en)</span></a></li> <li><a href="/w/index.php?title=2-3_tree&action=edit&redlink=1" class="new" title="2-3 tree (page inexistante)">2-3 tree</a> <a href="https://en.wikipedia.org/wiki/2-3_tree" class="extiw" title="en:2-3 tree"><span class="indicateur-langue" title="Article en anglais : « 2-3 tree »">(en)</span></a></li> <li><a href="/wiki/Arbre_2-3-4" title="Arbre 2-3-4">Arbre 2-3-4</a></li> <li><a href="/w/index.php?title=(a,b)-tree&action=edit&redlink=1" class="new" title="(a,b)-tree (page inexistante)">(a,b)-tree</a> <a href="https://en.wikipedia.org/wiki/(a,b)-tree" class="extiw" title="en:(a,b)-tree"><span class="indicateur-langue" title="Article en anglais : « (a,b)-tree »">(en)</span></a></li> <li><a href="/wiki/Dancing_tree" title="Dancing tree">Dancing tree</a></li> <li><a href="/w/index.php?title=Htree&action=edit&redlink=1" class="new" title="Htree (page inexistante)">Htree</a> <a href="https://en.wikipedia.org/wiki/Htree" class="extiw" title="en:Htree"><span class="indicateur-langue" title="Article en anglais : « Htree »">(en)</span></a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Trie_(informatique)" title="Trie (informatique)">Trie</a></th> <td class="navbox-list navbox-even" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Arbre_des_suffixes" title="Arbre des suffixes">Arbre des suffixes</a></li> <li><a href="/wiki/Arbre_radix" title="Arbre radix">Arbre radix</a></li> <li><a href="/wiki/Arbre_ternaire_de_recherche" title="Arbre ternaire de recherche">Arbre ternaire de recherche</a></li> <li><a href="/w/index.php?title=X-fast_trie&action=edit&redlink=1" class="new" title="X-fast trie (page inexistante)">X-fast trie</a> <a href="https://en.wikipedia.org/wiki/X-fast_trie" class="extiw" title="en:X-fast trie"><span class="indicateur-langue" title="Article en anglais : « X-fast trie »">(en)</span></a></li> <li><a href="/w/index.php?title=Y-fast_trie&action=edit&redlink=1" class="new" title="Y-fast trie (page inexistante)">Y-fast trie</a> <a href="https://en.wikipedia.org/wiki/Y-fast_trie" class="extiw" title="en:Y-fast trie"><span class="indicateur-langue" title="Article en anglais : « Y-fast trie »">(en)</span></a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Partition_binaire_de_l%27espace" title="Partition binaire de l'espace">Partition binaire de l'espace</a> trees</th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Quadtree" title="Quadtree">Quadtree</a></li> <li><a href="/wiki/Octree" title="Octree">Octree</a></li> <li><a href="/wiki/Arbre_kd" title="Arbre kd">Arbre kd</a> (<a href="/wiki/Arbre_kd_relax%C3%A9" title="Arbre kd relaxé">relaxé</a>)</li> <li><a href="/w/index.php?title=Implicit_k-d_tree&action=edit&redlink=1" class="new" title="Implicit k-d tree (page inexistante)">Implicit k-d tree</a> <a href="https://en.wikipedia.org/wiki/Implicit_k-d_tree" class="extiw" title="en:Implicit k-d tree"><span class="indicateur-langue" title="Article en anglais : « Implicit k-d tree »">(en)</span></a></li> <li><a href="/wiki/Vantage_point_tree" title="Vantage point tree"> Vp-tree</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style="">Arbres non binaires</th> <td class="navbox-list navbox-even" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Arbre_exponentiel" title="Arbre exponentiel">Arbre exponentiel</a></li> <li><a href="/w/index.php?title=Fusion_tree&action=edit&redlink=1" class="new" title="Fusion tree (page inexistante)">Fusion tree</a> <a href="https://en.wikipedia.org/wiki/Fusion_tree" class="extiw" title="en:Fusion tree"><span class="indicateur-langue" title="Article en anglais : « Fusion tree »">(en)</span></a></li> <li><a href="/wiki/Arbre_d%27intervalles" title="Arbre d'intervalles">arbre d'intervalles</a></li> <li><a href="/wiki/Arbre_PQ" title="Arbre PQ">arbre PQ</a></li> <li><a href="/wiki/Arbre_de_port%C3%A9e" title="Arbre de portée">arbre de portée (<i>range tree</i>)</a></li> <li><a href="/wiki/Arbre_SPQR" title="Arbre SPQR">arbre SPQR</a></li> <li><a href="/wiki/Arbre_de_Van_Emde_Boas" title="Arbre de Van Emde Boas">arbre de Van Emde Boas</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style="">Arbre de <a href="/wiki/Base_de_donn%C3%A9es_spatiales" title="Base de données spatiales">base de données spatiales</a></th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/R-arbre" title="R-arbre">R-arbre</a></li> <li><a href="/w/index.php?title=R%2B_tree&action=edit&redlink=1" class="new" title="R+ tree (page inexistante)">R+ tree</a> <a href="https://en.wikipedia.org/wiki/R%2B_tree" class="extiw" title="en:R+ tree"><span class="indicateur-langue" title="Article en anglais : « R+ tree »">(en)</span></a></li> <li><a href="/w/index.php?title=R*_tree&action=edit&redlink=1" class="new" title="R* tree (page inexistante)">R* tree</a> <a href="https://en.wikipedia.org/wiki/R*_tree" class="extiw" title="en:R* tree"><span class="indicateur-langue" title="Article en anglais : « R* tree »">(en)</span></a></li> <li><a href="/w/index.php?title=X-tree&action=edit&redlink=1" class="new" title="X-tree (page inexistante)">X-tree</a> <a href="https://en.wikipedia.org/wiki/X-tree" class="extiw" title="en:X-tree"><span class="indicateur-langue" title="Article en anglais : « X-tree »">(en)</span></a></li> <li><a href="/w/index.php?title=M-tree&action=edit&redlink=1" class="new" title="M-tree (page inexistante)">M-tree</a> <a href="https://en.wikipedia.org/wiki/M-tree" class="extiw" title="en:M-tree"><span class="indicateur-langue" title="Article en anglais : « M-tree »">(en)</span></a></li> <li><a href="/wiki/Arbre_de_segments" title="Arbre de segments">arbre de segments</a></li> <li><a href="/w/index.php?title=Hilbert_R-tree&action=edit&redlink=1" class="new" title="Hilbert R-tree (page inexistante)">Hilbert R-tree</a> <a href="https://en.wikipedia.org/wiki/Hilbert_R-tree" class="extiw" title="en:Hilbert R-tree"><span class="indicateur-langue" title="Article en anglais : « Hilbert R-tree »">(en)</span></a></li> <li><a href="/w/index.php?title=Priority_R-tree&action=edit&redlink=1" class="new" title="Priority R-tree (page inexistante)">Priority R-tree</a> <a href="https://en.wikipedia.org/wiki/Priority_R-tree" class="extiw" title="en:Priority R-tree"><span class="indicateur-langue" title="Article en anglais : « Priority R-tree »">(en)</span></a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style="">Autres arbres</th> <td class="navbox-list navbox-even" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Arbre_de_Merkle" title="Arbre de Merkle">Arbre de Merkle</a></li> <li><a href="/wiki/Arbre_couvrant_de_poids_minimal" title="Arbre couvrant de poids minimal">Arbre couvrant de poids minimal</a></li> <li><a href="/wiki/Arbre_syntaxique" title="Arbre syntaxique">Arbre syntaxique</a></li> <li><a href="/wiki/Arbre_de_la_syntaxe_abstraite" title="Arbre de la syntaxe abstraite">Arbre de la syntaxe abstraite</a></li> <li><a href="/w/index.php?title=Finger_tree&action=edit&redlink=1" class="new" title="Finger tree (page inexistante)">Finger tree</a> <a href="https://en.wikipedia.org/wiki/Finger_tree" class="extiw" title="en:Finger tree"><span class="indicateur-langue" title="Article en anglais : « Finger tree »">(en)</span></a></li> <li><a href="/w/index.php?title=Order_statistic_tree&action=edit&redlink=1" class="new" title="Order statistic tree (page inexistante)">Order statistic tree</a> <a href="https://en.wikipedia.org/wiki/Order_statistic_tree" class="extiw" title="en:Order statistic tree"><span class="indicateur-langue" title="Article en anglais : « Order statistic tree »">(en)</span></a></li> <li><a href="/wiki/Arbre_m%C3%A9trique" title="Arbre métrique">Arbre métrique</a></li> <li><a href="/w/index.php?title=Cover_tree&action=edit&redlink=1" class="new" title="Cover tree (page inexistante)">Cover tree</a> <a href="https://en.wikipedia.org/wiki/Cover_tree" class="extiw" title="en:Cover tree"><span class="indicateur-langue" title="Article en anglais : « Cover tree »">(en)</span></a></li> <li><a href="/w/index.php?title=BK-tree&action=edit&redlink=1" class="new" title="BK-tree (page inexistante)">BK-tree</a> <a href="https://en.wikipedia.org/wiki/BK-tree" class="extiw" title="en:BK-tree"><span class="indicateur-langue" title="Article en anglais : « BK-tree »">(en)</span></a></li> <li><a href="/wiki/Doubly_chained_tree" title="Doubly chained tree">Doubly chained tree</a></li> <li><a href="/w/index.php?title=IDistance&action=edit&redlink=1" class="new" title="IDistance (page inexistante)">iDistance</a> <a href="https://en.wikipedia.org/wiki/iDistance" class="extiw" title="en:iDistance"><span class="indicateur-langue" title="Article en anglais : « iDistance »">(en)</span></a></li> <li><a href="/w/index.php?title=Link-cut_tree&action=edit&redlink=1" class="new" title="Link-cut tree (page inexistante)">Link-cut tree</a> <a href="https://en.wikipedia.org/wiki/Link-cut_tree" class="extiw" title="en:Link-cut tree"><span class="indicateur-langue" title="Article en anglais : « Link-cut tree »">(en)</span></a></li> <li><a href="/w/index.php?title=Fenwick_tree&action=edit&redlink=1" class="new" title="Fenwick tree (page inexistante)">Fenwick tree</a> <a href="https://en.wikipedia.org/wiki/Fenwick_tree" class="extiw" title="en:Fenwick tree"><span class="indicateur-langue" title="Article en anglais : « Fenwick tree »">(en)</span></a></li> <li><a href="/wiki/Tas_(informatique)" title="Tas (informatique)">Tas</a> <ul><li><a href="/wiki/Tas_binaire" title="Tas binaire">Binaire</a></li> <li><a href="/wiki/Tas_binomial" title="Tas binomial">Binomial</a></li> <li><a href="/wiki/Tas_de_Fibonacci" title="Tas de Fibonacci">Fibonacci</a></li></ul></li> <li><a href="/wiki/Arbre_cousu" title="Arbre cousu">Arbre cousu</a></li></ul> </div></td> </tr> </tbody></table> <table class="navbox collapsible noprint autocollapse" style=""> <tbody><tr><th class="navbox-title" colspan="2" style=""><div style="float:left; width:6em; text-align:left"><div class="noprint plainlinks nowrap tnavbar" style="padding:0; font-size:xx-small; color:var(--color-emphasized, #000000);"><a href="/wiki/Mod%C3%A8le:Palette_Structure_de_donn%C3%A9es" title="Modèle:Palette Structure de données"><abbr class="abbr" title="Voir ce modèle.">v</abbr></a> · <a class="external text" href="https://fr.wikipedia.org/w/index.php?title=Mod%C3%A8le:Palette_Structure_de_donn%C3%A9es&action=edit"><abbr class="abbr" title="Modifier ce modèle. Merci de prévisualiser avant de sauvegarder.">m</abbr></a></div></div><div style="font-size:110%"><a href="/wiki/Structure_de_donn%C3%A9es" title="Structure de données">Structure de données</a></div></th> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Type_abstrait" title="Type abstrait">Type abstrait</a></th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Ensemble_(informatique)" title="Ensemble (informatique)">Ensemble</a></li> <li><a href="/wiki/File_(structure_de_donn%C3%A9es)" title="File (structure de données)">File</a></li> <li><a href="/wiki/File_d%27attente_%C3%A0_double_extr%C3%A9mit%C3%A9" title="File d'attente à double extrémité">File d'attente à double extrémité</a></li> <li><a href="/wiki/File_de_priorit%C3%A9" title="File de priorité">File de priorité</a></li> <li><a href="/wiki/Liste_(informatique)" title="Liste (informatique)">Liste</a></li> <li><a href="/wiki/Vecteur_(structure_de_donn%C3%A9es)" title="Vecteur (structure de données)">Vecteur</a></li> <li><a href="/wiki/Graphe_(type_abstrait)" title="Graphe (type abstrait)">Graphe</a></li> <li><a href="/wiki/Union-find" title="Union-find">Union-find</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Tableau_(structure_de_donn%C3%A9es)" title="Tableau (structure de données)">Tableau</a></th> <td class="navbox-list navbox-even" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Buffer_circulaire" title="Buffer circulaire">Buffer circulaire</a></li> <li><a href="/wiki/Tableau_de_bits" title="Tableau de bits">Tableau de bits</a></li> <li><a href="/wiki/Table_de_hachage" title="Table de hachage">Table de hachage</a></li> <li><a href="/wiki/Vecteur_(structure_de_donn%C3%A9es)" title="Vecteur (structure de données)">Vecteur</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style="">Chaînage</th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Liste_cha%C3%AEn%C3%A9e" title="Liste chaînée">Liste chaînée</a></li> <li><a href="/wiki/Skip_list" title="Skip list">Skip list</a></li> <li><a href="/wiki/Cha%C3%AEnage_XOR" title="Chaînage XOR">Chaînage XOR</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Arbre_enracin%C3%A9" title="Arbre enraciné">Arbre</a></th> <td class="navbox-list navbox-even" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Arbre_B" title="Arbre B">Arbre B</a></li> <li><a class="mw-selflink selflink">Arbre binaire de recherche</a> <ul><li><a href="/wiki/Arbre_AVL" title="Arbre AVL">AVL</a></li> <li><a href="/wiki/Arbre_bicolore" title="Arbre bicolore">Bicolore</a></li> <li><a href="/wiki/Arbre_%C3%A9quilibr%C3%A9" title="Arbre équilibré">Équilibré</a></li> <li><a href="/wiki/Arbre_splay" title="Arbre splay">Splay</a></li></ul></li> <li><a href="/wiki/Tas_(informatique)" title="Tas (informatique)">Tas</a> <ul><li><a href="/wiki/Tas_binaire" title="Tas binaire">Binaire</a></li> <li><a href="/wiki/Tas_binomial" title="Tas binomial">Binomial</a></li> <li><a href="/wiki/Tas_de_Fibonacci" title="Tas de Fibonacci">Fibonacci</a></li></ul></li> <li><a href="/wiki/Trie_(informatique)" title="Trie (informatique)">Trie</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Th%C3%A9orie_des_graphes" title="Théorie des graphes">Graphe</a></th> <td class="navbox-list" style=""><a href="/wiki/Diagramme_de_d%C3%A9cision_binaire" title="Diagramme de décision binaire">Diagramme de décision binaire</a></td> </tr> </tbody></table> </div> <ul id="bandeau-portail" class="bandeau-portail"><li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><span class="noviewer skin-invert-image" typeof="mw:File"><a href="/wiki/Portail:Informatique_th%C3%A9orique" title="Portail de l'informatique théorique"><img alt="icône décorative" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/30px-Max-cut.svg.png" decoding="async" width="30" height="24" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/45px-Max-cut.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/60px-Max-cut.svg.png 2x" data-file-width="200" data-file-height="160" /></a></span></span> <span class="bandeau-portail-texte"><a href="/wiki/Portail:Informatique_th%C3%A9orique" title="Portail:Informatique théorique">Portail de l'informatique théorique</a></span> </span></li> </ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Ce document provient de « <a dir="ltr" href="https://fr.wikipedia.org/w/index.php?title=Arbre_binaire_de_recherche&oldid=219902427">https://fr.wikipedia.org/w/index.php?title=Arbre_binaire_de_recherche&oldid=219902427</a> ».</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Cat%C3%A9gorie:Accueil" title="Catégorie:Accueil">Catégorie</a> : <ul><li><a href="/wiki/Cat%C3%A9gorie:Arbre_(structure_de_donn%C3%A9es)" title="Catégorie:Arbre (structure de données)">Arbre (structure de données)</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Catégories cachées : <ul><li><a href="/wiki/Cat%C3%A9gorie:Page_utilisant_P61" title="Catégorie:Page utilisant P61">Page utilisant P61</a></li><li><a href="/wiki/Cat%C3%A9gorie:Page_utilisant_P575" title="Catégorie:Page utilisant P575">Page utilisant P575</a></li><li><a href="/wiki/Cat%C3%A9gorie:Page_utilisant_P31" title="Catégorie:Page utilisant P31">Page utilisant P31</a></li><li><a href="/wiki/Cat%C3%A9gorie:Page_utilisant_P3755" title="Catégorie:Page utilisant P3755">Page utilisant P3755</a></li><li><a href="/wiki/Cat%C3%A9gorie:Page_utilisant_P3757" title="Catégorie:Page utilisant P3757">Page utilisant P3757</a></li><li><a href="/wiki/Cat%C3%A9gorie:Page_utilisant_P18" title="Catégorie:Page utilisant P18">Page utilisant P18</a></li><li><a href="/wiki/Cat%C3%A9gorie:Article_utilisant_l%27infobox_Algorithme" title="Catégorie:Article utilisant l'infobox Algorithme">Article utilisant l'infobox Algorithme</a></li><li><a href="/wiki/Cat%C3%A9gorie:Article_utilisant_une_Infobox" title="Catégorie:Article utilisant une Infobox">Article utilisant une Infobox</a></li><li><a href="/wiki/Cat%C3%A9gorie:Article_contenant_un_appel_%C3%A0_traduction_en_anglais" title="Catégorie:Article contenant un appel à traduction en anglais">Article contenant un appel à traduction en anglais</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Informatique_th%C3%A9orique/Articles_li%C3%A9s" title="Catégorie:Portail:Informatique théorique/Articles liés">Portail:Informatique théorique/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Informatique/Articles_li%C3%A9s" title="Catégorie:Portail:Informatique/Articles liés">Portail:Informatique/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Projet:Math%C3%A9matiques/Articles" title="Catégorie:Projet:Mathématiques/Articles">Projet:Mathématiques/Articles</a></li><li><a href="/wiki/Cat%C3%A9gorie:Bon_article_en_anglais" title="Catégorie:Bon article en anglais">Bon article en anglais</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> La dernière modification de cette page a été faite le 31 octobre 2024 à 11:23.</li> <li id="footer-info-copyright"><span style="white-space: normal"><a href="/wiki/Wikip%C3%A9dia:Citation_et_r%C3%A9utilisation_du_contenu_de_Wikip%C3%A9dia" title="Wikipédia:Citation et réutilisation du contenu de Wikipédia">Droit d'auteur</a> : les textes sont disponibles sous <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr">licence Creative Commons attribution, partage dans les mêmes conditions</a> ; d’autres conditions peuvent s’appliquer. Voyez les <a class="external text" href="https://foundation.wikimedia.org/wiki/Policy:Terms_of_Use/fr">conditions d’utilisation</a> pour plus de détails, ainsi que les <a href="/wiki/Wikip%C3%A9dia:Cr%C3%A9dits_graphiques" title="Wikipédia:Crédits graphiques">crédits graphiques</a>. En cas de réutilisation des textes de cette page, voyez <a href="/wiki/Sp%C3%A9cial:Citer/Arbre_binaire_de_recherche" title="Spécial:Citer/Arbre binaire de recherche">comment citer les auteurs et mentionner la licence</a>.<br /> Wikipedia® est une marque déposée de la <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, organisation de bienfaisance régie par le paragraphe <a href="/wiki/501c" title="501c">501(c)(3)</a> du code fiscal des États-Unis.</span><br /></li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/fr">Politique de confidentialité</a></li> <li id="footer-places-about"><a href="/wiki/Wikip%C3%A9dia:%C3%80_propos_de_Wikip%C3%A9dia">À propos de Wikipédia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikip%C3%A9dia:Avertissements_g%C3%A9n%C3%A9raux">Avertissements</a></li> <li id="footer-places-contact"><a href="//fr.wikipedia.org/wiki/Wikipédia:Contact">Contact</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code de conduite</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Développeurs</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/fr.wikipedia.org">Statistiques</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Déclaration sur les témoins (cookies)</a></li> <li id="footer-places-mobileview"><a href="//fr.m.wikipedia.org/w/index.php?title=Arbre_binaire_de_recherche&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Version mobile</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" lang="en" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Rechercher</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Rechercher sur Wikipédia"> <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Spécial:Recherche"> </div> <button class="cdx-button cdx-search-input__end-button">Rechercher</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Sommaire" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Basculer la table des matières" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Basculer la table des matières</span> </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Arbre binaire de recherche</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>34 langues</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Ajouter un sujet</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-558fc7fc45-tmt9r","wgBackendResponseTime":150,"wgPageParseReport":{"limitreport":{"cputime":"0.215","walltime":"0.382","ppvisitednodes":{"value":1516,"limit":1000000},"postexpandincludesize":{"value":106395,"limit":2097152},"templateargumentsize":{"value":24129,"limit":2097152},"expansiondepth":{"value":13,"limit":100},"expensivefunctioncount":{"value":36,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":3678,"limit":5000000},"entityaccesscount":{"value":3,"limit":400},"timingprofile":["100.00% 264.624 1 -total"," 34.02% 90.024 1 Modèle:Infobox_Algorithme"," 28.28% 74.839 1 Modèle:Palette"," 24.41% 64.596 2 Modèle:Méta_palette_de_navigation"," 24.31% 64.322 1 Modèle:Palette_Arbres_informatiques"," 19.56% 51.769 12 Modèle:Liste_horizontale"," 17.59% 46.560 28 Modèle:Lien"," 13.58% 35.949 1 Modèle:Voir_homonymes"," 12.88% 34.078 1 Modèle:Méta_bandeau_de_note"," 12.32% 32.591 1 Modèle:Méta_bandeau"]},"scribunto":{"limitreport-timeusage":{"value":"0.099","limit":"10.000"},"limitreport-memusage":{"value":4823969,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-868759585b-4zmk6","timestamp":"20250214194543","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Arbre binaire de recherche","url":"https:\/\/fr.wikipedia.org\/wiki\/Arbre_binaire_de_recherche","sameAs":"http:\/\/www.wikidata.org\/entity\/Q623818","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q623818","author":{"@type":"Organization","name":"Contributeurs aux projets Wikimedia"},"publisher":{"@type":"Organization","name":"Fondation Wikimedia, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2005-07-19T16:51:25Z","dateModified":"2024-10-31T10:23:14Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/d\/da\/Binary_search_tree.svg"}</script> </body> </html>