CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-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-toc-available" lang="ca" dir="ltr"> <head> <meta charset="UTF-8"> <title>Arbre binari de cerca - Viquipèdia, l'enciclopèdia lliure</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-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-toc-available";var cookie=document.cookie.match(/(?:^|; )cawikimwclientpreferences=([^;]+)/);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":["","gener","febrer","març","abril","maig","juny","juliol","agost","setembre","octubre","novembre","desembre"],"wgRequestId":"9c13cc67-ec8a-4ed5-8c22-f267331f334c","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Arbre_binari_de_cerca","wgTitle":"Arbre binari de cerca","wgCurRevisionId":34123125,"wgRevisionId":34123125,"wgArticleId":620460,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Pàgines amb errors de marcatge de sintaxi","Articles amb la plantilla Webarchive amb enllaç wayback","Pàgines amb enllaç commonscat des de Wikidata","Estructura de dades"],"wgPageViewLanguage":"ca","wgPageContentLanguage":"ca","wgPageContentModel":"wikitext","wgRelevantPageName":"Arbre_binari_de_cerca","wgRelevantArticleId":620460,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[], "wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":true,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"ca","pageLanguageDir":"ltr","pageVariantFallbacks":"ca"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"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","wikibase.client.data-bridge.externalModifiers":"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.UkensKonkurranse","ext.gadget.refToolbar","ext.gadget.charinsert","ext.gadget.AltresViccionari","ext.gadget.purgetab","ext.gadget.DocTabs","ext.gadget.switcher","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","wikibase.client.data-bridge.init","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","oojs-ui.styles.icons-media","oojs-ui-core.icons","wikibase.sidebar.tracking"];</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=ca&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.data-bridge.externalModifiers%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=ca&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=ca&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <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 name="viewport" content="width=1120"> <meta property="og:title" content="Arbre binari de cerca - Viquipèdia, l'enciclopèdia lliure"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//ca.m.wikipedia.org/wiki/Arbre_binari_de_cerca"> <link rel="alternate" type="application/x-wiki" title="Modifica" href="/w/index.php?title=Arbre_binari_de_cerca&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="Viquipèdia (ca)"> <link rel="EditURI" type="application/rsd+xml" href="//ca.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://ca.wikipedia.org/wiki/Arbre_binari_de_cerca"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.ca"> <link rel="alternate" type="application/atom+xml" title="Canal de sindicació Atom Viquipèdia" href="/w/index.php?title=Especial:Canvis_recents&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_binari_de_cerca rootpage-Arbre_binari_de_cerca skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Vés al contingut</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="Lloc"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <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="Menú 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" > Menú principal </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">Menú principal</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">mou a la barra lateral</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">amaga</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navegació </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Portada" title="Visiteu la pàgina principal [z]" accesskey="z">Portada</a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Especial:Article_aleatori" title="Carrega una pàgina a l’atzar [x]" accesskey="x">Article a l'atzar</a></li><li id="n-Articles-de-qualitat" class="mw-list-item"><a href="/wiki/Viquip%C3%A8dia:Articles_de_qualitat">Articles de qualitat</a></li> </ul> </div> </div> <div id="p-Comunitat" class="vector-menu mw-portlet mw-portlet-Comunitat" > <div class="vector-menu-heading"> Comunitat </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-portal" class="mw-list-item"><a href="/wiki/Viquip%C3%A8dia:Portal" title="Sobre el projecte, què podeu fer, on trobareu les coses">Portal viquipedista</a></li><li id="n-Agenda-d'actes" class="mw-list-item"><a href="/wiki/Viquip%C3%A8dia:Trobades">Agenda d'actes</a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Especial:Canvis_recents" title="Una llista dels canvis recents al wiki [r]" accesskey="r">Canvis recents</a></li><li id="n-La-taverna" class="mw-list-item"><a href="/wiki/Viquip%C3%A8dia:La_taverna">La taverna</a></li><li id="n-contactpage" class="mw-list-item"><a href="/wiki/Viquip%C3%A8dia:Contacte">Contacte</a></li><li id="n-Xat" class="mw-list-item"><a href="/wiki/Viquip%C3%A8dia:Canals_IRC">Xat</a></li><li id="n-help" class="mw-list-item"><a href="/wiki/Viquip%C3%A8dia:Ajuda" title="El lloc per a saber més coses">Ajuda</a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Portada" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <img class="mw-logo-wordmark" alt="Viquipèdia" src="/static/images/mobile/copyright/wikipedia-wordmark-ca.svg" style="width: 7.5em; height: 1.4375em;"> <img class="mw-logo-tagline" alt="l'Enciclopèdia Lliure" src="/static/images/mobile/copyright/wikipedia-tagline-ca.svg" width="120" height="14" style="width: 7.5em; height: 0.875em;"> </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/Especial:Cerca" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Cerca a la Viquipèdia [f]" accesskey="f"> Cerca </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="Cerca a Viquipèdia" aria-label="Cerca a Viquipèdia" autocapitalize="sentences" title="Cerca a la Viquipèdia [f]" accesskey="f" id="searchInput" > </div> <input type="hidden" name="title" value="Especial:Cerca"> </div> <button class="cdx-button cdx-search-input__end-button">Cerca</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Eines personals"> <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="Aparença"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <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="Aparença" > <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" > Aparença </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="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_ca.wikipedia.org&uselang=ca" class="">Donatius</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=Especial:Crea_compte&returnto=Arbre+binari+de+cerca" title="Us animem a crear un compte i iniciar una sessió, encara que no és obligatori" class="">Crea un compte</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=Especial:Registre_i_entrada&returnto=Arbre+binari+de+cerca" title="Us animem a registrar-vos, però no és obligatori [o]" accesskey="o" class="">Inicia la sessió</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="Més opcions" > <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="Eines personals" > <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" > Eines personals </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="Menú d'usuari" > <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="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_ca.wikipedia.org&uselang=ca">Donatius</a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Especial:Crea_compte&returnto=Arbre+binari+de+cerca" title="Us animem a crear un compte i iniciar una sessió, encara que no és obligatori"> Crea un compte</a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Especial:Registre_i_entrada&returnto=Arbre+binari+de+cerca" title="Us animem a registrar-vos, però no és obligatori [o]" accesskey="o"> Inicia la sessió</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"> Pàgines per a editors no registrats <a href="/wiki/Ajuda:Introducci%C3%B3" aria-label="Vegeu més informació sobre l'edició">més informació</a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Especial:Contribucions_pr%C3%B2pies" title="Una llista de les modificacions fetes des d'aquesta adreça IP [y]" accesskey="y">Contribucions</a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Especial:Discussi%C3%B3_personal" title="Discussió sobre les edicions per aquesta adreça ip. [n]" accesskey="n">Discussió per aquest IP</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="Lloc"> <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="Contingut" 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">Contingut</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">mou a la barra lateral</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">amaga</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">Inici</div> </a> </li> <li id="toc-Descripció" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Descripció"> <div class="vector-toc-text"> 1 Descripció </div> </a> <ul id="toc-Descripció-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Operacions" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Operacions"> <div class="vector-toc-text"> 2 Operacions </div> </a> <button aria-controls="toc-Operacions-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> Commuta la subsecció Operacions </button> <ul id="toc-Operacions-sublist" class="vector-toc-list"> <li id="toc-Cerca" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Cerca"> <div class="vector-toc-text"> 2.1 Cerca </div> </a> <ul id="toc-Cerca-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Inserció" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Inserció"> <div class="vector-toc-text"> 2.2 Inserció </div> </a> <ul id="toc-Inserció-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Esborrat" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Esborrat"> <div class="vector-toc-text"> 2.3 Esborrat </div> </a> <ul id="toc-Esborrat-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Altres_Operacions" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Altres_Operacions"> <div class="vector-toc-text"> 2.4 Altres Operacions </div> </a> <ul id="toc-Altres_Operacions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Recorreguts" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Recorreguts"> <div class="vector-toc-text"> 2.5 Recorreguts </div> </a> <ul id="toc-Recorreguts-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Tipus_d'arbres_binaris_de_cerca" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Tipus_d'arbres_binaris_de_cerca"> <div class="vector-toc-text"> 3 Tipus d'arbres binaris de cerca </div> </a> <ul id="toc-Tipus_d'arbres_binaris_de_cerca-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Comparació_de_rendiment" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Comparació_de_rendiment"> <div class="vector-toc-text"> 4 Comparació de rendiment </div> </a> <button aria-controls="toc-Comparació_de_rendiment-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> Commuta la subsecció Comparació de rendiment </button> <ul id="toc-Comparació_de_rendiment-sublist" class="vector-toc-list"> <li id="toc-Arbre_binari_de_cerca_òptim" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Arbre_binari_de_cerca_òptim"> <div class="vector-toc-text"> 4.1 Arbre binari de cerca òptim </div> </a> <ul id="toc-Arbre_binari_de_cerca_òptim-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Vegeu_també" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Vegeu_també"> <div class="vector-toc-text"> 5 Vegeu també </div> </a> <ul id="toc-Vegeu_també-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Referències" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Referències"> <div class="vector-toc-text"> 6 Referències </div> </a> <ul id="toc-Referències-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bibliografia" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Bibliografia"> <div class="vector-toc-text"> 7 Bibliografia </div> </a> <ul id="toc-Bibliografia-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Enllaços_externs" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Enllaços_externs"> <div class="vector-toc-text"> 8 Enllaços externs </div> </a> <ul id="toc-Enllaços_externs-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="Contingut" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <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="Commuta la taula de continguts." > <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" > Commuta la taula de continguts. </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">Arbre binari de cerca</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="Vés a un article en una altra llengua. Disponible en 34 llengües" > <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" > 34 llengües </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="شجرة بحث ثنائية - àrab" lang="ar" hreflang="ar" data-title="شجرة بحث ثنائية" data-language-autonym="العربية" data-language-local-name="àrab" class="interlanguage-link-target">العربية</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="Двоично дърво за търсене - búlgar" lang="bg" hreflang="bg" data-title="Двоично дърво за търсене" data-language-autonym="Български" data-language-local-name="búlgar" class="interlanguage-link-target">Български</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 - bosnià" lang="bs" hreflang="bs" data-title="Binarno stablo pretraživanja" data-language-autonym="Bosanski" data-language-local-name="bosnià" class="interlanguage-link-target">Bosanski</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 - txec" lang="cs" hreflang="cs" data-title="Binární vyhledávací strom" data-language-autonym="Čeština" data-language-local-name="txec" class="interlanguage-link-target">Čeština</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æ - danès" lang="da" hreflang="da" data-title="Binært søgetræ" data-language-autonym="Dansk" data-language-local-name="danès" class="interlanguage-link-target">Dansk</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 - alemany" lang="de" hreflang="de" data-title="Binärer Suchbaum" data-language-autonym="Deutsch" data-language-local-name="alemany" class="interlanguage-link-target">Deutsch</a></li><li class="interlanguage-link interwiki-en badge-Q17437798 badge-goodarticle mw-list-item" title="article bo"><a href="https://en.wikipedia.org/wiki/Binary_search_tree" title="Binary search tree - anglès" lang="en" hreflang="en" data-title="Binary search tree" data-language-autonym="English" data-language-local-name="anglès" class="interlanguage-link-target">English</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 - espanyol" lang="es" hreflang="es" data-title="Árbol binario de búsqueda" data-language-autonym="Español" data-language-local-name="espanyol" class="interlanguage-link-target">Español</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="درخت جستجوی دودویی - persa" lang="fa" hreflang="fa" data-title="درخت جستجوی دودویی" data-language-autonym="فارسی" data-language-local-name="persa" class="interlanguage-link-target">فارسی</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 - finès" lang="fi" hreflang="fi" data-title="Binäärinen hakupuu" data-language-autonym="Suomi" data-language-local-name="finès" class="interlanguage-link-target">Suomi</a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Arbre_binaire_de_recherche" title="Arbre binaire de recherche - francès" lang="fr" hreflang="fr" data-title="Arbre binaire de recherche" data-language-autonym="Français" data-language-local-name="francès" class="interlanguage-link-target">Français</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="עץ חיפוש - hebreu" lang="he" hreflang="he" data-title="עץ חיפוש" data-language-autonym="עברית" data-language-local-name="hebreu" class="interlanguage-link-target">עברית</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="Բինար որոնման ծառ - armeni" lang="hy" hreflang="hy" data-title="Բինար որոնման ծառ" data-language-autonym="Հայերեն" data-language-local-name="armeni" class="interlanguage-link-target">Հայերեն</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 - indonesi" lang="id" hreflang="id" data-title="Pohon Pencarian Biner" data-language-autonym="Bahasa Indonesia" data-language-local-name="indonesi" class="interlanguage-link-target">Bahasa Indonesia</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 - italià" lang="it" hreflang="it" data-title="Albero binario di ricerca" data-language-autonym="Italiano" data-language-local-name="italià" class="interlanguage-link-target">Italiano</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="二分探索木 - japonès" lang="ja" hreflang="ja" data-title="二分探索木" data-language-autonym="日本語" data-language-local-name="japonès" class="interlanguage-link-target">日本語</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">ಕನ್ನಡ</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="이진 탐색 트리 - coreà" lang="ko" hreflang="ko" data-title="이진 탐색 트리" data-language-autonym="한국어" data-language-local-name="coreà" class="interlanguage-link-target">한국어</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 - llombard" lang="lmo" hreflang="lmo" data-title="Alber binari de ricerca" data-language-autonym="Lombard" data-language-local-name="llombard" class="interlanguage-link-target">Lombard</a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Binaire_zoekboom" title="Binaire zoekboom - neerlandès" lang="nl" hreflang="nl" data-title="Binaire zoekboom" data-language-autonym="Nederlands" data-language-local-name="neerlandès" class="interlanguage-link-target">Nederlands</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ń - polonès" lang="pl" hreflang="pl" data-title="Binarne drzewo poszukiwań" data-language-autonym="Polski" data-language-local-name="polonès" class="interlanguage-link-target">Polski</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 - portuguès" lang="pt" hreflang="pt" data-title="Árvore binária de busca" data-language-autonym="Português" data-language-local-name="portuguès" class="interlanguage-link-target">Português</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 - romanès" lang="ro" hreflang="ro" data-title="Arbore binar de căutare" data-language-autonym="Română" data-language-local-name="romanès" class="interlanguage-link-target">Română</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="Двоичное дерево поиска - rus" lang="ru" hreflang="ru" data-title="Двоичное дерево поиска" data-language-autonym="Русский" data-language-local-name="rus" class="interlanguage-link-target">Русский</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 - serbocroat" lang="sh" hreflang="sh" data-title="Binarno stablo pretrage" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="serbocroat" class="interlanguage-link-target">Srpskohrvatski / српскохрватски</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 - eslovac" lang="sk" hreflang="sk" data-title="Binárny vyhľadávací strom" data-language-autonym="Slovenčina" data-language-local-name="eslovac" class="interlanguage-link-target">Slovenčina</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 - serbi" lang="sr" hreflang="sr" data-title="Binarno stablo pretrage" data-language-autonym="Српски / srpski" data-language-local-name="serbi" class="interlanguage-link-target">Српски / srpski</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 - suec" lang="sv" hreflang="sv" data-title="Binärt sökträd" data-language-autonym="Svenska" data-language-local-name="suec" class="interlanguage-link-target">Svenska</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="ต้นไม้ค้นหาแบบทวิภาค - tai" lang="th" hreflang="th" data-title="ต้นไม้ค้นหาแบบทวิภาค" data-language-autonym="ไทย" data-language-local-name="tai" class="interlanguage-link-target">ไทย</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">Türkçe</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="Двійкове дерево пошуку - ucraïnès" lang="uk" hreflang="uk" data-title="Двійкове дерево пошуку" data-language-autonym="Українська" data-language-local-name="ucraïnès" class="interlanguage-link-target">Українська</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 - vietnamita" 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="vietnamita" class="interlanguage-link-target">Tiếng Việt</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="二元搜尋樹 - xinès" lang="zh" hreflang="zh" data-title="二元搜尋樹" data-language-autonym="中文" data-language-local-name="xinès" class="interlanguage-link-target">中文</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="二元搜尋樹 - cantonès" lang="yue" hreflang="yue" data-title="二元搜尋樹" data-language-autonym="粵語" data-language-local-name="cantonès" class="interlanguage-link-target">粵語</a></li> </ul> <div class="after-portlet after-portlet-lang"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q623818#sitelinks-wikipedia" title="Modifica enllaços interlingües" class="wbc-editpage">Modifica els enllaços</a></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Espais 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_binari_de_cerca" title="Vegeu el contingut de la pàgina [c]" accesskey="c">Pàgina</a></li><li id="ca-talk" class="new vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Discussi%C3%B3:Arbre_binari_de_cerca&action=edit&redlink=1" rel="discussion" class="new" title="Discussió sobre el contingut d'aquesta pàgina (encara no existeix) [t]" accesskey="t">Discussió</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="Canvia la variant de llengua" > <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" >català </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="Vistes"> <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_binari_de_cerca">Mostra</a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit" title="Modifica el codi font d'aquesta pàgina [e]" accesskey="e">Modifica</a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Arbre_binari_de_cerca&action=history" title="Versions antigues d'aquesta pàgina [h]" accesskey="h">Mostra l'historial</a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Eines de la pàgina"> <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="Eines" > <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" >Eines </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">Eines</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">mou a la barra lateral</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">amaga</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="Més opcions" > <div class="vector-menu-heading"> Accions </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_binari_de_cerca">Mostra</a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit" title="Modifica el codi font d'aquesta pàgina [e]" accesskey="e">Modifica</a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Arbre_binari_de_cerca&action=history">Mostra l'historial</a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Especial:Enlla%C3%A7os/Arbre_binari_de_cerca" title="Una llista de totes les pàgines wiki que enllacen amb aquesta [j]" accesskey="j">Què hi enllaça</a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Especial:Seguiment/Arbre_binari_de_cerca" rel="nofollow" title="Canvis recents a pàgines enllaçades des d'aquesta pàgina [k]" accesskey="k">Canvis relacionats</a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Especial:P%C3%A0gines_especials" title="Llista totes les pàgines especials [q]" accesskey="q">Pàgines especials</a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Arbre_binari_de_cerca&oldid=34123125" title="Enllaç permanent a aquesta revisió de la pàgina">Enllaç permanent</a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Arbre_binari_de_cerca&action=info" title="Més informació sobre aquesta pàgina">Informació de la pàgina</a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Especial:Citau&page=Arbre_binari_de_cerca&id=34123125&wpFormIdentifier=titleform" title="Informació sobre com citar aquesta pàgina">Citau aquest article</a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Especial:UrlShortener&url=https%3A%2F%2Fca.wikipedia.org%2Fwiki%2FArbre_binari_de_cerca">Obtén una URL abreujada</a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Especial:QrCode&url=https%3A%2F%2Fca.wikipedia.org%2Fwiki%2FArbre_binari_de_cerca">Descarrega el codi QR</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"> Imprimeix/exporta </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=Especial:Llibre&bookcmd=book_creator&referer=Arbre+binari+de+cerca">Crea un llibre</a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Especial:DownloadAsPdf&page=Arbre_binari_de_cerca&action=show-download-screen">Baixa com a PDF</a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Arbre_binari_de_cerca&printable=yes" title="Versió per a impressió d'aquesta pàgina [p]" accesskey="p">Versió per a impressora</a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> En altres projectes </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">Commons</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="Enllaç a l'element del repositori de dades connectat [g]" accesskey="g">Element a Wikidata</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="Eines de la pàgina"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Aparença"> <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">Aparença</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">mou a la barra lateral</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">amaga</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">De la Viquipèdia, l'enciclopèdia lliure</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="ca" dir="ltr">En <a href="/wiki/Ci%C3%A8ncies_de_la_computaci%C3%B3" title="Ciències de la computació">ciències de la computació</a>, un arbre binari de cerca (BST, de l'anglès Binary Search Tree) és un tipus particular d'<a href="/wiki/Arbre_binari" title="Arbre binari">arbre binari</a> que presenta una <a href="/wiki/Estructura_de_dades" title="Estructura de dades">estructura de dades</a> en forma d'<a href="/wiki/Arbre_(estructura_de_dades)" title="Arbre (estructura de dades)">arbre</a>. <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Descripció">Descripció</h2>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=1" title="Modifica la secció: Descripció">modifica</a>]</div> Un arbre binari de cerca és un <a href="/wiki/Arbre_binari" title="Arbre binari">arbre binari</a> definit de la següent manera: <table style="margin-right:4em; margin-right:6em; min-width:50%; max-width:77%;"> <tbody><tr> <td><blockquote style="padding-right:2em; padding-left:1.5em; padding-bottom:0.5em; padding-top:0.5em; border:1px solid; font-family:Georgia,serif; border-color: #400000; background-color: #FFFFFF;"> Tot arbre buit és un arbre binari de cerca. Un arbre binari no buit, d'arrel R, és un arbre binari de cerca si: <ul><li>En cas de tenir subarbre esquerre, l'arrel R ha de ser major que el valor màxim emmagatzemat al subarbre esquerre, i que el subarbre esquerre sigui un arbre binari de cerca.</li> <li>En cas de tenir subarbre dret, l'arrel R ha de ser menor que el valor mínim emmagatzemat al subarbre dret, i que el subarbre dret sigui un arbre binari de cerca.</li></ul> </blockquote> </td></tr></tbody></table> Dit de manera resumida, és un arbre binari en què el subarbre esquerre de qualsevol <a href="/wiki/Node_(inform%C3%A0tica)" title="Node (informàtica)">node</a> (si no buit) conté valors menors que el que conté aquest node, i el subarbre dret (si no buit) conté valors més grans. Per tant, segons aquesta definició, hi ha una relació d'ordre establerta entre els elements dels nodes. Que certa relació estigui definida, o no, depèn de cada <a href="/wiki/Llenguatge_de_programaci%C3%B3" title="Llenguatge de programació">llenguatge de programació</a>. D'aquí es dedueix que hi pot haver diferents arbres binaris de cerca per a un mateix conjunt d'elements. L'alçada total de l'arbre (h) al pitjor dels casos tindrà la mateixa mida que el nombre d'elements disponibles. I en el millor dels casos ve donada per l'expressió <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h=\lceil \log _{2}(c+1)\rceil }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>h</mi> <mo>=</mo> <mo fence="false" stretchy="false">⌈</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>c</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo fence="false" stretchy="false">⌉</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h=\lceil \log _{2}(c+1)\rceil }</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1855b97382be58f3bbbe4c8207a2696b608b2ebe" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.347ex; height:2.843ex;" alt="{\displaystyle h=\lceil \log _{2}(c+1)\rceil }">, on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lceil \cdot \rceil }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⌈</mo> <mo>⋅</mo> <mo fence="false" stretchy="false">⌉</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lceil \cdot \rceil }</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f466ab9bff81efaf8aea33003f264a7d7edb5535" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.712ex; height:2.843ex;" alt="{\displaystyle \lceil \cdot \rceil }"> indica <a href="/wiki/Arrodoniment" title="Arrodoniment">arrodoniment</a> a l'alça. <a href="/wiki/Fitxer:ABB1.svg" class="mw-file-description" title="Arbre binari de cerca"><img alt="Arbre binari de cerca" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/7f/ABB1.svg/240px-ABB1.svg.png" decoding="async" width="240" height="146" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/7f/ABB1.svg/360px-ABB1.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/7f/ABB1.svg/480px-ABB1.svg.png 2x" data-file-width="240" data-file-height="146" /></a> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Fitxer:ABBabc.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/3/30/ABBabc.svg/220px-ABBabc.svg.png" decoding="async" width="220" height="162" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/30/ABBabc.svg/330px-ABBabc.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/30/ABBabc.svg/440px-ABBabc.svg.png 2x" data-file-width="201" data-file-height="148" /></a><figcaption>Exemple d' Arbre Binari de Cerca </figcaption></figure> L'interès dels arbres binaris de cerca és que el seu <a href="/wiki/Arbre_binari" title="Arbre binari">recorregut en inorder</a> proporciona els elements ordenats de forma ascendent i que la recerca d'algun element sol ser molt eficient. Depenent de les necessitats de l'usuari que tracti amb una estructura d'aquest tipus es podrà permetre la igualtat estricta en algun, en cap o en ambdós subarbres que pengen de l'arrel. Permetre l'ús de la igualtat provoca l'aparició de valors dobles i fa la recerca més complexa. Un arbre binari de cerca no deixa de ser un cas particular d'arbre binari. Amb la següent especificació d'arbre binari en <a href="/w/index.php?title=Maude&action=edit&redlink=1" class="new" title="Maude (encara no existeix)">Maude</a>: <div class="mw-highlight mw-content-ltr" dir="ltr"><pre>fmod TREE-BINARY {X :: TRIV} is sorts TreeBinNV{X} TreeBin{X} . subsort TreeBinNV{X} < TreeBin{X} . *** generadors op create : -> TreeBin{X}[ctor] . op treeBin : X$Elt TreeBin{X} TreeBin{X} -> TreeBinNV{X}[ctor] . endfm</pre></div> podem fer la següent definició per a un arbre binari de cerca (també en Maude): <div class="mw-highlight mw-content-ltr" dir="ltr"><pre>fmod TREE-BINARY-SEARCH {X :: ORDER} is protecting TREE-BINARY{VOrder}{X} . sorts BST{X} BSTNV{X} . subsort BSTNV{X} < BST{X} . subsort BST{X} < TreeBin{VOrder}{X} . subsort BSTNV{X} < TreeBinNV{VOrder}{X} . *** generadors op create : -> TreeBin{X}[ctor] . op treeBin : X$Elt TreeBin{X} TreeBin{X} -> TreeBinNV{X}[ctor] . endfm</pre></div> amb la següent <a href="/wiki/Teoria" title="Teoria">teoria</a> d'<a href="/wiki/Ordre" title="Ordre">ordre</a>: <div class="mw-highlight mw-content-ltr" dir="ltr"><pre>fth ORDER is Protecting BOOL . sort ELT . *** operacions op _ <_: ELT ELT → Bool . endfth</pre></div> Perquè un arbre binari pertanyi al tipus arbre binari de cerca ha de complir la condició d'ordenació següent que aniria al costat del mòdul TREE-BINARY-SEARCH: <div class="mw-highlight mw-content-ltr" dir="ltr"><pre>var R : X$Elt . vars INV DNV : BSTNV{X} . vars I D : BST{X} . mb create : BST{X} . mb treeBin(R, create, create) : BSTNV{X} . cmb treeBin(R, INV, create) : BSTNV{X} if R > max(INV) . cmb treeBin(R, create, DNV) : BSTNV{X} if R < min(DNV) . cmb treeBin(R, INV, DNV) : BSTNV{X} if (R > max(INV)) and (R < min(DNV)) . ops min max : BSTNV{X} -> X$Elt . eq min(treeBin(R, create, D)) = R . eq min(treeBin(R, INV, D)) = min(INV) . eq max(treeBin(R, I, create)) = R . eq max(treeBin(R, I, DNV)) = max(DNV) .</pre></div> Implementació en <a href="/wiki/Python_(llenguatge_de_programaci%C3%B3)" class="mw-redirect" title="Python (llenguatge de programació)">Python</a>: <div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre>class node: left, right, data = None, None, 0 def __init__(self, data): # Crea un node self.left = None self.right = None self.data = data class binaryTree: def __init__(self): # Inicia l'arrel self.root = None def insertNode(self, data): # Crea un nou node i el retorna return node(data) def insert(self, root, data): # Inserta un valor nou a l'arbre if root == None: # Si no hi ha nodes a l'arbre, l'agrega return self.insertNode(data) else: # Si hi ha nodes a l'arbre, el recorre if data <= root.data: # Si el valor és menor que el guardat, va al subarbre esquerre root.left = self.insert(root.left, data) else: # Si no, va al subarbre dret root.right = self.insert(root.right, data) return root </pre></div> <div class="mw-heading mw-heading2"><h2 id="Operacions">Operacions</h2>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=2" title="Modifica la secció: Operacions">modifica</a>]</div> Totes les operacions realitzades sobre arbres binaris de cerca estan basades en la comparació dels elements o clau dels mateixos, per la qual cosa cal una <a href="/wiki/Subrutina" title="Subrutina">subrutina</a>, que pot estar predefinida en el <a href="/wiki/Llenguatge_de_programaci%C3%B3" title="Llenguatge de programació">llenguatge de programació</a>, que els compari i pugui establir una relació d'ordre entre ells, és a dir, que donats dos elements sigui capaç de reconèixer quina és major i quina menor. Es parla de clau d'un element perquè en la majoria dels casos el contingut dels nodes serà un altre tipus d'estructura i cal que la comparació es faci sobre algun camp al que s'anomena clau. <div class="mw-heading mw-heading3"><h3 id="Cerca">Cerca</h3>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=3" title="Modifica la secció: Cerca">modifica</a>]</div> La cerca a l'arbre consisteix en accedir a l'arrel; si l'element a localitzar coincideix amb aquest llavors la cerca es dona per conclosa, si l'element és menor es busca en el subarbre esquerre i si és major en el dret. Si s'arriba a un node fulla i l'element no ha estat trobat, se suposa que no existeix en l'arbre. Cal destacar que la cerca en aquest tipus d'arbres és molt eficient, representa una <a href="/wiki/Logaritme" title="Logaritme">funció logarítmica</a>. El màxim nombre de comparacions que necessitaríem per saber si un element es troba en un arbre binari de cerca estaria entre log₂(n+1) i n, essent n el nombre de nodes. La recerca d'un element en un arbre binari de cerca es pot realitzar de dues formes; <a href="/wiki/Iteraci%C3%B3" title="Iteració">iterativa</a> o <a href="/wiki/Recursivitat" title="Recursivitat">recursiva</a>. Exemple de versió iterativa al <a href="/wiki/Llenguatge_de_programaci%C3%B3_C" class="mw-redirect" title="Llenguatge de programació C">llenguatge de programació C</a>, suposant que estem buscant una clau allotjada en un node on hi ha el corresponent "dada" que necessitem trobar: <div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>data search_BST(abb t, key k) { abb p; data e; e=NULL; p=t; if (!isNull(p)) { while (!isNull(p) && (p->k!=k)) { if (k < p->k) p = p->l; if (p->k < k) p = p->r; } if (!isNull(p) &&(p->d!=NULL)) { e = copyData(p->d); } } return e; } </pre></div> Vegeu ara la versió recursiva en aquest mateix llenguatge: <div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>int search(tTree *a, int elem) { if (a == NULL) { return 0; } else if (a->key < elem) { return search(a->hRight, elem); } else if (a->key > elem) { return search(a->hLeft, elem); } else { return 1; } } </pre></div> Un altre exemple, en <a href="/wiki/Python" title="Python">Python</a>: <div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre>def search_binary_tree(node, key): if node is None: return None # No s'ha trobat if key < node.key: return search_binary_tree(node.left, key) else if key > node.key: return search_binary_tree(node.right, key) else: return node.value </pre></div> En <a href="/wiki/Llenguatge_de_programaci%C3%B3_Pascal" class="mw-redirect" title="Llenguatge de programació Pascal">Pascal</a>: <div class="mw-highlight mw-highlight-lang-pascal mw-content-ltr" dir="ltr"><pre>Function search(T: ABR, y: integer): ABR begin if (T=nil) or (^T.root=y) then search:=T; else if (^T.root<y) then search:=search(^T.right,y); else search:=search(^T.left,y); end; </pre></div> Una especificació en Maude per a l'operació de cerca quedaria de la següent manera: <div class="mw-highlight mw-content-ltr" dir="ltr"><pre>op this? : X$Elt ABB{X} -> Bool . var R R1 R2 : X$Elt . vars I D : ABB{X} . eq this?(R, create) = false . eq this?(R1, treeBin(R2, I, D)) = if R1 == R2 then true else if R1 < R2 then this?(R1, I) else this?(R1, D) end end .</pre></div> <div class="mw-heading mw-heading3"><h3 id="Inserció">Inserció</h3>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=4" title="Modifica la secció: Inserció">modifica</a>]</div> La inserció és similar a la cerca, es pot donar una solució tant iterativa com recursiva. Si tenim inicialment com a <a href="/w/index.php?title=Argument_(Ci%C3%A8ncies_de_la_computaci%C3%B3)&action=edit&redlink=1" class="new" title="Argument (Ciències de la computació) (encara no existeix)">paràmetre</a> un arbre buit, es crea un nou node com a únic contingut l'element a inserir. Si no ho està, es comprova si l'element donat és menor que l'arrel de l'arbre inicial amb el que s'insereix en el subarbre esquerre, i si és major s'insereix en el subarbre dret. D'aquesta manera, les insercions es fan a les fulles. <figure class="mw-halign-center" typeof="mw:File/Thumb"><a href="/wiki/Fitxer:Insertar.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c0/Insertar.svg/800px-Insertar.svg.png" decoding="async" width="800" height="221" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c0/Insertar.svg/1200px-Insertar.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c0/Insertar.svg/1600px-Insertar.svg.png 2x" data-file-width="1655" data-file-height="458" /></a><figcaption>Evolució de la inserció de l'element "5" en un arbre binari de cerca</figcaption></figure> Com en el cas de la cerca pot haver diverses variants a l'hora d'implementar la inserció en el ADT (de l'anglès, Abstract Data Type), i és la decisió a prendre quan l'element (o clau de l'element) a inserir ja es troba en l'arbre; pot ser que aquest sigui modificat o que sigui ignorada la inserció. Aquesta operació modifica l'arbre, perdent la versió anterior d'aquest. A continuació hi ha les dues versions de l'algorisme amb <a href="/wiki/Pseudocodi" title="Pseudocodi">pseudocodi</a>, iterativa i recursiva, respectivament. <pre>PROC InsertarSBT (arbre: Tabba; dada: TElement) VARIABLES nou_node, PAV, pret: Tabba nova_clau: Tclau elements: TElement INICI nou_node <- NOU (TNodeSBT) nou_node^. esquerra <- NUL nou_node^. dreta <- NUL nou_node^. elem <- dada SI SBTBuit(arbre) LLAVORS arbre <- nou_node EN_CAS_CONTRARI nova_clau <- dada.clau PAV <- arbre // Punter Avançat pret <- NUL // Punter retardat MENTRE (PAV <- NUL) FER pret <- PAV elements = PAV^. elem SI (nova_clau < ele.clau) LLAVORS PAV <- PAV^. esquerra EN_CAS_CONTRARI PAV <- PAV^. dreta FI_SI FI_MENTRE elements = pret^. elem SI (nova_clau < ele.clau) LLAVORS pret^. esquerra <- nou_node EN_CAS_CONTRARI pret^. dreta <- nou_node FI_SI FI_SI FI </pre> <pre>PROC InsertarSBT (arbre: Tabba; dada: TElement) VARIABLES elements: TElement INICI SI (SBTBuit(arbre)) LLAVORS arbre <- NOU (TNodeSBT) arbre^. esquerra <- NUL arbre^. dreta <- NUL arbre^. elem <- dada EN_CAS_CONTRARI elements = InfoSBT (arbre) SI (dada.clau < ele.clau) LLAVORS InsertarSBT (arbre^. esquerra, dada) EN_CAS_CONTRARI InsertarSBT (arbre^. dreta, dada) FI_SI FI_SI FI </pre> Es pot apreciar la simplicitat que ofereix la versió recursiva; aquest algorisme és la traducció en <a href="/wiki/Llenguatge_de_programaci%C3%B3_C" class="mw-redirect" title="Llenguatge de programació C">C</a>. L'arbre és passat per <a href="/w/index.php?title=Argument_(Ci%C3%A8ncies_de_la_computaci%C3%B3)&action=edit&redlink=1" class="new" title="Argument (Ciències de la computació) (encara no existeix)">referència</a> perquè els nous enllaços als subarbre mantinguin la coherència. <div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>void insert(tTree **a, int elem) { if (*a == NULL) { *a = (tTree *) malloc(sizeof(tTree)); (*a)->key = elem; (*a)->hLeft = NULL; (*a)->hRight = NULL; } else if ((*a)->key < elem) { insert(&(*a)->hRight, elem); } else if ((*a)->key > elem) { insertar(&(*a)->hLeft, elem); } } </pre></div> Exemple en <a href="/wiki/Python" title="Python">Python</a>: <div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre>def binary_tree_insert(node, key, value): if node is None: return TreeNode(None, key, value, None) if key == node.key: return TreeNode(node.left, key, value, node.right) if key <node.key: return TreeNode(binary_tree_insert(node.left, key, value), node.key, node.value, node.right) else: return TreeNode(node.left, node.key, node.value, binary_tree_insert(node.right, key, value)) </pre></div> Un altre exemple en <a href="/wiki/Llenguatge_de_programaci%C3%B3_Pascal" class="mw-redirect" title="Llenguatge de programació Pascal">Pascal</a>: <div class="mw-highlight mw-highlight-lang-pascal mw-content-ltr" dir="ltr"><pre>Procedure Insertion(var T:ABR, y:integer) var last_node:ABR; current_node:ABR; new_node:ABR; begin last_node:=nil; current_node:=T; while (current_node<>nil) do begin last_node:=current_node; if (current_node^.root<y) then current_node:=current_node^.right else current_node:=current_node^.left; end; new(new_node); ^new_node.root:=y; ^new_node.left:=nil; ^new_node.right:=nil; if last_node=nil then T:=new_node else if last_node^.root<y then last_node^.right:=new_node else last_node^.left:=new_node; end; </pre></div> Vegeu també un exemple d'algorisme recursiu d'inserció en un BST en el llenguatge de programació <a href="/w/index.php?title=Maude&action=edit&redlink=1" class="new" title="Maude (encara no existeix)">Maude</a>: <div class="mw-highlight mw-content-ltr" dir="ltr"><pre>op insert : X$Elt BST{X} -> BSTNV{X} . var R R1 R2 : X$Elt . vars I D : BST{X} . eq insert(R, create) = treeBin(R, create, create) . eq insert(R1, treeBin(B2, I, D)) = if R1 < R2 then treeBin(R2, insert(R1, I), D) else treeBin(R2, I, insert(R1, D)) end .</pre></div> L'operació d'inserció requereix, en el pitjor dels casos, un temps proporcional a l'altura de l'arbre. <div class="mw-heading mw-heading3"><h3 id="Esborrat">Esborrat</h3>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=5" title="Modifica la secció: Esborrat">modifica</a>]</div> L'operació d'esborrat no és tan senzilla com les de recerca i inserció. Hi ha diversos casos a tenir en consideració:<a href="#cite_note-1">[1]</a> <ul><li> Esborrar un node sense fills o node fulla : simplement s'esborra i s'estableix a nul l'apuntador del seu predecessor.</li></ul> <figure class="mw-halign-center" typeof="mw:File/Frame"><a href="/wiki/Fitxer:ABBHOJA3.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/d/d7/ABBHOJA3.svg/615px-ABBHOJA3.svg.png" decoding="async" width="615" height="152" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/d7/ABBHOJA3.svg/923px-ABBHOJA3.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/d7/ABBHOJA3.svg/1230px-ABBHOJA3.svg.png 2x" data-file-width="615" data-file-height="152" /></a><figcaption>Node d'esborrar 74</figcaption></figure> <ul><li> Esborrar un node amb un subarbre fill : s'esborra el node i s'assigna el seu subarbre fill com subarbre del seu predecessor.</li></ul> <figure class="mw-halign-center" typeof="mw:File/Frame"><a href="/wiki/Fitxer:ABBHOJA5.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/2/20/ABBHOJA5.svg/615px-ABBHOJA5.svg.png" decoding="async" width="615" height="152" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/2/20/ABBHOJA5.svg/923px-ABBHOJA5.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/2/20/ABBHOJA5.svg/1230px-ABBHOJA5.svg.png 2x" data-file-width="615" data-file-height="152" /></a><figcaption>Node d'esborrar 70</figcaption></figure> <ul><li> Esborrar un node amb dos subarbres fill : la solució està en reemplaçar el valor del node pel del seu predecessor o pel del seu successor en inorder i posteriorment esborrar aquest node. El seu predecessor en inorder serà el node més a la dreta del seu subarbre esquerre (major node del subarbre esquerre), i el seu successor el node més a l'esquerra del seu subarbre dret (menor node del subarbre dret). En la següent figura es mostra com existeix la possibilitat de realitzar qualsevol dels dos reemplaçaments:</li></ul> <figure class="mw-halign-center" typeof="mw:File/Frame"><a href="/wiki/Fitxer:ABBHOJA4.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/1/18/ABBHOJA4.svg/615px-ABBHOJA4.svg.png" decoding="async" width="615" height="152" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/18/ABBHOJA4.svg/923px-ABBHOJA4.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/18/ABBHOJA4.svg/1230px-ABBHOJA4.svg.png 2x" data-file-width="615" data-file-height="152" /></a><figcaption>Node d'esborrar 59</figcaption></figure> El següent algorisme en <a href="/wiki/Llenguatge_de_programaci%C3%B3_C" class="mw-redirect" title="Llenguatge de programació C">C</a> realitza l'esborrament en un BST. El procediment replace busca la major clau del subarbre esquerre i l'assigna al node a eliminar. <div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>void replace(tTree **a, tTree **aux); /*Prototip de la funció replace */ void remove(tTree **a, int elem) { tTree *aux; if (*a == NULL) return; if ((*a)->key < elem) remove(&(*a)->hRight, elem); else if ((*a)->key > elem) remove(&(*a)->hLeft, elem); else if ((*a)->key == elem) { aux = *a; if ((*a)->hLeft== NULL) *a = (*a)->hRight; else if ((*a)->hRight== NULL) *a = (*a)->hLeft; else replace(&(*a)->hLeft, &aux); free(aux); } } void replace(tTree **a, tTree **aux) { if ((*a)->hRight == NULL) { (*aux)->key = (*a)->key; *aux = *a; *a = (*a)->hLeft; } else replace(&(*a)->hRight, aux); } </pre></div> Un altre exemple en <a href="/wiki/Llenguatge_de_programaci%C3%B3_Pascal" class="mw-redirect" title="Llenguatge de programació Pascal">Pascal</a>. <div class="mw-highlight mw-highlight-lang-pascal mw-content-ltr" dir="ltr"><pre>Procedure Remove(var T:ABR, x:ABR) var aRemove:ABR; previous:ABR; current:ABR; descendent:ABR; begin if (^x.left=nil) or (^x.right=nil) then aRemove:=x; else aRemove:=successor(T,x); current:=T; previous:=nil; while (current<>aRemove) do begin previous:=current; if (^current.root<^aRemove.root) then current:=^current.right; else current:=^current.left; end; if (^current.left=nil) then descendent:=^current.right; else descendent:=^current.left; if (previous=nil) then T:=descendent; else if (^previous.root<^current.root) then ^previous.right:=descendent; else ^previous.left:=descendent; if (aRemove<>x) then ^x.root:=^aRemove.root; free(aRemove); end; </pre></div> Vegeu també un exemple d'algorisme recursiu de supressió en un BST en el llenguatge de programació Maude, considerant els generadors create i treeBin. Aquesta especificació fa ús de la component clau a partir de la qual s'ordena l'arbre. <div class="mw-highlight mw-content-ltr" dir="ltr"><pre>op delete : X$Elt BST{X} -> BST{X} . vars R M : X$Elt . vars I D : ABB{X} . vars INV DNV : ABBNV{X} . ops max min : TreeBin{X} -> X$Elt . eq min(treeBin(R, create, D)) = R . eq max(treeBin(R, I, create)) = R . eq min(treeBin(R, INV, D)) = min(INV) . eq max(treeBin(R, I, DNV)) = max(DNV) . eq delete(M, create) = create . ceq delete(M, treeBin(R, create, D)) = D if M == key(R) . ceq delete(M, treeBin(R, I, create)) = I if M == key(R) . ceq delete(M, treeBin(R, INV, DNV)) = treeBin(max(INV), delete(key(max(INV)), INV), DNV) if M == key(R) . ceq delete(M, treeBin(R, I, D)) = treeBin(R, delete(M, I), D) if M < key(R) . ceq delete(M, treeBin(R, I, D)) = treeBin(R, I, delete(M, D)) if key(R) < M .</pre></div> <div class="mw-heading mw-heading3"><h3 id="Altres_Operacions">Altres Operacions</h3>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=6" title="Modifica la secció: Altres Operacions">modifica</a>]</div> Una altra opereció seria per exemple comprovar que un arbre binari és un arbre binari de cerca. La seva implementació en Maude és la següent: <div class="mw-highlight mw-content-ltr" dir="ltr"><pre>op isBST? : BST{X} -> Bool . var R : X$Elt . vars I D : BST{X} . eq isBST?(create) = true . eq isBST?(treeBin(R, I, D)) = (Max(I) < R) and (Min(D) > R) and (isBST?(I)) and (isBST?(D)) .</pre></div> <div class="mw-heading mw-heading3"><h3 id="Recorreguts">Recorreguts</h3>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=7" title="Modifica la secció: Recorreguts">modifica</a>]</div> Es pot fer un recorregut d'un arbre en profunditat o en amplada. Els recorreguts en amplada són per nivells, es realitza horitzontalment des de l'arrel a tots els fills abans de passar a la descendència d'algun dels fills. El recorregut en profunditat porta al camí des de l'arrel cap al descendent més llunyà del primer fill i després continua amb el fill. Una propietat dels BST és que en fer un recorregut en profunditat inorder obtenim els elements ordenats de forma ascendent. <figure class="mw-halign-left" typeof="mw:File/Frame"><a href="/wiki/Fitxer:ABBEJEM.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/f/f0/ABBEJEM.svg/328px-ABBEJEM.svg.png" decoding="async" width="328" height="152" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/f/f0/ABBEJEM.svg/492px-ABBEJEM.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/f/f0/ABBEJEM.svg/656px-ABBEJEM.svg.png 2x" data-file-width="328" data-file-height="152" /></a><figcaption>Exemple arbre binari de cerca</figcaption></figure> Resultat de fer el recorregut a: Inorder = [6, 9, 13, 14, 15, 17, 20, 26, 64, 72]. Preorder = [15, 9, 6, 14, 13, 20, 17, 64, 26, 72]. Postorder = [6, 13, 14, 9, 17, 26, 72, 64, 20, 15]. <div class="mw-heading mw-heading2"><h2 id="Tipus_d'arbres_binaris_de_cerca">Tipus d'arbres binaris de cerca</h2>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=8" title="Modifica la secció: Tipus d'arbres binaris de cerca">modifica</a>]</div> Hi ha diversos tipus d'arbres binaris de cerca. Els <a href="/w/index.php?title=Arbre_AVL&action=edit&redlink=1" class="new" title="Arbre AVL (encara no existeix)">arbre AVL</a>, <a href="/w/index.php?title=Arbre_Vermell-Negre&action=edit&redlink=1" class="new" title="Arbre Vermell-Negre (encara no existeix)">arbres vermell-negre</a>, són arbres autobalancejables. Els <a href="/w/index.php?title=Arbre_bisellat&action=edit&redlink=1" class="new" title="Arbre bisellat (encara no existeix)">arbres bisellats</a> són arbres també autobalancejables amb la propietat que els elements accedits recentment s'accediran més ràpid en posteriors accessos. Al <a href="/w/index.php?title=Monticle_(inform%C3%A0tica)&action=edit&redlink=1" class="new" title="Monticle (informàtica) (encara no existeix)">monticle</a>, com en tots els arbres binaris de cerca, cada node pare té un valor major que els seus fills i a més és complet, és a dir que tots els nivells estan plens amb excepció de l'últim, que pot no estar-ho. Dues maneres de configurar un arbre binari de cerca podria ser com un arbre complet o degenerat. Un arbre complet és un arbre amb "n" nivells, on cada nivell d és menor o igual que n-1, el nombre de nodes existents en el nivell "d" és igual que 2d. Això vol dir que tots els possibles nodes existeixen en aquests nivells, no hi ha cap forat. Un requeriment addicional per a un arbre binari complet és que per al nivell "n", els nodes han d'estar ocupats d'esquerra a dreta, i no hi podrà haver un forat a l'esquerra d'un node ocupat. Un arbre degeneratiu és un arbre que, per a cada node pare, només hi ha associat un node fill; es comporta com una llista enllaçada. <div class="mw-heading mw-heading2"><h2 id="Comparació_de_rendiment">Comparació de rendiment</h2>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=9" title="Modifica la secció: Comparació de rendiment">modifica</a>]</div> D. A. Heger (2004)<a href="#cite_note-2">[2]</a> realitzà una comparació entre els diferents tipus d'arbres binaris de cerca per trobar quin tipus ens donaria el millor rendiment per a cada cas. Els monticles es troben com el tipus d'arbre binari de cerca que millor resultat mitjana dona, mentre que els arbres vermell-negre els que menor rendiment mitjà ens aporten. <div class="mw-heading mw-heading3"><h3 id="Arbre_binari_de_cerca_òptim">Arbre binari de cerca òptim</h3>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=10" title="Modifica la secció: Arbre binari de cerca òptim">modifica</a>]</div> Si no es pretén planificar un arbre binari de cerca, i sabem exactament amb quina freqüència serà visitat cada element, es pot construir un arbre binari de cerca òptim amb l'objectiu de que la mitjana de despesa generada a l'hora de buscar un element sigui minimitzada. Assumint que coneixem els elements i en quin nivell està cada un, també coneixem la proporció de futures recerques que es faran per trobar aquest element. Si és així, podem utilitzar una solució basada en la <a href="/w/index.php?title=Programaci%C3%B3_din%C3%A0mica_(computaci%C3%B3)&action=edit&redlink=1" class="new" title="Programació dinàmica (computació) (encara no existeix)">programació dinàmica</a>. En canvi, de vegades només tenim l'estimació dels costos de recerca, com passa amb els sistemes que ens mostren el temps que ha necessitat per a realitzar una cerca. Un exemple, si tenim un BST de paraules usat en un <a href="/wiki/Corrector_ortogr%C3%A0fic" title="Corrector ortogràfic">corrector ortogràfic</a>, s'hauria d'equilibrar l'arbre basat en la freqüència que té una paraula en el <a href="/wiki/Corpus_ling%C3%BC%C3%ADstic" title="Corpus lingüístic">Corpus lingüístic</a>, desplaçant paraules molt freqüents a prop de l'arrel i paraules menys freqúents a prop de les fulles. Un arbre com a tal podria ser comparat amb els <a href="/wiki/Codificaci%C3%B3_Huffman" class="mw-redirect" title="Codificació Huffman">arbres Huffman</a> que tracten de trobar elements que són accedits freqüentment a prop de l'arrel per produir una densa informació; de tota manera, els arbres Huffman només poden guardar elements que contenen dades en les fulles i aquests elements no necessiten ser ordenats. Arbres alfabètics són arbres Huffman amb una restricció d'ordre addicional o cosa que és el mateix, arbres de cerca amb modificació tal que tots els elements són emmagatzemats a les fulles. <div class="mw-heading mw-heading2"><h2 id="Vegeu_també">Vegeu també</h2>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=11" title="Modifica la secció: Vegeu també">modifica</a>]</div> <div style="-moz-column-count:2; column-count:2;"> <ul><li><a href="/wiki/Arbre_(estructura_de_dades)" title="Arbre (estructura de dades)">Arbre (estructura de dades)</a></li> <li><a href="/wiki/Arbre_binari" title="Arbre binari">Arbre binari</a></li> <li><a href="/w/index.php?title=Arbre_AVL&action=edit&redlink=1" class="new" title="Arbre AVL (encara no existeix)">Arbre AVL</a></li> <li><a href="/w/index.php?title=Arbre_2-3&action=edit&redlink=1" class="new" title="Arbre 2-3 (encara no existeix)">Arbre 2-3</a></li> <li><a href="/wiki/Arbre-B" title="Arbre-B">Arbre-B</a></li> <li><a href="/w/index.php?title=Arbre_vermell-negre&action=edit&redlink=1" class="new" title="Arbre vermell-negre (encara no existeix)">Arbre vermell-negre</a></li> <li><a href="/w/index.php?title=Arbre_biselat&action=edit&redlink=1" class="new" title="Arbre biselat (encara no existeix)">Arbre biselat</a></li> <li><a href="/w/index.php?title=Arbre_multiarrel&action=edit&redlink=1" class="new" title="Arbre multiarrel (encara no existeix)">Arbre multiarrel</a></li></ul> </div> <div class="mw-heading mw-heading2"><h2 id="Referències">Referències</h2>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=12" title="Modifica la secció: Referències">modifica</a>]</div> <div class="reflist {{#if: | references-column-count references-column-count-{{{col}}}" style="list-style-type: decimal;"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-1"><a href="#cite_ref-1">↑</a> s. <a href="/w/index.php?title=Robert_Sedgewick_(computer_scientist)&action=edit&redlink=1" class="new" title="Robert Sedgewick (computer scientist) (encara no existeix)">Robert Sedgewick</a>, Kevin Wayne: <a rel="nofollow" class="external text" href="http://www.albertstam.com/Algorithms.pdf">Algorithms Fourth Edition.</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20161018061612/http://albertstam.com/Algorithms.pdf">Arxivat</a> 2016-10-18 a <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a>. Pearson Education, 2011, <a href="/wiki/Especial:Fonts_bibliogr%C3%A0fiques/978-0-321-57351-3" title="Especial:Fonts bibliogràfiques/978-0-321-57351-3">ISBN 978-0-321-57351-3</a>, p. 410. </li> <li id="cite_note-2"><a href="#cite_ref-2">↑</a> Heger, Dominique A. «<a rel="nofollow" class="external text" href="http://www.cepis.org/upgrade/files/full-2004-V.pdf">A Disquisition on The Performance Behavior of Binary Search Tree Data Structures</a>». European Journal for the Informatics Professional, 5, 2004, p. 67-75. </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="Bibliografia">Bibliografia</h2>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=13" title="Modifica la secció: Bibliografia">modifica</a>]</div> <ul><li>© Aquest article inclou material de <a href="/wiki/Domini_p%C3%BAblic" title="Domini públic">domini públic</a> provinent de l'<a href="/wiki/Institut_Nacional_d%27Est%C3%A0ndards_i_Tecnologia" title="Institut Nacional d'Estàndards i Tecnologia">Institut Nacional d'Estàndards i Tecnologia</a> (NIST). Black, Paul E. <a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/binarySearchTree.html">Binary Search Tree</a>.</li> <li><a href="/w/index.php?title=Kurt_Mehlhorn&action=edit&redlink=1" class="new" title="Kurt Mehlhorn (encara no existeix)">Mehlhorn, Kurt</a>; <a href="/w/index.php?title=Peter_Sanders_(computer_scientist)&action=edit&redlink=1" class="new" title="Peter Sanders (computer scientist) (encara no existeix)">Sanders, Peter</a>. <a rel="nofollow" class="external text" href="http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/SortedSequences.pdf">Algorithms and Data Structures: The Basic Toolbox</a>. Springer, 2008.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algorithms+and+Data+Structures%3A+The+Basic+Toolbox&rft.date=2008&rft.pub=Springer&rft_id=http%3A%2F%2Fpeople.mpi-inf.mpg.de%2F%7Emehlhorn%2Fftp%2FToolbox%2FSortedSequences.pdf"> </li> <li>Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. «12: Binary search trees, 15.5: Optimal binary search trees». A: Introduction to Algorithms. 2a edició. MIT Press & McGraw-Hill, 2001, p. 253–272, 356–363. <a href="/wiki/Especial:Fonts_bibliogr%C3%A0fiques/0-262-03293-7" title="Especial:Fonts bibliogràfiques/0-262-03293-7">ISBN 0-262-03293-7</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Algorithms&rft.atitle=12%3A+Binary+search+trees%2C+15.5%3A+Optimal+binary+search+trees&rft.date=2001&rft.edition=2a+edici%C3%B3&rft.pub=MIT+Press+%26+McGraw-Hill&rft.pages=253%E2%80%93272%2C+356%E2%80%93363&rft.isbn=0-262-03293-7"> </li> <li>Jarc, Duane J. «<a rel="nofollow" class="external text" href="https://web.archive.org/web/20140227082917/http://nova.umuc.edu/~jarc/idsv/lesson1.html">Binary Tree Traversals</a>». Interactive Data Structure Visualizations. <a href="/wiki/University_of_Maryland" class="mw-redirect" title="University of Maryland">University of Maryland</a>, 03-12-2005. Arxivat de l'<a rel="nofollow" class="external text" href="http://nova.umuc.edu/~jarc/idsv/lesson1.html">original</a> el 27 de febrer 2014. [Consulta: 13 març 2020].</li> <li><a href="/wiki/Donald_Knuth" title="Donald Knuth">Knuth, Donald</a>. «6.2.2: Binary Tree Searching». A: <a href="/wiki/The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a>. 3: "Sorting and Searching". 3rd. Addison-Wesley, 1997, p. 426–458. <a href="/wiki/Especial:Fonts_bibliogr%C3%A0fiques/0-201-89685-0" title="Especial:Fonts bibliogràfiques/0-201-89685-0">ISBN 0-201-89685-0</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=%5B%5BThe+Art+of+Computer+Programming%5D%5D&rft.atitle=6.2.2%3A+Binary+Tree+Searching&rft.aulast=Knuth&rft.aufirst=Donald&rft.date=1997&rft.edition=3rd&rft.pub=Addison-Wesley&rft.pages=426%E2%80%93458&rft.isbn=0-201-89685-0"> </li> <li>Long, Sean. «<a rel="nofollow" class="external text" href="http://employees.oneonta.edu/zhangs/PowerPointPlatform/resources/samples/binarysearchtree.ppt">Binary Search Tree</a>» (<a href="/wiki/Microsoft_PowerPoint" title="Microsoft PowerPoint">PPT</a>). Data Structures and Algorithms Visualization-A PowerPoint Slides Based Approach. SUNY Oneonta.</li> <li>Parlante, Nick. «<a rel="nofollow" class="external text" href="http://cslibrary.stanford.edu/110/BinaryTrees.html">Binary Trees</a>». CS Education Library. <a href="/wiki/Universitat_Stanford" title="Universitat Stanford">Universitat Stanford</a>, 2001.</li> <li>«<a rel="nofollow" class="external text" href="https://grisha.org/blog/2013/04/02/linus-on-understanding-pointers/">Linus on understanding pointers</a>». [Consulta: 21 febrer 2019].</li></ul> <div class="mw-heading mw-heading2"><h2 id="Enllaços_externs">Enllaços externs</h2>[<a href="/w/index.php?title=Arbre_binari_de_cerca&action=edit&section=14" title="Modifica la secció: Enllaços externs">modifica</a>]</div> <style data-mw-deduplicate="TemplateStyles:r33663753">.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:#f9f9f9;display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}.mw-parser-output .side-box-center{clear:both;margin:auto}}</style><div class="side-box metadata side-box-right plainlinks"> <div class="side-box-flex"> <div class="side-box-image"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png" decoding="async" width="30" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/45px-Commons-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/59px-Commons-logo.svg.png 2x" data-file-width="1024" data-file-height="1376" /></div> <div class="side-box-text plainlist">A <a class="external text" href="https://commons.wikimedia.org/wiki/P%C3%A0gina_principal?uselang=ca">Wikimedia Commons</a> hi ha contingut multimèdia relatiu a: <a href="https://commons.wikimedia.org/wiki/Category:Binary_search_trees" class="extiw" title="commons:Category:Binary search trees">Arbre binari de cerca</a></div></div> </div> <ul><li><a rel="nofollow" class="external text" href="http://btv.melezinek.cz">Binary Tree Visualizer</a> (Animació feta amb Javascript de vàries estructures d'arbres binaris)</li> <li><a rel="nofollow" class="external text" href="http://code.activestate.com/recipes/286239/">Binary Search Tree Exemple en Python</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100311192315/http://code.activestate.com/recipes/286239/">Arxivat</a> 2010-03-11 a <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a>.</li> <li>«<a rel="nofollow" class="external text" href="http://msdn.microsoft.com/en-us/library/1sf8shae%28v=vs.80%29.aspx">References to Pointers (C++)</a>». <a href="/w/index.php?title=Microsoft_Developer_Network&action=edit&redlink=1" class="new" title="Microsoft Developer Network (encara no existeix)">MSDN</a>. <a href="/wiki/Microsoft" title="Microsoft">Microsoft</a>, 2005. (Exemple d'implementació de l'arbre)</li></ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Obtingut de «<a dir="ltr" href="https://ca.wikipedia.org/w/index.php?title=Arbre_binari_de_cerca&oldid=34123125">https://ca.wikipedia.org/w/index.php?title=Arbre_binari_de_cerca&oldid=34123125</a>»</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Especial:Categorias" title="Especial:Categorias">Categoria</a>: <ul><li><a href="/wiki/Categoria:Estructura_de_dades" title="Categoria:Estructura de dades">Estructura de dades</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Categories ocultes: <ul><li><a href="/wiki/Categoria:P%C3%A0gines_amb_errors_de_marcatge_de_sintaxi" title="Categoria:Pàgines amb errors de marcatge de sintaxi">Pàgines amb errors de marcatge de sintaxi</a></li><li><a href="/wiki/Categoria:Articles_amb_la_plantilla_Webarchive_amb_enlla%C3%A7_wayback" title="Categoria:Articles amb la plantilla Webarchive amb enllaç wayback">Articles amb la plantilla Webarchive amb enllaç wayback</a></li><li><a href="/wiki/Categoria:P%C3%A0gines_amb_enlla%C3%A7_commonscat_des_de_Wikidata" title="Categoria:Pàgines amb enllaç commonscat des de Wikidata">Pàgines amb enllaç commonscat des de Wikidata</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 pàgina va ser modificada per darrera vegada el 18 oct 2024 a les 08:11.</li> <li id="footer-info-copyright">El text està disponible sota la <a href="/wiki/Viquip%C3%A8dia:Text_de_la_llic%C3%A8ncia_de_Creative_Commons_Reconeixement-Compartir_Igual_4.0_No_adaptada" title="Viquipèdia:Text de la llicència de Creative Commons Reconeixement-Compartir Igual 4.0 No adaptada"> Llicència de Creative Commons Reconeixement i Compartir-Igual</a>; es poden aplicar termes addicionals. Vegeu les <a class="external text" href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use/ca">Condicions d'ús</a>. Wikipedia® (Viquipèdia™) és una <a href="/wiki/Marca_comercial" title="Marca comercial">marca registrada</a> de <a rel="nofollow" class="external text" href="https://www.wikimediafoundation.org">Wikimedia Foundation, Inc</a>. </li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Política de privadesa</a></li> <li id="footer-places-about"><a href="/wiki/Viquip%C3%A8dia:Quant_a_la_Viquip%C3%A8dia">Quant al projecte Viquipèdia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Viquip%C3%A8dia:Av%C3%ADs_d%27exempci%C3%B3_de_responsabilitat">Descàrrec de responsabilitat</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Codi de conducta</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Desenvolupadors</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/ca.wikipedia.org">Estadístiques</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Declaració de cookies</a></li> <li id="footer-places-mobileview"><a href="//ca.m.wikipedia.org/w/index.php?title=Arbre_binari_de_cerca&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Versió per a mòbils</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" 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"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </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-f69cdc8f6-xqqpl","wgBackendResponseTime":148,"wgPageParseReport":{"limitreport":{"cputime":"0.236","walltime":"1.240","ppvisitednodes":{"value":2655,"limit":1000000},"postexpandincludesize":{"value":17813,"limit":2097152},"templateargumentsize":{"value":6555,"limit":2097152},"expansiondepth":{"value":13,"limit":100},"expensivefunctioncount":{"value":10,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":47951,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 1035.510 1 -total"," 6.07% 62.808 1 Plantilla:Commonscat"," 5.46% 56.496 1 Plantilla:Referències"," 5.24% 54.296 1 Plantilla:Sister"," 5.02% 51.938 1 Plantilla:Caixa_lateral"," 2.59% 26.797 1 Plantilla:Citar_ref"," 2.34% 24.274 5 Plantilla:Ref-web"," 2.25% 23.321 1 Plantilla:Citar_publicació"," 1.88% 19.441 2 Plantilla:Webarchive"," 1.81% 18.789 3 Plantilla:Ref-llibre"]},"scribunto":{"limitreport-timeusage":{"value":"0.046","limit":"10.000"},"limitreport-memusage":{"value":1283797,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-84d8f4b96-b4bml","timestamp":"20241117095823","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Arbre binari de cerca","url":"https:\/\/ca.wikipedia.org\/wiki\/Arbre_binari_de_cerca","sameAs":"http:\/\/www.wikidata.org\/entity\/Q623818","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q623818","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2010-03-27T17:55:41Z","dateModified":"2024-10-18T07:11:10Z"}</script> </body> </html>