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="pl" dir="ltr"> <head> <meta charset="UTF-8"> <title>Binarne drzewo poszukiwań – Wikipedia, wolna encyklopedia</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(/(?:^|; )plwikimwclientpreferences=([^;]+)/);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":["","styczeń","luty","marzec","kwiecień","maj","czerwiec","lipiec","sierpień","wrzesień","październik","listopad","grudzień"],"wgRequestId":"a19cdde3-11c2-417a-ba9b-85a95b36c6ff","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Binarne_drzewo_poszukiwań","wgTitle":"Binarne drzewo poszukiwań","wgCurRevisionId":69794177,"wgRevisionId":69794177,"wgArticleId":19117,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Zalążki sekcji artykułów","Drzewa (informatyka)"],"wgPageViewLanguage":"pl","wgPageContentLanguage":"pl","wgPageContentModel":"wikitext","wgRelevantPageName":"Binarne_drzewo_poszukiwań","wgRelevantArticleId":19117,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":true,"wgFlaggedRevsParams":{ "tags":{"accuracy":{"levels":1}}},"wgStableRevisionId":69794177,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"pl","pageLanguageDir":"ltr","pageVariantFallbacks":"pl"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":10000,"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.gadget.wikiflex":"ready","ext.gadget.infobox":"ready","ext.gadget.hlist":"ready","ext.gadget.darkmode-overrides":"ready","ext.gadget.small-references":"ready","ext.gadget.citation-access-info":"ready","ext.gadget.sprawdz-problemy-szablony":"ready","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.cite.styles":"ready","ext.pygments":"ready","mediawiki.page.gallery.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.flaggedRevs.basic":"ready","mediawiki.codex.messagebox.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","mediawiki.page.media","ext.scribunto.logs", "site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.flaggedRevs.advanced","ext.gadget.ll-script-loader","ext.gadget.veKeepParameters","ext.gadget.szablon-galeria","ext.gadget.NavFrame","ext.gadget.citoid-overrides","ext.gadget.maps","ext.gadget.padlock-indicators","ext.gadget.interwiki-langlist","ext.gadget.edit-summaries","ext.gadget.edit-first-section","ext.gadget.wikibugs","ext.gadget.map-toggler","ext.gadget.narrowFootnoteColumns","ext.gadget.WDsearch","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","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=pl&modules=ext.cite.styles%7Cext.flaggedRevs.basic%7Cext.math.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cmediawiki.codex.messagebox.styles%7Cmediawiki.page.gallery.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=pl&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=pl&modules=ext.gadget.citation-access-info%2Cdarkmode-overrides%2Chlist%2Cinfobox%2Csmall-references%2Csprawdz-problemy-szablony%2Cwikiflex&only=styles&skin=vector-2022"> <link rel="stylesheet" href="/w/load.php?lang=pl&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 property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/1200px-Binary_search_tree.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1000"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/800px-Binary_search_tree.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="667"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/640px-Binary_search_tree.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="533"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Binarne drzewo poszukiwań – Wikipedia, wolna encyklopedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//pl.m.wikipedia.org/wiki/Binarne_drzewo_poszukiwa%C5%84"> <link rel="alternate" type="application/x-wiki" title="Edytuj" href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&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="Wikipedia (pl)"> <link rel="EditURI" type="application/rsd+xml" href="//pl.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://pl.wikipedia.org/wiki/Binarne_drzewo_poszukiwa%C5%84"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.pl"> <link rel="alternate" type="application/atom+xml" title="Kanał Atom Wikipedii" href="/w/index.php?title=Specjalna:Ostatnie_zmiany&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-Binarne_drzewo_poszukiwań rootpage-Binarne_drzewo_poszukiwań skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Przejdź do zawartości</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="Witryna"> <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="Menu główne" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Menu główne</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Menu główne</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">przypnij</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">ukryj</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Nawigacja </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Wikipedia:Strona_g%C5%82%C3%B3wna" title="Przejdź na stronę główną [z]" accesskey="z"><span>Strona główna</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Specjalna:Losowa_strona" title="Załaduj losową stronę [x]" accesskey="x"><span>Losuj artykuł</span></a></li><li id="n-Kategorie" class="mw-list-item"><a href="/wiki/Portal:Kategorie_G%C5%82%C3%B3wne"><span>Kategorie artykułów</span></a></li><li id="n-Featured-articles" class="mw-list-item"><a href="/wiki/Wikipedia:Wyr%C3%B3%C5%BCniona_zawarto%C5%9B%C4%87_Wikipedii"><span>Najlepsze artykuły</span></a></li><li id="n-FAQ" class="mw-list-item"><a href="/wiki/Pomoc:FAQ"><span>Częste pytania (FAQ)</span></a></li> </ul> </div> </div> <div id="p-zmiany" class="vector-menu mw-portlet mw-portlet-zmiany" > <div class="vector-menu-heading"> Dla czytelników </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-czytelnicy" class="mw-list-item"><a href="/wiki/Wikipedia:O_Wikipedii"><span>O Wikipedii</span></a></li><li id="n-contact" class="mw-list-item"><a href="/wiki/Wikipedia:Kontakt_z_wikipedystami"><span>Kontakt</span></a></li> </ul> </div> </div> <div id="p-edytorzy" class="vector-menu mw-portlet mw-portlet-edytorzy" > <div class="vector-menu-heading"> Dla wikipedystów </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-pierwsze-kroki" class="mw-list-item"><a href="/wiki/Pomoc:Pierwsze_kroki"><span>Pierwsze kroki</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Portal_wikipedyst%C3%B3w" title="O projekcie – co możesz zrobić, gdzie możesz znaleźć informacje"><span>Portal wikipedystów</span></a></li><li id="n-Noticeboard" class="mw-list-item"><a href="/wiki/Wikipedia:Tablica_og%C5%82osze%C5%84"><span>Ogłoszenia</span></a></li><li id="n-Guidelines" class="mw-list-item"><a href="/wiki/Wikipedia:Zasady"><span>Zasady</span></a></li><li id="n-helppage-name" class="mw-list-item"><a href="/wiki/Pomoc:Spis_tre%C5%9Bci"><span>Pomoc</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Specjalna:Ostatnie_zmiany" title="Lista ostatnich zmian w Wikipedii. [r]" accesskey="r"><span>Ostatnie zmiany</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Wikipedia:Strona_g%C5%82%C3%B3wna" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="wolna encyklopedia" src="/static/images/mobile/copyright/wikipedia-tagline-pl.svg" width="120" height="13" style="width: 7.5em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Specjalna:Szukaj" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Przeszukaj Wikipedię [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Szukaj</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Przeszukaj Wikipedię" aria-label="Przeszukaj Wikipedię" autocapitalize="sentences" title="Przeszukaj Wikipedię [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Specjalna:Szukaj"> </div> <button class="cdx-button cdx-search-input__end-button">Szukaj</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Narzędzia osobiste"> <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="Wygląd"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Zmień rozmiar czcionki, szerokość oraz kolorystykę strony" > <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="Wygląd" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Wygląd</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_pl.wikipedia.org&uselang=pl" class=""><span>Wspomóż Wikipedię</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Specjalna:Utw%C3%B3rz_konto&returnto=Binarne+drzewo+poszukiwa%C5%84" title="Zachęcamy do stworzenia konta i zalogowania, ale nie jest to obowiązkowe." class=""><span>Utwórz konto</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Specjalna:Zaloguj&returnto=Binarne+drzewo+poszukiwa%C5%84" title="Zachęcamy do zalogowania się, choć nie jest to obowiązkowe. [o]" accesskey="o" class=""><span>Zaloguj się</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Więcej opcji" > <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="Narzędzia osobiste" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Narzędzia osobiste</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="Menu użytkownika" > <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_pl.wikipedia.org&uselang=pl"><span>Wspomóż Wikipedię</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Specjalna:Utw%C3%B3rz_konto&returnto=Binarne+drzewo+poszukiwa%C5%84" title="Zachęcamy do stworzenia konta i zalogowania, ale nie jest to obowiązkowe."><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Utwórz konto</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Specjalna:Zaloguj&returnto=Binarne+drzewo+poszukiwa%C5%84" title="Zachęcamy do zalogowania się, choć nie jest to obowiązkowe. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Zaloguj się</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Strony dla anonimowych edytorów <a href="/wiki/Pomoc:Pierwsze_kroki" aria-label="Dowiedz się więcej na temat edytowania"><span>dowiedz się więcej</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Specjalna:M%C3%B3j_wk%C5%82ad" title="Lista edycji wykonanych z tego adresu IP [y]" accesskey="y"><span>Edycje</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Specjalna:Moja_dyskusja" title="Dyskusja użytkownika dla tego adresu IP [n]" accesskey="n"><span>Dyskusja</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Witryna"> <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="Spis treści" 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">Spis treści</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">przypnij</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">ukryj</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">Początek</div> </a> </li> <li id="toc-Operacje_wykonywane_na_drzewie" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Operacje_wykonywane_na_drzewie"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Operacje wykonywane na drzewie</span> </div> </a> <button aria-controls="toc-Operacje_wykonywane_na_drzewie-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Przełącz podsekcję Operacje wykonywane na drzewie</span> </button> <ul id="toc-Operacje_wykonywane_na_drzewie-sublist" class="vector-toc-list"> <li id="toc-Operacje_wyszukiwania" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Operacje_wyszukiwania"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>Operacje wyszukiwania</span> </div> </a> <ul id="toc-Operacje_wyszukiwania-sublist" class="vector-toc-list"> <li id="toc-Wyszukiwanie_dowolnego_klucza_w_drzewie" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Wyszukiwanie_dowolnego_klucza_w_drzewie"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1.1</span> <span>Wyszukiwanie dowolnego klucza w drzewie</span> </div> </a> <ul id="toc-Wyszukiwanie_dowolnego_klucza_w_drzewie-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Wyszukiwanie_najmniejszego_i_największego_klucza_w_drzewie" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Wyszukiwanie_najmniejszego_i_największego_klucza_w_drzewie"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1.2</span> <span>Wyszukiwanie najmniejszego i największego klucza w drzewie</span> </div> </a> <ul id="toc-Wyszukiwanie_najmniejszego_i_największego_klucza_w_drzewie-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Wyszukiwanie_następnika_i_poprzednika_w_drzewie" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Wyszukiwanie_następnika_i_poprzednika_w_drzewie"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1.3</span> <span>Wyszukiwanie następnika i poprzednika w drzewie</span> </div> </a> <ul id="toc-Wyszukiwanie_następnika_i_poprzednika_w_drzewie-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Wstawianie_klucza" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Wstawianie_klucza"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.2</span> <span>Wstawianie klucza</span> </div> </a> <ul id="toc-Wstawianie_klucza-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Usuwanie_klucza" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Usuwanie_klucza"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.3</span> <span>Usuwanie klucza</span> </div> </a> <ul id="toc-Usuwanie_klucza-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Wyważanie_drzewa" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Wyważanie_drzewa"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Wyważanie drzewa</span> </div> </a> <ul id="toc-Wyważanie_drzewa-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Optymalne_drzewo_poszukiwań" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Optymalne_drzewo_poszukiwań"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Optymalne drzewo poszukiwań</span> </div> </a> <ul id="toc-Optymalne_drzewo_poszukiwań-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Zobacz_też" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Zobacz_też"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Zobacz też</span> </div> </a> <ul id="toc-Zobacz_też-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Przypisy" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Przypisy"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Przypisy</span> </div> </a> <ul id="toc-Przypisy-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Linki_zewnętrzne" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Linki_zewnętrzne"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Linki zewnętrzne</span> </div> </a> <ul id="toc-Linki_zewnętrzne-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="Spis treści" 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="Przełącz stan spisu treści" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Przełącz stan spisu treści</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Binarne drzewo poszukiwań</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Przejdź do artykułu w innym języku. Treść dostępna w 34 językach" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-34" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">34 języki</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%B4%D8%AC%D8%B1%D8%A9_%D8%A8%D8%AD%D8%AB_%D8%AB%D9%86%D8%A7%D8%A6%D9%8A%D8%A9" title="شجرة بحث ثنائية – arabski" lang="ar" hreflang="ar" data-title="شجرة بحث ثنائية" data-language-autonym="العربية" data-language-local-name="arabski" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE_%D0%B4%D1%8A%D1%80%D0%B2%D0%BE_%D0%B7%D0%B0_%D1%82%D1%8A%D1%80%D1%81%D0%B5%D0%BD%D0%B5" title="Двоично дърво за търсене – bułgarski" lang="bg" hreflang="bg" data-title="Двоично дърво за търсене" data-language-autonym="Български" data-language-local-name="bułgarski" class="interlanguage-link-target"><span>Български</span></a></li><li class="interlanguage-link interwiki-bs mw-list-item"><a href="https://bs.wikipedia.org/wiki/Binarno_stablo_pretra%C5%BEivanja" title="Binarno stablo pretraživanja – bośniacki" lang="bs" hreflang="bs" data-title="Binarno stablo pretraživanja" data-language-autonym="Bosanski" data-language-local-name="bośniacki" class="interlanguage-link-target"><span>Bosanski</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Arbre_binari_de_cerca" title="Arbre binari de cerca – kataloński" lang="ca" hreflang="ca" data-title="Arbre binari de cerca" data-language-autonym="Català" data-language-local-name="kataloński" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Bin%C3%A1rn%C3%AD_vyhled%C3%A1vac%C3%AD_strom" title="Binární vyhledávací strom – czeski" lang="cs" hreflang="cs" data-title="Binární vyhledávací strom" data-language-autonym="Čeština" data-language-local-name="czeski" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Bin%C3%A6rt_s%C3%B8getr%C3%A6" title="Binært søgetræ – duński" lang="da" hreflang="da" data-title="Binært søgetræ" data-language-autonym="Dansk" data-language-local-name="duński" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum" title="Binärer Suchbaum – niemiecki" lang="de" hreflang="de" data-title="Binärer Suchbaum" data-language-autonym="Deutsch" data-language-local-name="niemiecki" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-en badge-Q17437798 badge-goodarticle mw-list-item" title="dobry artykuł"><a href="https://en.wikipedia.org/wiki/Binary_search_tree" title="Binary search tree – angielski" lang="en" hreflang="en" data-title="Binary search tree" data-language-autonym="English" data-language-local-name="angielski" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/%C3%81rbol_binario_de_b%C3%BAsqueda" title="Árbol binario de búsqueda – hiszpański" lang="es" hreflang="es" data-title="Árbol binario de búsqueda" data-language-autonym="Español" data-language-local-name="hiszpański" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C_%D8%AF%D9%88%D8%AF%D9%88%DB%8C%DB%8C" title="درخت جستجوی دودویی – perski" lang="fa" hreflang="fa" data-title="درخت جستجوی دودویی" data-language-autonym="فارسی" data-language-local-name="perski" class="interlanguage-link-target"><span>فارسی</span></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 – francuski" lang="fr" hreflang="fr" data-title="Arbre binaire de recherche" data-language-autonym="Français" data-language-local-name="francuski" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC" title="이진 탐색 트리 – koreański" lang="ko" hreflang="ko" data-title="이진 탐색 트리" data-language-autonym="한국어" data-language-local-name="koreański" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-hy mw-list-item"><a href="https://hy.wikipedia.org/wiki/%D4%B2%D5%AB%D5%B6%D5%A1%D6%80_%D5%B8%D6%80%D5%B8%D5%B6%D5%B4%D5%A1%D5%B6_%D5%AE%D5%A1%D5%BC" title="Բինար որոնման ծառ – ormiański" lang="hy" hreflang="hy" data-title="Բինար որոնման ծառ" data-language-autonym="Հայերեն" data-language-local-name="ormiański" class="interlanguage-link-target"><span>Հայերեն</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Pohon_Pencarian_Biner" title="Pohon Pencarian Biner – indonezyjski" lang="id" hreflang="id" data-title="Pohon Pencarian Biner" data-language-autonym="Bahasa Indonesia" data-language-local-name="indonezyjski" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Albero_binario_di_ricerca" title="Albero binario di ricerca – włoski" lang="it" hreflang="it" data-title="Albero binario di ricerca" data-language-autonym="Italiano" data-language-local-name="włoski" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A2%D7%A5_%D7%97%D7%99%D7%A4%D7%95%D7%A9" title="עץ חיפוש – hebrajski" lang="he" hreflang="he" data-title="עץ חיפוש" data-language-autonym="עברית" data-language-local-name="hebrajski" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-kn mw-list-item"><a href="https://kn.wikipedia.org/wiki/%E0%B2%AC%E0%B3%88%E0%B2%A8%E0%B2%B0%E0%B2%BF_%E0%B2%B8%E0%B2%B0%E0%B3%8D%E0%B2%9A%E0%B3%8D_%E0%B2%9F%E0%B3%8D%E0%B2%B0%E0%B3%80_(%E0%B2%AC%E0%B3%88%E0%B2%A8%E0%B2%B0%E0%B2%BF_%E0%B2%B9%E0%B3%81%E0%B2%A1%E0%B3%81%E0%B2%95%E0%B2%BE%E0%B2%9F%E0%B2%A6_%E0%B2%9F%E0%B3%8D%E0%B2%B0%E0%B3%80)" title="ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ (ಬೈನರಿ ಹುಡುಕಾಟದ ಟ್ರೀ) – kannada" lang="kn" hreflang="kn" data-title="ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ (ಬೈನರಿ ಹುಡುಕಾಟದ ಟ್ರೀ)" data-language-autonym="ಕನ್ನಡ" data-language-local-name="kannada" class="interlanguage-link-target"><span>ಕನ್ನಡ</span></a></li><li class="interlanguage-link interwiki-lmo mw-list-item"><a href="https://lmo.wikipedia.org/wiki/Alber_binari_de_ricerca" title="Alber binari de ricerca – lombardzki" lang="lmo" hreflang="lmo" data-title="Alber binari de ricerca" data-language-autonym="Lombard" data-language-local-name="lombardzki" class="interlanguage-link-target"><span>Lombard</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Binaire_zoekboom" title="Binaire zoekboom – niderlandzki" lang="nl" hreflang="nl" data-title="Binaire zoekboom" data-language-autonym="Nederlands" data-language-local-name="niderlandzki" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8" title="二分探索木 – japoński" lang="ja" hreflang="ja" data-title="二分探索木" data-language-autonym="日本語" data-language-local-name="japoński" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/%C3%81rvore_bin%C3%A1ria_de_busca" title="Árvore binária de busca – portugalski" lang="pt" hreflang="pt" data-title="Árvore binária de busca" data-language-autonym="Português" data-language-local-name="portugalski" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Arbore_binar_de_c%C4%83utare" title="Arbore binar de căutare – rumuński" lang="ro" hreflang="ro" data-title="Arbore binar de căutare" data-language-autonym="Română" data-language-local-name="rumuński" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0" title="Двоичное дерево поиска – rosyjski" lang="ru" hreflang="ru" data-title="Двоичное дерево поиска" data-language-autonym="Русский" data-language-local-name="rosyjski" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Bin%C3%A1rny_vyh%C4%BEad%C3%A1vac%C3%AD_strom" title="Binárny vyhľadávací strom – słowacki" lang="sk" hreflang="sk" data-title="Binárny vyhľadávací strom" data-language-autonym="Slovenčina" data-language-local-name="słowacki" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/Binarno_stablo_pretrage" title="Binarno stablo pretrage – serbski" lang="sr" hreflang="sr" data-title="Binarno stablo pretrage" data-language-autonym="Српски / srpski" data-language-local-name="serbski" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Binarno_stablo_pretrage" title="Binarno stablo pretrage – serbsko-chorwacki" lang="sh" hreflang="sh" data-title="Binarno stablo pretrage" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="serbsko-chorwacki" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Bin%C3%A4%C3%A4rinen_hakupuu" title="Binäärinen hakupuu – fiński" lang="fi" hreflang="fi" data-title="Binäärinen hakupuu" data-language-autonym="Suomi" data-language-local-name="fiński" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Bin%C3%A4rt_s%C3%B6ktr%C3%A4d" title="Binärt sökträd – szwedzki" lang="sv" hreflang="sv" data-title="Binärt sökträd" data-language-autonym="Svenska" data-language-local-name="szwedzki" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%95%E0%B9%89%E0%B8%99%E0%B9%84%E0%B8%A1%E0%B9%89%E0%B8%84%E0%B9%89%E0%B8%99%E0%B8%AB%E0%B8%B2%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B8%97%E0%B8%A7%E0%B8%B4%E0%B8%A0%E0%B8%B2%E0%B8%84" title="ต้นไม้ค้นหาแบบทวิภาค – tajski" lang="th" hreflang="th" data-title="ต้นไม้ค้นหาแบบทวิภาค" data-language-autonym="ไทย" data-language-local-name="tajski" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/%C4%B0kili_arama_a%C4%9Fac%C4%B1" title="İkili arama ağacı – turecki" lang="tr" hreflang="tr" data-title="İkili arama ağacı" data-language-autonym="Türkçe" data-language-local-name="turecki" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%94%D0%B2%D1%96%D0%B9%D0%BA%D0%BE%D0%B2%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D1%88%D1%83%D0%BA%D1%83" title="Двійкове дерево пошуку – ukraiński" lang="uk" hreflang="uk" data-title="Двійкове дерево пошуку" data-language-autonym="Українська" data-language-local-name="ukraiński" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n" title="Cây tìm kiếm nhị phân – wietnamski" 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="wietnamski" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9" title="二元搜尋樹 – kantoński" lang="yue" hreflang="yue" data-title="二元搜尋樹" data-language-autonym="粵語" data-language-local-name="kantoński" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9" title="二元搜尋樹 – chiński" lang="zh" hreflang="zh" data-title="二元搜尋樹" data-language-autonym="中文" data-language-local-name="chiński" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q623818#sitelinks-wikipedia" title="Edytuj linki pomiędzy wersjami językowymi" class="wbc-editpage">Edytuj linki</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Przestrzenie nazw"> <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/Binarne_drzewo_poszukiwa%C5%84" title="Zobacz stronę treści [c]" accesskey="c"><span>Artykuł</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Dyskusja:Binarne_drzewo_poszukiwa%C5%84" rel="discussion" title="Dyskusja o zawartości tej strony [t]" accesskey="t"><span>Dyskusja</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Zmień wariant języka" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">polski</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Widok"> <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/Binarne_drzewo_poszukiwa%C5%84"><span>Czytaj</span></a></li><li id="ca-ve-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit" title="Edytuj tę stronę [v]" accesskey="v"><span>Edytuj</span></a></li><li id="ca-edit" class="collapsible vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit" title="Edycja kodu źródłowego strony [e]" accesskey="e"><span>Edytuj kod źródłowy</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=history" title="Starsze wersje tej strony [h]" accesskey="h"><span>Wyświetl historię</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Narzędzia dla stron"> <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="Narzędzia" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Narzędzia</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Narzędzia</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">przypnij</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">ukryj</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="Więcej opcji" > <div class="vector-menu-heading"> Działania </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/Binarne_drzewo_poszukiwa%C5%84"><span>Czytaj</span></a></li><li id="ca-more-ve-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit" title="Edytuj tę stronę [v]" accesskey="v"><span>Edytuj</span></a></li><li id="ca-more-edit" class="collapsible vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit" title="Edycja kodu źródłowego strony [e]" accesskey="e"><span>Edytuj kod źródłowy</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=history"><span>Wyświetl historię</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> Ogólne </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Specjalna:Linkuj%C4%85ce/Binarne_drzewo_poszukiwa%C5%84" title="Pokaż listę wszystkich stron linkujących do tej strony [j]" accesskey="j"><span>Linkujące</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Specjalna:Zmiany_w_linkowanych/Binarne_drzewo_poszukiwa%C5%84" rel="nofollow" title="Ostatnie zmiany w stronach, do których ta strona linkuje [k]" accesskey="k"><span>Zmiany w linkowanych</span></a></li><li id="t-upload" class="mw-list-item"><a href="//pl.wikipedia.org/wiki/Wikipedia:Prześlij_plik" title="Prześlij pliki [u]" accesskey="u"><span>Prześlij plik</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Specjalna:Strony_specjalne" title="Lista wszystkich stron specjalnych [q]" accesskey="q"><span>Strony specjalne</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&oldid=69794177" title="Stały link do tej wersji tej strony"><span>Link do tej wersji</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=info" title="Więcej informacji na temat tej strony"><span>Informacje o tej stronie</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Specjalna:Cytuj&page=Binarne_drzewo_poszukiwa%C5%84&id=69794177&wpFormIdentifier=titleform" title="Informacja o tym jak należy cytować tę stronę"><span>Cytowanie tego artykułu</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Specjalna:Skr%C3%B3%C4%87_adres_URL&url=https%3A%2F%2Fpl.wikipedia.org%2Fwiki%2FBinarne_drzewo_poszukiwa%25C5%2584"><span>Zobacz skrócony adres URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Specjalna:Kod_QR&url=https%3A%2F%2Fpl.wikipedia.org%2Fwiki%2FBinarne_drzewo_poszukiwa%25C5%2584"><span>Pobierz kod QR</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Drukuj lub eksportuj </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=Specjalna:Ksi%C4%85%C5%BCka&bookcmd=book_creator&referer=Binarne+drzewo+poszukiwa%C5%84"><span>Utwórz książkę</span></a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Specjalna:DownloadAsPdf&page=Binarne_drzewo_poszukiwa%C5%84&action=show-download-screen"><span>Pobierz jako PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&printable=yes" title="Wersja do wydruku [p]" accesskey="p"><span>Wersja do druku</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> W innych projektach </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Binary_search_trees" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q623818" title="Link do powiązanego elementu w repozytorium danych [g]" accesskey="g"><span>Element Wikidanych</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Narzędzia dla stron"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Wygląd"> <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">Wygląd</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">przypnij</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">ukryj</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">Z Wikipedii, wolnej encyklopedii</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="pl" dir="ltr"><figure typeof="mw:File/Thumb"><a href="/wiki/Plik:Binary_search_tree.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/250px-Binary_search_tree.svg.png" decoding="async" width="250" height="208" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/375px-Binary_search_tree.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/500px-Binary_search_tree.svg.png 2x" data-file-width="300" data-file-height="250" /></a><figcaption>Binarne drzewo poszukiwań o wielkości równej 9, a wysokości równej 3; wierzchołek '8' jest tu korzeniem, a wierzchołki '1', '4', '7' i '13', to liście</figcaption></figure> <p><b>Binarne drzewo poszukiwań</b> (<a href="/wiki/J%C4%99zyk_angielski" title="Język angielski">ang.</a> <i>Binary Search Tree</i>, BST) – dynamiczna <a href="/wiki/Struktura_danych" title="Struktura danych">struktura danych</a> będąca <a href="/wiki/Drzewo_binarne" title="Drzewo binarne">drzewem binarnym</a>, w którym lewe poddrzewo każdego węzła zawiera wyłącznie elementy o kluczach mniejszych niż klucz węzła, a prawe poddrzewo zawiera wyłącznie elementy o kluczach nie mniejszych niż klucz węzła. Węzły, oprócz klucza, przechowują wskaźniki na swojego lewego i prawego syna oraz na swojego ojca. </p><p>Koszt wykonania podstawowych operacji w drzewie BST (wstawienie, wyszukanie, usunięcie węzła) jest proporcjonalny do wysokości drzewa <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>h</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b8c92993ef69282ac39ddc98b7150dabfae40c14" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.986ex; height:2.509ex;" alt="{\displaystyle h,}"></span> ponieważ operacje wykonywane są wzdłuż drzewa. Fakt ten w <a href="/wiki/Asymptotyczne_tempo_wzrostu" title="Asymptotyczne tempo wzrostu">notacji Landaua</a> zapisuje się <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {O} (h).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">O</mi> </mrow> <mo stretchy="false">(</mo> <mi>h</mi> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {O} (h).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/21467c8f6eb379d69c202ecdca0549ba7c6a8b14" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.603ex; height:2.843ex;" alt="{\displaystyle \mathrm {O} (h).}"></span> Jeżeli drzewo jest zrównoważone, to jego wysokość bliska jest logarytmowi dwójkowemu liczby węzłów <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (h\approx \log _{2}(n)),}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>h</mi> <mo>≈</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (h\approx \log _{2}(n)),}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/480350fc109339b3fac177d4d254a83291ce93f8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.124ex; height:2.843ex;" alt="{\displaystyle (h\approx \log _{2}(n)),}"></span> zatem dla drzewa o <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> węzłach optymistyczny koszt każdej z podstawowych operacji wynosi <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {O} (\log n).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">O</mi> </mrow> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {O} (\log n).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b358339fa85815c51155f8143af52148d0d86ab5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.018ex; height:2.843ex;" alt="{\displaystyle \mathrm {O} (\log n).}"></span> Z drugiej strony drzewo skrajnie niezrównoważone ma wysokość porównywalną z liczbą węzłów (w skrajnym przypadku drzewa zdegenerowanego do listy wartości te są równe: <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h=n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>h</mi> <mo>=</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h=n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ca144ffa4c586c3cfac786662f905fd70fe9e103" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.832ex; height:2.176ex;" alt="{\displaystyle h=n}"></span>), z tego powodu koszt pesymistyczny wzrasta do <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {O} (n).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">O</mi> </mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {O} (n).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dfc27ae307d4b9e117a3a585dcd12f753740c6b2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.659ex; height:2.843ex;" alt="{\displaystyle \mathrm {O} (n).}"></span> </p><p>Przechodząc drzewo metodą <a href="/wiki/Przechodzenie_drzewa" title="Przechodzenie drzewa">in-order</a>, uzyskuje się ciąg wartości kluczy posortowanych niemalejąco<sup id="cite_ref-Cormen1_1-0" class="reference"><a href="#cite_note-Cormen1-1">[1]</a></sup>. </p><p>Binarne drzewa wyszukiwań często stosuje się w zadaniach, w których wymagane jest względnie szybkie <a href="/wiki/Sortowanie" title="Sortowanie">sortowanie</a> lub wyszukiwanie elementów, na przykład różnego rodzaju słowniki, kolejki priorytetowe<sup id="cite_ref-Cormen1_1-1" class="reference"><a href="#cite_note-Cormen1-1">[1]</a></sup>. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Operacje_wykonywane_na_drzewie">Operacje wykonywane na drzewie</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit&section=1" title="Edytuj sekcję: Operacje wykonywane na drzewie" class="mw-editsection-visualeditor"><span>edytuj</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit&section=1" title="Edytuj kod źródłowy sekcji: Operacje wykonywane na drzewie"><span>edytuj kod</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Operacje_wyszukiwania">Operacje wyszukiwania</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit&section=2" title="Edytuj sekcję: Operacje wyszukiwania" class="mw-editsection-visualeditor"><span>edytuj</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit&section=2" title="Edytuj kod źródłowy sekcji: Operacje wyszukiwania"><span>edytuj kod</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading4"><h4 id="Wyszukiwanie_dowolnego_klucza_w_drzewie">Wyszukiwanie dowolnego klucza w drzewie</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit&section=3" title="Edytuj sekcję: Wyszukiwanie dowolnego klucza w drzewie" class="mw-editsection-visualeditor"><span>edytuj</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit&section=3" title="Edytuj kod źródłowy sekcji: Wyszukiwanie dowolnego klucza w drzewie"><span>edytuj kod</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Thumb"><a href="/wiki/Plik:Binary_search_tree_search_4.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/9/92/Binary_search_tree_search_4.svg/250px-Binary_search_tree_search_4.svg.png" decoding="async" width="250" height="211" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/92/Binary_search_tree_search_4.svg/375px-Binary_search_tree_search_4.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/92/Binary_search_tree_search_4.svg/500px-Binary_search_tree_search_4.svg.png 2x" data-file-width="320" data-file-height="270" /></a><figcaption>Wyszukiwanie klucza o wartości 4 w binarnym drzewie wyszkukiwań</figcaption></figure> <p>Jedną z podstawowych operacji jaką można wykonać działając na drzewie BST jest operacja wyszukiwania. </p><p>Wyszukiwanie elementu w drzewie rozpoczynane jest poprzez wywołanie procedury BST_TREE_SEARCH ze wskaźnikiem na korzeń drzewa oraz wartością poszukiwanego klucza jako jej parametrami. Następnie klucz każdego napotkanego węzła jest porównywany z poszukiwanym kluczem: jeżeli obie wartości są równe, to zwracany jest adres węzła ze znalezionym kluczem; jeżeli wartość poszukiwanego klucza jest mniejsza niż wartość klucza w porównywanym węźle to dalsze poszukiwania prowadzone są tylko w lewym poddrzewie; analogicznie, jeżeli wartość poszukiwanego klucza jest większa niż wartość klucza w porównywanym węźle to dalsze poszukiwania prowadzone są tylko w prawym poddrzewie<sup id="cite_ref-Cormen1_1-2" class="reference"><a href="#cite_note-Cormen1-1">[1]</a></sup>. </p><p>Rekurencyjny algorytm wyszukiwania wygląda następująco: </p> <div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre><span></span><span class="n">define</span><span class="w"> </span><span class="n">BST_TREE_SEARCH</span><span class="w"> </span><span class="p">(</span><span class="n">Node</span><span class="p">,</span><span class="w"> </span><span class="n">Key</span><span class="p">)</span><span class="o">:</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">Node</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="nb">NULL</span><span class="p">)</span><span class="w"> </span><span class="k">or</span><span class="w"> </span><span class="p">(</span><span class="n">Node</span><span class="o">-></span><span class="n">Key</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="n">Key</span><span class="p">)</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">Node</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">Key</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="n">Node</span><span class="o">-></span><span class="n">Key</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">BST_TREE_SEARCH</span><span class="w"> </span><span class="p">(</span><span class="n">Node</span><span class="o">-></span><span class="n">Left</span><span class="p">,</span><span class="w"> </span><span class="n">Key</span><span class="p">)</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">BST_TREE_SEARCH</span><span class="w"> </span><span class="p">(</span><span class="n">Node</span><span class="o">-></span><span class="n">Right</span><span class="p">,</span><span class="w"> </span><span class="n">Key</span><span class="p">)</span> </pre></div> <p>Istnieje także efektywniejszy algorytm przeszukiwania drzewa – <a href="/wiki/Algorytm_iteracyjny" title="Algorytm iteracyjny">algorytm iteracyjny</a>. Przedstawia się on następująco: </p> <div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre><span></span><span class="n">define</span><span class="w"> </span><span class="n">ITERATIVE_BST_TREE_SEARCH</span><span class="w"> </span><span class="p">(</span><span class="n">Node</span><span class="p">,</span><span class="w"> </span><span class="n">Key</span><span class="p">)</span><span class="o">:</span> <span class="w"> </span><span class="k">while</span><span class="w"> </span><span class="p">((</span><span class="n">Node</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="nb">NULL</span><span class="p">)</span><span class="w"> </span><span class="k">and</span><span class="w"> </span><span class="p">(</span><span class="n">Node</span><span class="o">-></span><span class="n">Key</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="n">Key</span><span class="p">))</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">Key</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="n">Node</span><span class="o">-></span><span class="n">Key</span><span class="p">)</span> <span class="w"> </span><span class="n">Node</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Node</span><span class="o">-></span><span class="n">left</span> <span class="w"> </span><span class="k">else</span> <span class="w"> </span><span class="n">Node</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Node</span><span class="o">-></span><span class="n">right</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">Node</span> </pre></div> <p>Podobnie jak w przypadku algorytmu rekurencyjnego, także tutaj procedura wywoływana jest z parametrami będącymi wskaźnikiem na korzeń drzewa oraz wartością wyszukiwanego klucza. Także tutaj poruszamy się w dół drzewa, jednak zamiast wywołań rekurencyjnych stosujemy przypisanie adresu odpowiedniego syna węzła do zmiennej Node<sup id="cite_ref-Cormen1_1-3" class="reference"><a href="#cite_note-Cormen1-1">[1]</a></sup>. </p> <div class="mw-heading mw-heading4"><h4 id="Wyszukiwanie_najmniejszego_i_największego_klucza_w_drzewie"><span id="Wyszukiwanie_najmniejszego_i_najwi.C4.99kszego_klucza_w_drzewie"></span>Wyszukiwanie najmniejszego i największego klucza w drzewie</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit&section=4" title="Edytuj sekcję: Wyszukiwanie najmniejszego i największego klucza w drzewie" class="mw-editsection-visualeditor"><span>edytuj</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit&section=4" title="Edytuj kod źródłowy sekcji: Wyszukiwanie najmniejszego i największego klucza w drzewie"><span>edytuj kod</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Aby wyszukać w drzewie klucz o najmniejszej wartości, wystarczy kierować się w lewy, skrajny dół drzewa. Ostatni napotkany element, niebędący węzłem pustym, jest węzłem zawierającym najmniejszy klucz. Algorytm iteracyjny jest następujący<sup id="cite_ref-Cormen1_1-4" class="reference"><a href="#cite_note-Cormen1-1">[1]</a></sup>: </p> <div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre><span></span><span class="n">define</span><span class="w"> </span><span class="n">BST_SEARCH_MIN_KEY</span><span class="p">(</span><span class="n">Node</span><span class="p">)</span><span class="o">:</span> <span class="w"> </span><span class="k">while</span><span class="w"> </span><span class="p">(</span><span class="n">Node</span><span class="o">-></span><span class="n">left</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="nb">NULL</span><span class="p">)</span> <span class="w"> </span><span class="n">Node</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Node</span><span class="o">-></span><span class="n">left</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">Node</span> </pre></div> <p>Analogicznie, aby znaleźć węzeł z największym kluczem w drzewie należy skierować się w prawy, skrajny dół drzewa<sup id="cite_ref-Cormen1_1-5" class="reference"><a href="#cite_note-Cormen1-1">[1]</a></sup>. </p> <div class="mw-heading mw-heading4"><h4 id="Wyszukiwanie_następnika_i_poprzednika_w_drzewie"><span id="Wyszukiwanie_nast.C4.99pnika_i_poprzednika_w_drzewie"></span>Wyszukiwanie następnika i poprzednika w drzewie</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit&section=5" title="Edytuj sekcję: Wyszukiwanie następnika i poprzednika w drzewie" class="mw-editsection-visualeditor"><span>edytuj</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit&section=5" title="Edytuj kod źródłowy sekcji: Wyszukiwanie następnika i poprzednika w drzewie"><span>edytuj kod</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Następnik danego węzła jest węzłem, który jest odwiedzany jako następny w przypadku <a href="/wiki/Przechodzenie_drzewa" title="Przechodzenie drzewa">przechodzenia drzewa metodą in-order</a>. W drzewie BST w celu wyznaczenia następnika węzła nie trzeba przeprowadzać żadnych porównań kluczy. Podczas wyszukiwania mogą zaistnieć dwie sytuacje<sup id="cite_ref-Cormen1_1-6" class="reference"><a href="#cite_note-Cormen1-1">[1]</a></sup><sup id="cite_ref-Lecture1_2-0" class="reference"><a href="#cite_note-Lecture1-2">[2]</a></sup>: </p> <ul><li>istnieje prawe poddrzewo węzła odniesienia – wtedy znalezienie jego następnika ogranicza się do znalezienia najmniejszego klucza w tym poddrzewie,</li> <li>nie istnieje prawe poddrzewo węzła odniesienia – wtedy następnikiem jest węzeł będący najniższym (w sensie wysokości w drzewie) przodkiem węzła odniesienia, dla którego węzeł odniesienia leży w lewym poddrzewie.</li></ul> <p>Algorytm wyznaczania następnika jest następujący<sup id="cite_ref-Cormen1_1-7" class="reference"><a href="#cite_note-Cormen1-1">[1]</a></sup><sup id="cite_ref-Lecture1_2-1" class="reference"><a href="#cite_note-Lecture1-2">[2]</a></sup>: </p> <div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre><span></span><span class="n">define</span><span class="w"> </span><span class="n">BST_FIND_SUCCESSOR</span><span class="p">(</span><span class="n">Node</span><span class="p">)</span><span class="o">:</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">Node</span><span class="o">-></span><span class="n">right</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="nb">NULL</span><span class="p">)</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">BST_SEARCH_MIN_KEY</span><span class="p">(</span><span class="n">Node</span><span class="o">-></span><span class="n">right</span><span class="p">)</span> <span class="w"> </span><span class="n">Node_tmp</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Node</span><span class="o">-></span><span class="n">parent</span> <span class="w"> </span><span class="k">while</span><span class="w"> </span><span class="p">(</span><span class="n">Node_tmp</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="nb">NULL</span><span class="w"> </span><span class="k">and</span><span class="w"> </span><span class="n">Node_tmp</span><span class="o">-></span><span class="n">left</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="n">Node</span><span class="p">)</span> <span class="w"> </span><span class="n">Node</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Node_tmp</span> <span class="w"> </span><span class="n">Node_tmp</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Node_tmp</span><span class="o">-></span><span class="n">parent</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">Node_tmp</span> </pre></div> <p>Analogicznie przebiega wyszukiwanie poprzednika: </p> <div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre><span></span><span class="n">define</span><span class="w"> </span><span class="n">BST_FIND_PREDECESSOR</span><span class="p">(</span><span class="n">Node</span><span class="p">)</span><span class="o">:</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">Node</span><span class="o">-></span><span class="n">left</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="nb">NULL</span><span class="p">)</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">BST_SEARCH_MAX_KEY</span><span class="p">(</span><span class="n">Node</span><span class="o">-></span><span class="n">left</span><span class="p">)</span> <span class="w"> </span><span class="n">Node_tmp</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Node</span><span class="o">-></span><span class="n">parent</span> <span class="w"> </span><span class="k">while</span><span class="w"> </span><span class="p">(</span><span class="n">Node_tmp</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="nb">NULL</span><span class="w"> </span><span class="k">and</span><span class="w"> </span><span class="n">Node_tmp</span><span class="o">-></span><span class="n">right</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="n">Node</span><span class="p">)</span> <span class="w"> </span><span class="n">Node</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Node_tmp</span> <span class="w"> </span><span class="n">Node_tmp</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Node_tmp</span><span class="o">-></span><span class="n">parent</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">Node_tmp</span> </pre></div> <p>Podobnie jak w poprzednim przypadku wyszukiwanie rozpoczynamy od wywołania procedury BST_FIND_PREDECESSOR z adresem węzła, którego poprzednik chcemy znaleźć. Podczas przeszukiwania mogą zaistnieć dwie sytuacje<sup id="cite_ref-Cormen1_1-8" class="reference"><a href="#cite_note-Cormen1-1">[1]</a></sup><sup id="cite_ref-Lecture1_2-2" class="reference"><a href="#cite_note-Lecture1-2">[2]</a></sup>: </p> <ul><li>istnieje lewe poddrzewo danego węzła – wtedy znalezienie jego poprzednika ogranicza się do znalezienia największego klucza w tym poddrzewie</li> <li>nie istnieje lewe poddrzewo danego węzła – wtedy poprzednikiem jest węzeł będący jednocześnie najniższym przodkiem węzła (którego chcemy znaleźć) oraz mającym prawego syna, który także jest przodkiem danego węzła.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Wstawianie_klucza">Wstawianie klucza</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit&section=6" title="Edytuj sekcję: Wstawianie klucza" class="mw-editsection-visualeditor"><span>edytuj</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit&section=6" title="Edytuj kod źródłowy sekcji: Wstawianie klucza"><span>edytuj kod</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Nowe elementy wstawiane są jako liście w odpowiednim miejscu. Do procedury przekazujemy jako argument węzeł <code>InsertNode</code>, w którym <code>InsertNode->Left == NULL</code>, <code>InsertNode->Right == NULL</code> oraz <code>InsertNode->Key != NULL</code>. Algorytm wstawiania węzła do drzewa jest bardzo podobny do algorytmu wyszukiwania węzła w drzewie i wygląda następująco<sup id="cite_ref-Cormen1_1-9" class="reference"><a href="#cite_note-Cormen1-1">[1]</a></sup>: </p> <div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre><span></span><span class="n">define</span><span class="w"> </span><span class="n">BST_TREE_INSERT_NODE</span><span class="p">(</span><span class="n">Tree</span><span class="p">,</span><span class="w"> </span><span class="n">InsertNode</span><span class="p">)</span> <span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nb">NULL</span> <span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Tree</span><span class="o">-></span><span class="n">Root</span> <span class="w"> </span><span class="k">while</span><span class="w"> </span><span class="p">(</span><span class="n">x</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="nb">NULL</span><span class="p">)</span> <span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">x</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">InsertNode</span><span class="o">-></span><span class="n">Key</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="n">x</span><span class="o">-></span><span class="n">Key</span><span class="p">)</span> <span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">x</span><span class="o">-></span><span class="n">left</span> <span class="w"> </span><span class="k">else</span> <span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">x</span><span class="o">-></span><span class="n">right</span> <span class="w"> </span><span class="n">InsertNode</span><span class="o">-></span><span class="n">Parent</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">y</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">y</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="nb">NULL</span><span class="p">)</span><span class="w"> </span><span class="c1">//drzewo jest puste</span> <span class="w"> </span><span class="n">Tree</span><span class="o">-></span><span class="n">Root</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">InsertNode</span> <span class="w"> </span><span class="k">else</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">InsertNode</span><span class="o">-></span><span class="n">Key</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="n">y</span><span class="o">-></span><span class="n">key</span><span class="p">)</span> <span class="w"> </span><span class="n">y</span><span class="o">-></span><span class="n">Left</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">InsertNode</span> <span class="w"> </span><span class="k">else</span> <span class="w"> </span><span class="n">y</span><span class="o">-></span><span class="n">Right</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">InsertNode</span> </pre></div> <p>Wstawianie rozpoczyna się przeglądaniem węzła od korzenia w celu znalezienia miejsca przyłączenia wstawianego węzła. </p> <div class="mw-heading mw-heading3"><h3 id="Usuwanie_klucza">Usuwanie klucza</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit&section=7" title="Edytuj sekcję: Usuwanie klucza" class="mw-editsection-visualeditor"><span>edytuj</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit&section=7" title="Edytuj kod źródłowy sekcji: Usuwanie klucza"><span>edytuj kod</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Usuwanie węzła jest procedurą bardziej skomplikowaną niż jego wstawianie. Podczas wykonywania procedury należy rozważyć trzy przypadki<sup id="cite_ref-Cormen1_1-10" class="reference"><a href="#cite_note-Cormen1-1">[1]</a></sup>: </p> <ul><li>w przypadku, gdy usuwany węzeł nie ma synów (jest liściem) usunięcie przebiega bez reorganizacji drzewa – wskaźnik do węzła w jego ojcu zastępowany jest wskaźnikiem do węzła pustego</li> <li>w przypadku, gdy usuwany węzeł ma jednego syna to dany węzeł usuwamy a jego syna podstawiamy w miejsce usuniętego węzła</li> <li>w przypadku, gdy usuwany węzeł ma dwóch synów to po jego usunięciu wstawiamy w jego miejsce węzeł, który jest jego następnikiem (który nie ma lewego syna).</li></ul> <ul class="gallery mw-gallery-traditional" style="max-width: 586px;"> <li class="gallerybox" style="width: 285px"> <div class="thumb" style="width: 280px; height: 150px;"><span typeof="mw:File"><a href="/wiki/Plik:Binary_search_tree_delete_13.svg" class="mw-file-description" title="Usuwanie węzła, który jest liściem"><img alt="Usuwanie węzła, który jest liściem" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1d/Binary_search_tree_delete_13.svg/250px-Binary_search_tree_delete_13.svg.png" decoding="async" width="250" height="101" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1d/Binary_search_tree_delete_13.svg/375px-Binary_search_tree_delete_13.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1d/Binary_search_tree_delete_13.svg/500px-Binary_search_tree_delete_13.svg.png 2x" data-file-width="620" data-file-height="250" /></a></span></div> <div class="gallerytext"> Usuwanie węzła, który jest liściem</div> </li> <li class="gallerybox" style="width: 285px"> <div class="thumb" style="width: 280px; height: 150px;"><span typeof="mw:File"><a href="/wiki/Plik:Binary_search_tree_delete_14.svg" class="mw-file-description" title="Usuwanie węzła z jednym synem"><img alt="Usuwanie węzła z jednym synem" src="//upload.wikimedia.org/wikipedia/commons/thumb/0/08/Binary_search_tree_delete_14.svg/250px-Binary_search_tree_delete_14.svg.png" decoding="async" width="250" height="101" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/0/08/Binary_search_tree_delete_14.svg/375px-Binary_search_tree_delete_14.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/0/08/Binary_search_tree_delete_14.svg/500px-Binary_search_tree_delete_14.svg.png 2x" data-file-width="620" data-file-height="250" /></a></span></div> <div class="gallerytext"> Usuwanie węzła z jednym synem</div> </li> <li class="gallerybox" style="width: 285px"> <div class="thumb" style="width: 280px; height: 150px;"><span typeof="mw:File"><a href="/wiki/Plik:Binary_search_tree_delete_3.svg" class="mw-file-description" title="Usuwanie węzła z kluczem 3 z dwoma synami. Następnikiem węzła jest węzeł z kluczem 4"><img alt="Usuwanie węzła z kluczem 3 z dwoma synami. Następnikiem węzła jest węzeł z kluczem 4" src="//upload.wikimedia.org/wikipedia/commons/thumb/2/2b/Binary_search_tree_delete_3.svg/250px-Binary_search_tree_delete_3.svg.png" decoding="async" width="250" height="105" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/2/2b/Binary_search_tree_delete_3.svg/375px-Binary_search_tree_delete_3.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/2/2b/Binary_search_tree_delete_3.svg/500px-Binary_search_tree_delete_3.svg.png 2x" data-file-width="620" data-file-height="260" /></a></span></div> <div class="gallerytext"> Usuwanie węzła z kluczem 3 z dwoma synami. Następnikiem węzła jest węzeł z kluczem 4</div> </li> <li class="gallerybox" style="width: 285px"> <div class="thumb" style="width: 280px; height: 150px;"><span typeof="mw:File"><a href="/wiki/Plik:Binary_search_tree_delete_8.svg" class="mw-file-description" title="Usuwanie węzła z kluczem 8 z dwoma synami. Następnikiem węzła jest węzeł z kluczem 10"><img alt="Usuwanie węzła z kluczem 8 z dwoma synami. Następnikiem węzła jest węzeł z kluczem 10" src="//upload.wikimedia.org/wikipedia/commons/thumb/b/b3/Binary_search_tree_delete_8.svg/250px-Binary_search_tree_delete_8.svg.png" decoding="async" width="250" height="105" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/b/b3/Binary_search_tree_delete_8.svg/375px-Binary_search_tree_delete_8.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/b/b3/Binary_search_tree_delete_8.svg/500px-Binary_search_tree_delete_8.svg.png 2x" data-file-width="620" data-file-height="260" /></a></span></div> <div class="gallerytext"> Usuwanie węzła z kluczem 8 z dwoma synami. Następnikiem węzła jest węzeł z kluczem 10</div> </li> </ul> <div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre><span></span><span class="n">define</span><span class="w"> </span><span class="n">BST_TREE_DELETE</span><span class="w"> </span><span class="p">(</span><span class="n">Tree</span><span class="p">,</span><span class="w"> </span><span class="n">DeleteNode</span><span class="p">)</span><span class="o">:</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">DeleteNode</span><span class="o">-></span><span class="n">Left</span><span class="o">==</span><span class="nb">NULL</span><span class="p">)</span><span class="w"> </span><span class="k">or</span><span class="w"> </span><span class="p">(</span><span class="n">DeleteNode</span><span class="o">-></span><span class="n">Right</span><span class="o">==</span><span class="nb">NULL</span><span class="p">)</span> <span class="w"> </span><span class="n">y</span><span class="o">=</span><span class="n">DeleteNode</span> <span class="w"> </span><span class="k">else</span> <span class="w"> </span><span class="n">y</span><span class="o">=</span><span class="n">BST_FIND_SUCCESSOR</span><span class="p">(</span><span class="n">DeleteNode</span><span class="p">)</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">y</span><span class="o">-></span><span class="n">Left</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="nb">NULL</span><span class="p">)</span> <span class="w"> </span><span class="n">x</span><span class="o">=</span><span class="n">y</span><span class="o">-></span><span class="n">Left</span> <span class="w"> </span><span class="k">else</span> <span class="w"> </span><span class="n">x</span><span class="o">=</span><span class="n">y</span><span class="o">-></span><span class="n">Right</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">x</span><span class="o">!=</span><span class="nb">NULL</span><span class="p">)</span> <span class="w"> </span><span class="n">x</span><span class="o">-></span><span class="n">parent</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">y</span><span class="o">-></span><span class="n">parent</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">y</span><span class="o">-></span><span class="n">parent</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="nb">NULL</span><span class="p">)</span> <span class="w"> </span><span class="n">Tree</span><span class="o">-></span><span class="n">root</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">x</span> <span class="w"> </span><span class="k">else</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">y</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="n">y</span><span class="o">-></span><span class="n">parent</span><span class="o">-></span><span class="n">Left</span><span class="p">)</span> <span class="w"> </span><span class="n">y</span><span class="o">-></span><span class="n">parent</span><span class="o">-></span><span class="n">Left</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">x</span> <span class="w"> </span><span class="k">else</span> <span class="w"> </span><span class="n">y</span><span class="o">-></span><span class="n">parent</span><span class="o">-></span><span class="n">Right</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">x</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">y</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="n">DeleteNode</span><span class="p">)</span> <span class="w"> </span><span class="n">DeleteNode</span><span class="o">-></span><span class="n">Key</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">y</span><span class="o">-></span><span class="n">Key</span> <span class="w"> </span><span class="c1">// Jeśli y ma inne pola, to je także należy skopiować</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">y</span> </pre></div> <div class="mw-heading mw-heading2"><h2 id="Wyważanie_drzewa"><span id="Wywa.C5.BCanie_drzewa"></span>Wyważanie drzewa</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit&section=8" title="Edytuj sekcję: Wyważanie drzewa" class="mw-editsection-visualeditor"><span>edytuj</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit&section=8" title="Edytuj kod źródłowy sekcji: Wyważanie drzewa"><span>edytuj kod</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Thumb"><a href="/wiki/Plik:Unbalanced_binary_tree.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Unbalanced_binary_tree.svg/294px-Unbalanced_binary_tree.svg.png" decoding="async" width="294" height="294" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Unbalanced_binary_tree.svg/441px-Unbalanced_binary_tree.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Unbalanced_binary_tree.svg/588px-Unbalanced_binary_tree.svg.png 2x" data-file-width="800" data-file-height="800" /></a><figcaption>Drzewo niezrównoważone (np. lewe poddrzewo węzła 76 ma wysokość 3, a prawe 0)</figcaption></figure> <p>Średni czas wykonywania operacji na drzewach poszukiwań binarnych zależy od średniej wysokości drzewa. Podobnie pesymistyczny czas wykonania operacji zależy od wysokości drzewa (tj. długości najdłuższej ścieżki od korzenia do liści). Najlepiej, gdy wynosi ona w przybliżeniu <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}n,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mi>n</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \log _{2}n,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c62bffdfdf8fbe51d0daac1466dbd6f908a7b336" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.455ex; height:2.676ex;" alt="{\displaystyle \log _{2}n,}"></span> gdzie <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> to liczba węzłów w drzewie. Powoduje to że zarówno w lewym i prawym poddrzewie jest mniej więcej tyle samo węzłów, a tym samym dojście do każdego liścia zajmuje mniej więcej tyle samo kroków. Jest tak w przypadku, gdy drzewo jest <b>zrównoważone</b>, wówczas różnica wysokości lewego i prawego poddrzewa każdego z węzłów wynosi co najwyżej 1. Drzewo jest <b>doskonale zrównoważone</b>, gdy liczby elementów prawego i lewego poddrzewa każdego węzła różnią się najwyżej o jeden. </p><p>Powszechnie używane struktury gwarantujące zrównoważenie to <a href="/wiki/Drzewo_AVL" title="Drzewo AVL">drzewa AVL</a> i <a href="/wiki/Drzewo_czerwono-czarne" title="Drzewo czerwono-czarne">drzewa czerwono-czarne</a>. Posiadają one bardziej skomplikowane reguły wstawiania i usuwania, jak również przechowują dodatkowe wartości pomocnicze w węzłach drzewa. </p><p>Wyważone drzewo można łatwo zbudować na bazie posortowanej <a href="/wiki/Tablica_(informatyka)" title="Tablica (informatyka)">tablicy</a>, algorytmem analogicznym do <a href="/wiki/Wyszukiwanie_binarne" title="Wyszukiwanie binarne">wyszukiwania binarnego</a>. Jednak to podejście jest nie najlepsze jeśli drzewo już istnieje – wymaga bowiem skopiowania wszystkich danych do dodatkowej pamięci i całkowitej przebudowy drzewa. Lepszym rozwiązaniem jest użycie <a href="/wiki/Algorytm_DSW" title="Algorytm DSW">algorytmu DSW</a>, który równoważy drzewo BST poprzez szereg <a href="/wiki/Rotacja_drzewa" title="Rotacja drzewa">rotacji</a>, co nie wymaga ani sortowania, ani dodatkowej pamięci. <br style="clear:both;" /> </p> <table class="infobox noprint plainlinks" cellpadding="4" role="presentation"> <tbody><tr> <td style="vertical-align:middle; text-align:center; width:30px;"><span class="notpageimage" typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/f/fa/Wikibooks-logo.svg/28px-Wikibooks-logo.svg.png" decoding="async" width="28" height="28" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/f/fa/Wikibooks-logo.svg/42px-Wikibooks-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/f/fa/Wikibooks-logo.svg/56px-Wikibooks-logo.svg.png 2x" data-file-width="300" data-file-height="300" /></span></span> </td> <td style="line-height:normal; vertical-align:middle; text-align:center; flex:unset;">Zobacz publikację<br /><b><a href="https://pl.wikibooks.org/wiki/Kody_%C5%BAr%C3%B3d%C5%82owe/Binarne_drzewo_poszukiwa%C5%84" class="extiw" title="b:Kody źródłowe/Binarne drzewo poszukiwań">Kody_źródłowe/Binarne_drzewo_poszukiwań</a></b> w Wikibooks </td></tr></tbody></table> <div class="mw-heading mw-heading2"><h2 id="Optymalne_drzewo_poszukiwań"><span id="Optymalne_drzewo_poszukiwa.C5.84"></span>Optymalne drzewo poszukiwań</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit&section=9" title="Edytuj sekcję: Optymalne drzewo poszukiwań" class="mw-editsection-visualeditor"><span>edytuj</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit&section=9" title="Edytuj kod źródłowy sekcji: Optymalne drzewo poszukiwań"><span>edytuj kod</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="noprint relarticle mainarticle" style="margin:0.2em 0 0.5em 1.6em"><span class="nomobile navigation-not-searchable"><span class="notpageimage" typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Wiki_letter_w.svg/20px-Wiki_letter_w.svg.png" decoding="async" width="20" height="20" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Wiki_letter_w.svg/30px-Wiki_letter_w.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Wiki_letter_w.svg/40px-Wiki_letter_w.svg.png 2x" data-file-width="44" data-file-height="44" /></span></span> </span><i>Ta sekcja jest niekompletna. Jeśli możesz, <span class="plainlinks"><a class="external text" href="https://pl.wikipedia.org/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit">rozbuduj ją</a></span>.</i></div> <p>Jeśli wiadomo, że dane w drzewie nie będą zmieniane, a ponadto znane są prawdopodobieństwa (częstotliwości) dostępu do poszczególnych kluczy, można utworzyć optymalne BST, w którym <b>oczekiwany czas wyszukiwania</b> będzie minimalny. Przy konstrukcji drzewa optymalnego bierze się pod uwagę dwa czynniki: prawdopodobieństwo wyszukiwania zakończonego powodzeniem (klucz jest w drzewie) oraz niepowodzeniem (klucza nie ma w drzewie). </p><p>Algorytm tworzący optymalne BST opiera swoje działanie na <a href="/wiki/Programowanie_dynamiczne" title="Programowanie dynamiczne">programowaniu dynamicznym</a> i charakteryzuje się złożonością czasową <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {O} (n^{3})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">O</mi> </mrow> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {O} (n^{3})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/322cb97cebd9acca1440e8e9b2ab8bd69bd981ef" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \mathrm {O} (n^{3})}"></span> lub przy niewielkich modyfikacjach pokazanych przez Knutha – <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {O} (n^{2});}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">O</mi> </mrow> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> <mo>;</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {O} (n^{2});}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cb712da7acd61e537db2b6398cf393e05c8ca233" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.713ex; height:3.176ex;" alt="{\displaystyle \mathrm {O} (n^{2});}"></span> złożoność pamięciowa wynosi <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {O} (n^{2}).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">O</mi> </mrow> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {O} (n^{2}).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5bcb4f4ebcd5b1bbc8bd18a10c7d216967cf5d06" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.713ex; height:3.176ex;" alt="{\displaystyle \mathrm {O} (n^{2}).}"></span> Knuth pokazuje także metody przybliżone, o mniejszej złożoności czasowej, które dają BST gorsze o 2–5% od optymalnego rozwiązania. </p><p>W przypadku nieznanej statystyki dostępu do kluczy można stosować <a href="/wiki/Drzewo_splay" title="Drzewo splay">drzewa samoorganizujące się</a>, które na bieżąco korygują położenie kluczy w drzewie. </p> <div class="mw-heading mw-heading2"><h2 id="Zobacz_też"><span id="Zobacz_te.C5.BC"></span>Zobacz też</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit&section=10" title="Edytuj sekcję: Zobacz też" class="mw-editsection-visualeditor"><span>edytuj</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit&section=10" title="Edytuj kod źródłowy sekcji: Zobacz też"><span>edytuj kod</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Algorytm_DSW" title="Algorytm DSW">algorytm DSW</a></li> <li><a href="/wiki/Drzewo_AVL" title="Drzewo AVL">drzewo AVL</a></li> <li><a href="/wiki/Drzewo_czerwono-czarne" title="Drzewo czerwono-czarne">drzewo czerwono-czarne</a></li> <li><a href="/wiki/Drzewo_o_ograniczonym_zr%C3%B3wnowa%C5%BCeniu" title="Drzewo o ograniczonym zrównoważeniu">drzewo o ograniczonym zrównoważeniu</a></li> <li><a href="/wiki/Drzewo_splay" title="Drzewo splay">drzewo splay</a></li> <li><a href="/wiki/Przechodzenie_drzewa" title="Przechodzenie drzewa">przechodzenie drzewa</a></li> <li><a href="/wiki/Rotacja_drzewa" title="Rotacja drzewa">rotacja drzewa</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Przypisy">Przypisy</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit&section=11" title="Edytuj sekcję: Przypisy" class="mw-editsection-visualeditor"><span>edytuj</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit&section=11" title="Edytuj kod źródłowy sekcji: Przypisy"><span>edytuj kod</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="do-not-make-smaller refsection"><div class="mw-references-wrap"><ol class="references"> <li id="cite_note-Cormen1-1"><span class="mw-cite-backlink">↑ <sup><a href="#cite_ref-Cormen1_1-0">a</a></sup> <sup><a href="#cite_ref-Cormen1_1-1">b</a></sup> <sup><a href="#cite_ref-Cormen1_1-2">c</a></sup> <sup><a href="#cite_ref-Cormen1_1-3">d</a></sup> <sup><a href="#cite_ref-Cormen1_1-4">e</a></sup> <sup><a href="#cite_ref-Cormen1_1-5">f</a></sup> <sup><a href="#cite_ref-Cormen1_1-6">g</a></sup> <sup><a href="#cite_ref-Cormen1_1-7">h</a></sup> <sup><a href="#cite_ref-Cormen1_1-8">i</a></sup> <sup><a href="#cite_ref-Cormen1_1-9">j</a></sup> <sup><a href="#cite_ref-Cormen1_1-10">k</a></sup></span> <span class="reference-text"><cite class="citation book">Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: <i>Wprowadzenie do algorytmów</i>. Warszawa: <a href="/wiki/Wydawnictwa_Naukowo-Techniczne" title="Wydawnictwa Naukowo-Techniczne">Wydawnictwa Naukowo-Techniczne</a>, 2007, s. 253–272. <a href="/wiki/Specjalna:Ksi%C4%85%C5%BCki/9788320433289" title="Specjalna:Książki/9788320433289">ISBN <span class="isbn">978-83-204-3328-9</span></a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Wprowadzenie+do+algorytm%C3%B3w&rft.au=Thomas+H.+Cormen&rft.pub=%5B%5BWydawnictwa+Naukowo-Techniczne%5D%5D&rft.place=Warszawa&rft.pages=253%E2%80%93272&rft.isbn=978-83-204-3328-9"></span></cite></span> </li> <li id="cite_note-Lecture1-2"><span class="mw-cite-backlink">↑ <sup><a href="#cite_ref-Lecture1_2-0">a</a></sup> <sup><a href="#cite_ref-Lecture1_2-1">b</a></sup> <sup><a href="#cite_ref-Lecture1_2-2">c</a></sup></span> <span class="reference-text"><cite class="citation web">Thomas A. Anastasio: <a rel="nofollow" class="external text" href="http://faculty.salisbury.edu/~despickler/personal/Resources/AdvancedDataStructures/Handouts/succ_pred_rules.pdf">Successor/Predecessor Rules in Binary Search Trees</a>. 2003-07-07. [dostęp 2010-09-18]. <span class="lang-list">(<abbr title="Treść w języku angielskim (English)">ang.</abbr>)</span>.</cite></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="Linki_zewnętrzne"><span id="Linki_zewn.C4.99trzne"></span>Linki zewnętrzne</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&veaction=edit&section=12" title="Edytuj sekcję: Linki zewnętrzne" class="mw-editsection-visualeditor"><span>edytuj</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&action=edit&section=12" title="Edytuj kod źródłowy sekcji: Linki zewnętrzne"><span>edytuj kod</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="https://people.ksp.sk/~kuko/gnarley-trees/BST.html">Wizualizacja drzewa poszukiwań binarnych</a></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="">Źródło: „<a dir="ltr" href="https://pl.wikipedia.org/w/index.php?title=Binarne_drzewo_poszukiwań&oldid=69794177">https://pl.wikipedia.org/w/index.php?title=Binarne_drzewo_poszukiwań&oldid=69794177</a>”</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Specjalna:Kategorie" title="Specjalna:Kategorie">Kategoria</a>: <ul><li><a href="/wiki/Kategoria:Drzewa_(informatyka)" title="Kategoria:Drzewa (informatyka)">Drzewa (informatyka)</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Ukryta kategoria: <ul><li><a href="/wiki/Kategoria:Zal%C4%85%C5%BCki_sekcji_artyku%C5%82%C3%B3w" title="Kategoria:Zalążki sekcji artykułów">Zalążki sekcji artykułów</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"> Tę stronę ostatnio edytowano 6 mar 2023, 14:30.</li> <li id="footer-info-copyright">Tekst udostępniany na licencji <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.pl">Creative Commons: uznanie autorstwa, na tych samych warunkach</a>, z możliwością obowiązywania dodatkowych ograniczeń. Zobacz szczegółowe informacje o <a class="external text" href="https://foundation.wikimedia.org/wiki/Policy:Terms_of_Use/pl">warunkach korzystania</a>.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Polityka prywatności</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:O_Wikipedii">O Wikipedii</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:Korzystasz_z_Wikipedii_tylko_na_w%C5%82asn%C4%85_odpowiedzialno%C5%9B%C4%87">Korzystasz z Wikipedii tylko na własną odpowiedzialność</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Powszechne Zasady Postępowania</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Dla deweloperów</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/pl.wikipedia.org">Statystyki</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Oświadczenie o ciasteczkach</a></li> <li id="footer-places-mobileview"><a href="//pl.m.wikipedia.org/w/index.php?title=Binarne_drzewo_poszukiwa%C5%84&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Wersja mobilna</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-f2r5r","wgBackendResponseTime":184,"wgPageParseReport":{"limitreport":{"cputime":"0.197","walltime":"0.385","ppvisitednodes":{"value":1258,"limit":1000000},"postexpandincludesize":{"value":6791,"limit":2097152},"templateargumentsize":{"value":1919,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":8,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":26888,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 122.394 1 -total"," 64.84% 79.361 1 Szablon:Przypisy"," 27.71% 33.921 1 Szablon:Cytuj_stronę"," 26.51% 32.446 1 Szablon:Cytuj_książkę"," 26.15% 32.003 1 Szablon:Wikibooks"," 22.56% 27.608 1 Szablon:Projekt_siostrzany"," 20.28% 24.821 2 Szablon:Ikona"," 12.96% 15.860 2 Szablon:Lang"," 6.48% 7.937 1 Szablon:Sekcja_stub"," 2.81% 3.445 1 Szablon:Dmbox"]},"scribunto":{"limitreport-timeusage":{"value":"0.035","limit":"10.000"},"limitreport-memusage":{"value":2093243,"limit":52428800},"limitreport-logs":"required = table#1 {\n}\nrequired = table#1 {\n}\n"},"cachereport":{"origin":"mw-web.eqiad.main-8f644c877-6tlcv","timestamp":"20241106072412","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Binarne drzewo poszukiwa\u0144","url":"https:\/\/pl.wikipedia.org\/wiki\/Binarne_drzewo_poszukiwa%C5%84","sameAs":"http:\/\/www.wikidata.org\/entity\/Q623818","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q623818","author":{"@type":"Organization","name":"Wsp\u00f3\u0142tw\u00f3rcy projekt\u00f3w Fundacji Wikimedia"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-06-09T17:37:21Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/d\/da\/Binary_search_tree.svg"}</script> </body> </html>