CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="vi" dir="ltr"> <head> <meta charset="UTF-8"> <title>Cây tìm kiếm nhị phân – Wikipedia tiếng Việt</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )viwikimwclientpreferences=([^;]+)/);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": "vi normal","wgMonthNames":["","tháng 1","tháng 2","tháng 3","tháng 4","tháng 5","tháng 6","tháng 7","tháng 8","tháng 9","tháng 10","tháng 11","tháng 12"],"wgRequestId":"7485a240-9a89-452a-a4f9-a1e40a342c63","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Cây_tìm_kiếm_nhị_phân","wgTitle":"Cây tìm kiếm nhị phân","wgCurRevisionId":71839321,"wgRevisionId":71839321,"wgArticleId":61665,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Bản mẫu webarchive dùng liên kết wayback","Trang sử dụng liên kết tự động ISBN","Cây (cấu trúc)","Kiểu dữ liệu"],"wgPageViewLanguage":"vi","wgPageContentLanguage":"vi","wgPageContentModel":"wikitext","wgRelevantPageName":"Cây_tìm_kiếm_nhị_phân","wgRelevantArticleId":61665,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[], "wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"vi","pageLanguageDir":"ltr","pageVariantFallbacks":"vi"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"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.charinsert-styles":"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.pygments":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.pygments.view","mediawiki.page.media","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.did_you_mean","ext.gadget.ReferenceTooltips","ext.gadget.AVIM","ext.gadget.AVIM_portlet","ext.gadget.charinsert","ext.gadget.refToolbar","ext.gadget.wikibugs","ext.gadget.purgetab","ext.gadget.switcher","ext.gadget.AdvancedSiteNotices","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap", "ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=vi&modules=ext.math.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=vi&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=vi&modules=ext.gadget.charinsert-styles&only=styles&skin=vector-2022"> <link rel="stylesheet" href="/w/load.php?lang=vi&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.16"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Cây tìm kiếm nhị phân – Wikipedia tiếng Việt"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//vi.m.wikipedia.org/wiki/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n"> <link rel="alternate" type="application/x-wiki" title="Sửa đổi" href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&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 (vi)"> <link rel="EditURI" type="application/rsd+xml" href="//vi.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://vi.wikipedia.org/wiki/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.vi"> <link rel="alternate" type="application/atom+xml" title="Nguồn cấp Atom của Wikipedia" href="/w/index.php?title=%C4%90%E1%BA%B7c_bi%E1%BB%87t:Thay_%C4%91%E1%BB%95i_g%E1%BA%A7n_%C4%91%C3%A2y&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-Cây_tìm_kiếm_nhị_phân rootpage-Cây_tìm_kiếm_nhị_phân skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Bước tới nội dung</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="Trang Web"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Trình đơn chính" > <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="Trình đơn chính" > <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" > Trình đơn chính </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">Trình đơn chính</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">chuyển sang thanh bên</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">ẩn</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Điều hướng </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Trang_Ch%C3%ADnh" title="Xem trang chính [z]" accesskey="z">Trang Chính</a></li><li id="n-wikipedia-featuredcontent" class="mw-list-item"><a href="/wiki/C%E1%BB%95ng_th%C3%B4ng_tin:N%E1%BB%99i_dung_ch%E1%BB%8Dn_l%E1%BB%8Dc">Nội dung chọn lọc</a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ng%E1%BA%ABu_nhi%C3%AAn" title="Xem trang ngẫu nhiên [x]" accesskey="x">Bài viết ngẫu nhiên</a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Thay_%C4%91%E1%BB%95i_g%E1%BA%A7n_%C4%91%C3%A2y" title="Danh sách thay đổi gần đây trong wiki [r]" accesskey="r">Thay đổi gần đây</a></li><li id="n-bug_in_article" class="mw-list-item"><a href="/wiki/Wikipedia:B%C3%A1o_l%E1%BB%97i_b%C3%A0i_vi%E1%BA%BFt">Báo lỗi nội dung</a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Trang_%C4%91%E1%BA%B7c_bi%E1%BB%87t">Trang đặc biệt</a></li> </ul> </div> </div> <div id="p-wikipedia-interaction" class="vector-menu mw-portlet mw-portlet-wikipedia-interaction" > <div class="vector-menu-heading"> Tương tác </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-wikipedia-helppage" class="mw-list-item"><a href="/wiki/Wikipedia:S%C3%A1ch_h%C6%B0%E1%BB%9Bng_d%E1%BA%ABn">Hướng dẫn</a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:Gi%E1%BB%9Bi_thi%E1%BB%87u">Giới thiệu Wikipedia</a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:C%E1%BB%99ng_%C4%91%E1%BB%93ng" title="Giới thiệu dự án, cách sử dụng và tìm kiếm thông tin ở đây">Cộng đồng</a></li><li id="n-wikipedia-villagepump" class="mw-list-item"><a href="/wiki/Wikipedia:Th%E1%BA%A3o_lu%E1%BA%ADn">Thảo luận chung</a></li><li id="n-wikipedia-helpdesk" class="mw-list-item"><a href="/wiki/Wikipedia:Gi%C3%BAp_s%E1%BB%AD_d%E1%BB%A5ng_Wikipedia">Giúp sử dụng</a></li><li id="n-contactpage" class="mw-list-item"><a href="//vi.wikipedia.org/wiki/Wikipedia:Liên_lạc">Liên lạc</a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:Tr%C3%ACnh_t%E1%BA%A3i_l%C3%AAn_t%E1%BA%ADp_tin">Tải lên tập tin</a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Trang_Ch%C3%ADnh" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="Bách khoa toàn thư mở" src="/static/images/mobile/copyright/wikipedia-tagline-vi.svg" width="120" height="10" style="width: 7.5em; height: 0.625em;"> </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/%C4%90%E1%BA%B7c_bi%E1%BB%87t:T%C3%ACm_ki%E1%BA%BFm" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Tìm kiếm Wikipedia [f]" accesskey="f"> Tìm kiếm </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="Tìm kiếm trên Wikipedia" aria-label="Tìm kiếm trên Wikipedia" autocapitalize="sentences" title="Tìm kiếm Wikipedia [f]" accesskey="f" id="searchInput" > </div> <input type="hidden" name="title" value="Đặc_biệt:Tìm_kiếm"> </div> <button class="cdx-button cdx-search-input__end-button">Tìm kiếm</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Công cụ cá nhân"> <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="Giao diện"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Giao diện" > <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" > Giao diện </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=vi.wikipedia.org&uselang=vi" class="">Quyên góp</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=%C4%90%E1%BA%B7c_bi%E1%BB%87t:M%E1%BB%9F_t%C3%A0i_kho%E1%BA%A3n&returnto=C%C3%A2y+t%C3%ACm+ki%E1%BA%BFm+nh%E1%BB%8B+ph%C3%A2n" title="Bạn được khuyến khích mở tài khoản và đăng nhập; tuy nhiên, không bắt buộc phải có tài khoản" class="">Tạo tài khoản</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=%C4%90%E1%BA%B7c_bi%E1%BB%87t:%C4%90%C4%83ng_nh%E1%BA%ADp&returnto=C%C3%A2y+t%C3%ACm+ki%E1%BA%BFm+nh%E1%BB%8B+ph%C3%A2n" title="Đăng nhập sẽ có lợi hơn, tuy nhiên không bắt buộc. [o]" accesskey="o" class="">Đăng nhập</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="Thêm tùy chọn" > <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="Công cụ cá nhân" > <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" > Công cụ cá nhân </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="Bảng chọn thành viên" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=vi.wikipedia.org&uselang=vi">Quyên góp</a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=%C4%90%E1%BA%B7c_bi%E1%BB%87t:M%E1%BB%9F_t%C3%A0i_kho%E1%BA%A3n&returnto=C%C3%A2y+t%C3%ACm+ki%E1%BA%BFm+nh%E1%BB%8B+ph%C3%A2n" title="Bạn được khuyến khích mở tài khoản và đăng nhập; tuy nhiên, không bắt buộc phải có tài khoản"> Tạo tài khoản</a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=%C4%90%E1%BA%B7c_bi%E1%BB%87t:%C4%90%C4%83ng_nh%E1%BA%ADp&returnto=C%C3%A2y+t%C3%ACm+ki%E1%BA%BFm+nh%E1%BB%8B+ph%C3%A2n" title="Đăng nhập sẽ có lợi hơn, tuy nhiên không bắt buộc. [o]" accesskey="o"> Đăng nhập</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"> Trang dành cho người dùng chưa đăng nhập <a href="/wiki/Tr%E1%BB%A3_gi%C3%BAp:Gi%E1%BB%9Bi_thi%E1%BB%87u" aria-label="Tìm hiểu thêm về sửa đổi">tìm hiểu thêm</a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:%C4%90%C3%B3ng_g%C3%B3p_c%E1%BB%A7a_t%C3%B4i" title="Danh sách các sửa đổi được thực hiện qua địa chỉ IP này [y]" accesskey="y">Đóng góp</a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Th%E1%BA%A3o_lu%E1%BA%ADn_t%C3%B4i" title="Thảo luận với địa chỉ IP này [n]" accesskey="n">Thảo luận cho địa chỉ IP này</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="Trang Web"> <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="Nội dung" 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">Nội dung</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">chuyển sang thanh bên</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">ẩn</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">Đầu</div> </a> </li> <li id="toc-Định_nghĩa" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Định_nghĩa"> <div class="vector-toc-text"> 1 Định nghĩa </div> </a> <ul id="toc-Định_nghĩa-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Các_phép_toán_trên_BST" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Các_phép_toán_trên_BST"> <div class="vector-toc-text"> 2 Các phép toán trên BST </div> </a> <button aria-controls="toc-Các_phép_toán_trên_BST-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> Hiện/ẩn mục Các phép toán trên BST </button> <ul id="toc-Các_phép_toán_trên_BST-sublist" class="vector-toc-list"> <li id="toc-Tìm_kiếm_(Searching)" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Tìm_kiếm_(Searching)"> <div class="vector-toc-text"> 2.1 Tìm kiếm (Searching) </div> </a> <ul id="toc-Tìm_kiếm_(Searching)-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Chèn_(Insertion)" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Chèn_(Insertion)"> <div class="vector-toc-text"> 2.2 Chèn (Insertion) </div> </a> <ul id="toc-Chèn_(Insertion)-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Xóa_(Deletion)" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Xóa_(Deletion)"> <div class="vector-toc-text"> 2.3 Xóa (Deletion) </div> </a> <ul id="toc-Xóa_(Deletion)-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Phép_duyệt" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Phép_duyệt"> <div class="vector-toc-text"> 2.4 Phép duyệt </div> </a> <ul id="toc-Phép_duyệt-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Sắp_xếp" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Sắp_xếp"> <div class="vector-toc-text"> 2.5 Sắp xếp </div> </a> <ul id="toc-Sắp_xếp-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Mã_giả_bằng_ngôn_ngữ_C" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Mã_giả_bằng_ngôn_ngữ_C"> <div class="vector-toc-text"> 3 Mã giả bằng ngôn ngữ C </div> </a> <ul id="toc-Mã_giả_bằng_ngôn_ngữ_C-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Các_loại_cây_tìm_kiếm_nhị_phân" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Các_loại_cây_tìm_kiếm_nhị_phân"> <div class="vector-toc-text"> 4 Các loại cây tìm kiếm nhị phân </div> </a> <ul id="toc-Các_loại_cây_tìm_kiếm_nhị_phân-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Xem_thêm" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Xem_thêm"> <div class="vector-toc-text"> 5 Xem thêm </div> </a> <ul id="toc-Xem_thêm-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Chú_thích" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Chú_thích"> <div class="vector-toc-text"> 6 Chú thích </div> </a> <ul id="toc-Chú_thích-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Tham_khảo" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Tham_khảo"> <div class="vector-toc-text"> 7 Tham khảo </div> </a> <ul id="toc-Tham_khảo-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Liên_kết_ngoài" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Liên_kết_ngoài"> <div class="vector-toc-text"> 8 Liên kết ngoài </div> </a> <ul id="toc-Liên_kết_ngoài-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="Nội dung" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Mục lục" > <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="Đóng mở mục lục" > <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" > Đóng mở mục lục </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">Cây tìm kiếm nhị phân</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="Xem bài viết trong ngôn ngữ khác. Bài có sẵn trong 34 ngôn ngữ" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-34" aria-hidden="true" > 34 ngôn ngữ </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="شجرة بحث ثنائية – Tiếng Ả Rập" lang="ar" hreflang="ar" data-title="شجرة بحث ثنائية" data-language-autonym="العربية" data-language-local-name="Tiếng Ả Rập" class="interlanguage-link-target">العربية</a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Pohon_Pencarian_Biner" title="Pohon Pencarian Biner – Tiếng Indonesia" lang="id" hreflang="id" data-title="Pohon Pencarian Biner" data-language-autonym="Bahasa Indonesia" data-language-local-name="Tiếng Indonesia" class="interlanguage-link-target">Bahasa Indonesia</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 – Tiếng Bosnia" lang="bs" hreflang="bs" data-title="Binarno stablo pretraživanja" data-language-autonym="Bosanski" data-language-local-name="Tiếng Bosnia" class="interlanguage-link-target">Bosanski</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="Двоично дърво за търсене – Tiếng Bulgaria" lang="bg" hreflang="bg" data-title="Двоично дърво за търсене" data-language-autonym="Български" data-language-local-name="Tiếng Bulgaria" class="interlanguage-link-target">Български</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 – Tiếng Catalan" lang="ca" hreflang="ca" data-title="Arbre binari de cerca" data-language-autonym="Català" data-language-local-name="Tiếng Catalan" class="interlanguage-link-target">Català</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 – Tiếng Séc" lang="cs" hreflang="cs" data-title="Binární vyhledávací strom" data-language-autonym="Čeština" data-language-local-name="Tiếng Séc" class="interlanguage-link-target">Čeština</a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Bin%C3%A6rt_s%C3%B8getr%C3%A6" title="Binært søgetræ – Tiếng Đan Mạch" lang="da" hreflang="da" data-title="Binært søgetræ" data-language-autonym="Dansk" data-language-local-name="Tiếng Đan Mạch" class="interlanguage-link-target">Dansk</a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum" title="Binärer Suchbaum – Tiếng Đức" lang="de" hreflang="de" data-title="Binärer Suchbaum" data-language-autonym="Deutsch" data-language-local-name="Tiếng Đức" class="interlanguage-link-target">Deutsch</a></li><li class="interlanguage-link interwiki-en badge-Q17437798 badge-goodarticle mw-list-item" title="bài viết tốt"><a href="https://en.wikipedia.org/wiki/Binary_search_tree" title="Binary search tree – Tiếng Anh" lang="en" hreflang="en" data-title="Binary search tree" data-language-autonym="English" data-language-local-name="Tiếng Anh" class="interlanguage-link-target">English</a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/%C3%81rbol_binario_de_b%C3%BAsqueda" title="Árbol binario de búsqueda – Tiếng Tây Ban Nha" lang="es" hreflang="es" data-title="Árbol binario de búsqueda" data-language-autonym="Español" data-language-local-name="Tiếng Tây Ban Nha" class="interlanguage-link-target">Español</a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C_%D8%AF%D9%88%D8%AF%D9%88%DB%8C%DB%8C" title="درخت جستجوی دودویی – Tiếng Ba Tư" lang="fa" hreflang="fa" data-title="درخت جستجوی دودویی" data-language-autonym="فارسی" data-language-local-name="Tiếng Ba Tư" class="interlanguage-link-target">فارسی</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 – Tiếng Pháp" lang="fr" hreflang="fr" data-title="Arbre binaire de recherche" data-language-autonym="Français" data-language-local-name="Tiếng Pháp" class="interlanguage-link-target">Français</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="이진 탐색 트리 – Tiếng Hàn" lang="ko" hreflang="ko" data-title="이진 탐색 트리" data-language-autonym="한국어" data-language-local-name="Tiếng Hàn" class="interlanguage-link-target">한국어</a></li><li class="interlanguage-link interwiki-hy mw-list-item"><a href="https://hy.wikipedia.org/wiki/%D4%B2%D5%AB%D5%B6%D5%A1%D6%80_%D5%B8%D6%80%D5%B8%D5%B6%D5%B4%D5%A1%D5%B6_%D5%AE%D5%A1%D5%BC" title="Բինար որոնման ծառ – Tiếng Armenia" lang="hy" hreflang="hy" data-title="Բինար որոնման ծառ" data-language-autonym="Հայերեն" data-language-local-name="Tiếng Armenia" class="interlanguage-link-target">Հայերեն</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 – Tiếng Italy" lang="it" hreflang="it" data-title="Albero binario di ricerca" data-language-autonym="Italiano" data-language-local-name="Tiếng Italy" class="interlanguage-link-target">Italiano</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="עץ חיפוש – Tiếng Do Thái" lang="he" hreflang="he" data-title="עץ חיפוש" data-language-autonym="עברית" data-language-local-name="Tiếng Do Thái" class="interlanguage-link-target">עברית</a></li><li class="interlanguage-link interwiki-kn mw-list-item"><a href="https://kn.wikipedia.org/wiki/%E0%B2%AC%E0%B3%88%E0%B2%A8%E0%B2%B0%E0%B2%BF_%E0%B2%B8%E0%B2%B0%E0%B3%8D%E0%B2%9A%E0%B3%8D_%E0%B2%9F%E0%B3%8D%E0%B2%B0%E0%B3%80_(%E0%B2%AC%E0%B3%88%E0%B2%A8%E0%B2%B0%E0%B2%BF_%E0%B2%B9%E0%B3%81%E0%B2%A1%E0%B3%81%E0%B2%95%E0%B2%BE%E0%B2%9F%E0%B2%A6_%E0%B2%9F%E0%B3%8D%E0%B2%B0%E0%B3%80)" title="ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ (ಬೈನರಿ ಹುಡುಕಾಟದ ಟ್ರೀ) – Tiếng Kannada" lang="kn" hreflang="kn" data-title="ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ (ಬೈನರಿ ಹುಡುಕಾಟದ ಟ್ರೀ)" data-language-autonym="ಕನ್ನಡ" data-language-local-name="Tiếng Kannada" class="interlanguage-link-target">ಕನ್ನಡ</a></li><li class="interlanguage-link interwiki-lmo mw-list-item"><a href="https://lmo.wikipedia.org/wiki/Alber_binari_de_ricerca" title="Alber binari de ricerca – Tiếng Lombard" lang="lmo" hreflang="lmo" data-title="Alber binari de ricerca" data-language-autonym="Lombard" data-language-local-name="Tiếng Lombard" class="interlanguage-link-target">Lombard</a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Binaire_zoekboom" title="Binaire zoekboom – Tiếng Hà Lan" lang="nl" hreflang="nl" data-title="Binaire zoekboom" data-language-autonym="Nederlands" data-language-local-name="Tiếng Hà Lan" class="interlanguage-link-target">Nederlands</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="二分探索木 – Tiếng Nhật" lang="ja" hreflang="ja" data-title="二分探索木" data-language-autonym="日本語" data-language-local-name="Tiếng Nhật" class="interlanguage-link-target">日本語</a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Binarne_drzewo_poszukiwa%C5%84" title="Binarne drzewo poszukiwań – Tiếng Ba Lan" lang="pl" hreflang="pl" data-title="Binarne drzewo poszukiwań" data-language-autonym="Polski" data-language-local-name="Tiếng Ba Lan" class="interlanguage-link-target">Polski</a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/%C3%81rvore_bin%C3%A1ria_de_busca" title="Árvore binária de busca – Tiếng Bồ Đào Nha" lang="pt" hreflang="pt" data-title="Árvore binária de busca" data-language-autonym="Português" data-language-local-name="Tiếng Bồ Đào Nha" class="interlanguage-link-target">Português</a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Arbore_binar_de_c%C4%83utare" title="Arbore binar de căutare – Tiếng Romania" lang="ro" hreflang="ro" data-title="Arbore binar de căutare" data-language-autonym="Română" data-language-local-name="Tiếng Romania" class="interlanguage-link-target">Română</a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0" title="Двоичное дерево поиска – Tiếng Nga" lang="ru" hreflang="ru" data-title="Двоичное дерево поиска" data-language-autonym="Русский" data-language-local-name="Tiếng Nga" class="interlanguage-link-target">Русский</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 – Tiếng Slovak" lang="sk" hreflang="sk" data-title="Binárny vyhľadávací strom" data-language-autonym="Slovenčina" data-language-local-name="Tiếng Slovak" class="interlanguage-link-target">Slovenčina</a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/Binarno_stablo_pretrage" title="Binarno stablo pretrage – Tiếng Serbia" lang="sr" hreflang="sr" data-title="Binarno stablo pretrage" data-language-autonym="Српски / srpski" data-language-local-name="Tiếng Serbia" class="interlanguage-link-target">Српски / srpski</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 – Tiếng Serbo-Croatia" lang="sh" hreflang="sh" data-title="Binarno stablo pretrage" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="Tiếng Serbo-Croatia" class="interlanguage-link-target">Srpskohrvatski / српскохрватски</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 – Tiếng Phần Lan" lang="fi" hreflang="fi" data-title="Binäärinen hakupuu" data-language-autonym="Suomi" data-language-local-name="Tiếng Phần Lan" class="interlanguage-link-target">Suomi</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 – Tiếng Thụy Điển" lang="sv" hreflang="sv" data-title="Binärt sökträd" data-language-autonym="Svenska" data-language-local-name="Tiếng Thụy Điển" class="interlanguage-link-target">Svenska</a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%95%E0%B9%89%E0%B8%99%E0%B9%84%E0%B8%A1%E0%B9%89%E0%B8%84%E0%B9%89%E0%B8%99%E0%B8%AB%E0%B8%B2%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B8%97%E0%B8%A7%E0%B8%B4%E0%B8%A0%E0%B8%B2%E0%B8%84" title="ต้นไม้ค้นหาแบบทวิภาค – Tiếng Thái" lang="th" hreflang="th" data-title="ต้นไม้ค้นหาแบบทวิภาค" data-language-autonym="ไทย" data-language-local-name="Tiếng Thái" class="interlanguage-link-target">ไทย</a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/%C4%B0kili_arama_a%C4%9Fac%C4%B1" title="İkili arama ağacı – Tiếng Thổ Nhĩ Kỳ" lang="tr" hreflang="tr" data-title="İkili arama ağacı" data-language-autonym="Türkçe" data-language-local-name="Tiếng Thổ Nhĩ Kỳ" class="interlanguage-link-target">Türkçe</a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%94%D0%B2%D1%96%D0%B9%D0%BA%D0%BE%D0%B2%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D1%88%D1%83%D0%BA%D1%83" title="Двійкове дерево пошуку – Tiếng Ukraina" lang="uk" hreflang="uk" data-title="Двійкове дерево пошуку" data-language-autonym="Українська" data-language-local-name="Tiếng Ukraina" class="interlanguage-link-target">Українська</a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9" title="二元搜尋樹 – Tiếng Quảng Đông" lang="yue" hreflang="yue" data-title="二元搜尋樹" data-language-autonym="粵語" data-language-local-name="Tiếng Quảng Đông" class="interlanguage-link-target">粵語</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="二元搜尋樹 – Tiếng Trung" lang="zh" hreflang="zh" data-title="二元搜尋樹" data-language-autonym="中文" data-language-local-name="Tiếng Trung" class="interlanguage-link-target">中文</a></li> </ul> <div class="after-portlet after-portlet-lang"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q623818#sitelinks-wikipedia" title="Sửa liên kết giữa ngôn ngữ" class="wbc-editpage">Sửa liên kết</a></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Không gian tên"> <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/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n" title="Xem bài viết [c]" accesskey="c">Bài viết</a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Th%E1%BA%A3o_lu%E1%BA%ADn:C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n" rel="discussion" title="Thảo luận về trang này [t]" accesskey="t">Thảo luận</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="Thay đổi biến thể ngôn ngữ" > <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" >Tiếng Việt </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="Giao diện"> <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/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n">Đọc</a></li><li id="ca-ve-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit" title="Sửa đổi trang này [v]" accesskey="v">Sửa đổi</a></li><li id="ca-edit" class="collapsible vector-tab-noicon mw-list-item"><a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit" title="Sửa đổi mã nguồn của trang này [e]" accesskey="e">Sửa mã nguồn</a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=history" title="Các phiên bản cũ của trang này [h]" accesskey="h">Xem lịch sử</a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Công cụ trang"> <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="Công cụ" > <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" >Công cụ </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">Công cụ</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">chuyển sang thanh bên</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">ẩn</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="Thêm tùy chọn" > <div class="vector-menu-heading"> Tác vụ </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/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n">Đọc</a></li><li id="ca-more-ve-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit" title="Sửa đổi trang này [v]" accesskey="v">Sửa đổi</a></li><li id="ca-more-edit" class="collapsible vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit" title="Sửa đổi mã nguồn của trang này [e]" accesskey="e">Sửa mã nguồn</a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=history">Xem lịch sử</a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> Chung </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Li%C3%AAn_k%E1%BA%BFt_%C4%91%E1%BA%BFn_%C4%91%C3%A2y/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n" title="Các trang liên kết đến đây [j]" accesskey="j">Các liên kết đến đây</a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Thay_%C4%91%E1%BB%95i_li%C3%AAn_quan/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n" rel="nofollow" title="Thay đổi gần đây của các trang liên kết đến đây [k]" accesskey="k">Thay đổi liên quan</a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&oldid=71839321" title="Liên kết thường trực đến phiên bản này của trang">Liên kết thường trực</a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=info" title="Thêm chi tiết về trang này">Thông tin trang</a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=%C4%90%E1%BA%B7c_bi%E1%BB%87t:Tr%C3%ADch_d%E1%BA%ABn&page=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&id=71839321&wpFormIdentifier=titleform" title="Hướng dẫn cách trích dẫn trang này">Trích dẫn trang này</a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=%C4%90%E1%BA%B7c_bi%E1%BB%87t:UrlShortener&url=https%3A%2F%2Fvi.wikipedia.org%2Fwiki%2FC%25C3%25A2y_t%25C3%25ACm_ki%25E1%25BA%25BFm_nh%25E1%25BB%258B_ph%25C3%25A2n">Lấy URL ngắn gọn</a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=%C4%90%E1%BA%B7c_bi%E1%BB%87t:QrCode&url=https%3A%2F%2Fvi.wikipedia.org%2Fwiki%2FC%25C3%25A2y_t%25C3%25ACm_ki%25E1%25BA%25BFm_nh%25E1%25BB%258B_ph%25C3%25A2n">Tải mã QR</a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> In và xuất </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=%C4%90%E1%BA%B7c_bi%E1%BB%87t:S%C3%A1ch&bookcmd=book_creator&referer=C%C3%A2y+t%C3%ACm+ki%E1%BA%BFm+nh%E1%BB%8B+ph%C3%A2n">Tạo một quyển sách</a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=%C4%90%E1%BA%B7c_bi%E1%BB%87t:DownloadAsPdf&page=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=show-download-screen">Tải dưới dạng PDF</a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&printable=yes" title="Bản để in ra của trang [p]" accesskey="p">Bản để in ra</a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> Tại dự án khác </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">Wikimedia Commons</a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q623818" title="Liên kết đến khoản mục kết nối trong kho dữ liệu [g]" accesskey="g">Khoản mục Wikidata</a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Công cụ trang"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Giao diện"> <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">Giao diện</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">chuyển sang thanh bên</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">ẩn</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">Bách khoa toàn thư mở Wikipedia</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="vi" dir="ltr">Cây tìm kiếm nhị phân (viết tắt <a href="/wiki/Ti%E1%BA%BFng_Anh" title="Tiếng Anh">tiếng Anh</a>: BST - Binary Search Tree) là một <a href="/wiki/C%E1%BA%A5u_tr%C3%BAc_d%E1%BB%AF_li%E1%BB%87u" title="Cấu trúc dữ liệu">cấu trúc dữ liệu</a> rất thuận lợi cho bài toán tìm kiếm. Mỗi cây tìm kiếm nhị phân đều có tính chất sau: Với mỗi nút <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}">, các nút ở cây con bên trái của <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}"> đều có giá trị key nhỏ hơn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}">: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y.key\leq x.key}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> <mo>.</mo> <mi>k</mi> <mi>e</mi> <mi>y</mi> <mo>≤</mo> <mi>x</mi> <mo>.</mo> <mi>k</mi> <mi>e</mi> <mi>y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y.key\leq x.key}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c63af62678db4512b521debfb6b1ea4ef3e15bcf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.552ex; height:2.509ex;" alt="{\displaystyle y.key\leq x.key}">, còn các nút ở cây con bên phải của <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}"> đều có key lớn hơn hoặc bằng <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}">: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y.key\geq x.key}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> <mo>.</mo> <mi>k</mi> <mi>e</mi> <mi>y</mi> <mo>≥</mo> <mi>x</mi> <mo>.</mo> <mi>k</mi> <mi>e</mi> <mi>y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y.key\geq x.key}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a3b83bb0fd502d931c76639db4088a80dffbe22e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.552ex; height:2.509ex;" alt="{\displaystyle y.key\geq x.key}">. <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Định_nghĩa">Định nghĩa</h2>[<a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit&section=1" title="Sửa đổi phần “Định nghĩa”" class="mw-editsection-visualeditor">sửa</a> | <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit&section=1" title="Sửa mã nguồn tại đề mục: Định nghĩa">sửa mã nguồn</a>]</div> <figure class="mw-halign-left" typeof="mw:File/Thumb"><a href="/wiki/T%E1%BA%ADp_tin:CayTimKiem.PNG" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/vi/thumb/a/a8/CayTimKiem.PNG/200px-CayTimKiem.PNG" decoding="async" width="200" height="180" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/vi/thumb/a/a8/CayTimKiem.PNG/300px-CayTimKiem.PNG 1.5x, //upload.wikimedia.org/wikipedia/vi/a/a8/CayTimKiem.PNG 2x" data-file-width="303" data-file-height="273" /></a><figcaption>Cây tìm kiếm nhị phân</figcaption></figure> Cây tìm kiếm ứng với n khóa <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{1},k_{2},...k_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{1},k_{2},...k_{n}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bf5e750c4d68d86a19604b4feee9acf868b4bcdf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.13ex; height:2.509ex;" alt="{\displaystyle k_{1},k_{2},...k_{n}}"> là <a href="/wiki/C%C3%A2y_(c%E1%BA%A5u_tr%C3%BAc_d%E1%BB%AF_li%E1%BB%87u)" title="Cây (cấu trúc dữ liệu)">cây nhị phân</a> mà mỗi nút đều được gán một khóa sao cho với mỗi mỗi nút k: <ul><li>Mọi khóa trên cây con trái đều nhỏ hơn khóa trên nút k</li> <li>Mọi khóa trên cây con phải đều lớn hơn khóa trên nút k</li></ul> Cây tìm kiếm nhị phân là một cấu trúc dữ liệu cơ bản được sử dụng để xây dựng các cấu trúc dữ liệu trừu tượng hơn như các tập hợp, đa tập hợp, các dãy kết hợp. Nếu một BST có chứa các giá trị giống nhau thì nó biểu diễn một đa tập hợp. Cây loại này sử dụng các bất đẳng thức không nghiêm ngặt. Mọi nút trong cây con trái có khóa nhỏ hơn khóa của nút cha, mọi nút trên cây con phải có nút lớn hơn hoặc bằng khóa của nút cha. Nếu một BST không chứa các giá trị giống nhau thì nó biểu diễn một tập hợp đơn trị như trong <a href="/wiki/L%C3%BD_thuy%E1%BA%BFt_t%E1%BA%ADp_h%E1%BB%A3p" title="Lý thuyết tập hợp">lý thuyết tập hợp</a>. Cây loại này sử dụng các bất đẳng thức nghiêm ngặt. Mọi nút trong cây con trái có khóa nhỏ hơn khóa của nút cha, mọi nút trên cây con phải có khóa lớn hơn khóa của nút cha. Việc chọn đưa các giá trị bằng nhau vào cây con phải (hay trái) là tùy theo mỗi người. Một số người cũng đưa các giá trị bằng nhau vào cả hai phía, nhưng khi đó việc tìm kiếm trở nên phức tạp hơn. <div class="mw-heading mw-heading2"><h2 id="Các_phép_toán_trên_BST">Các phép toán trên BST</h2>[<a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit&section=2" title="Sửa đổi phần “Các phép toán trên BST”" class="mw-editsection-visualeditor">sửa</a> | <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit&section=2" title="Sửa mã nguồn tại đề mục: Các phép toán trên BST">sửa mã nguồn</a>]</div> <div class="mw-heading mw-heading3"><h3 id="Tìm_kiếm_(Searching)">Tìm kiếm (Searching)</h3>[<a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit&section=3" title="Sửa đổi phần “Tìm kiếm (Searching)”" class="mw-editsection-visualeditor">sửa</a> | <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit&section=3" title="Sửa mã nguồn tại đề mục: Tìm kiếm (Searching)">sửa mã nguồn</a>]</div> Việc tìm một khóa trên BST có thể thực hiện nhờ <a href="/wiki/%C4%90%E1%BB%87_quy" title="Đệ quy">đệ quy</a>. Chúng ta bắt đầu từ gốc. Nếu khóa cần tìm bằng khóa của gốc thì khóa đó trên cây, nếu khóa cần tìm nhỏ hơn khóa ở gốc, ta phải tìm nó trên cây con trái, nếu khóa cần tìm lớn hơn khóa ở gốc, ta phải tìm nó trên cây con phải. Nếu cây con (trái hoặc phải) là rỗng thì khóa cần tìm không có trên cây. <a href="/wiki/T%E1%BA%ADp_tin:Bstreesearchexample.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/f/fa/Bstreesearchexample.jpg" decoding="async" width="342" height="153" class="mw-file-element" data-file-width="342" data-file-height="153" /></a> Giả mã <pre><code> </code></pre><code>Search_binary_tree(node, key); </code><code><pre> if node is Null then return None; /* key not found */ if key < node.key: return search binary_tree(node.left, key); else if key > node.key return search_binary_tree(node.right, key) else /* key is equal to node key */ return node.value; # found key </pre></code><code></code><code></code> Mã Python: <code><div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre> def search_binary_tree(node, key): if node is None: return None # key not found if key < node.key: return search_binary_tree(node.leftChild, key) elif key > node.key: return search_binary_tree(node.rightChild, key) else: # key is equal to node key return node.value # found key </pre></div></code> Thời gian tìm kiếm trung bình là O(log 2n), và là O(n) khi cây là không cân bằng chỉ là một <a href="/wiki/Danh_s%C3%A1ch_li%C3%AAn_k%E1%BA%BFt" title="Danh sách liên kết">danh sách liên kết</a>. <div class="mw-heading mw-heading3"><h3 id="Chèn_(Insertion)">Chèn (Insertion)</h3>[<a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit&section=4" title="Sửa đổi phần “Chèn (Insertion)”" class="mw-editsection-visualeditor">sửa</a> | <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit&section=4" title="Sửa mã nguồn tại đề mục: Chèn (Insertion)">sửa mã nguồn</a>]</div> Phép chèn bắt đầu giống như phép tìm kiếm; Nếu khóa của gốc khác khóa cần chèn ta tìm nó trong cây con trái hoặc phải. Nếu cây con trái hoặc phải tương ứng là rỗng (không tìm thấy) thì thêm một nút và gán cho nút ấy khóa cần chèn. Sau đây là mã trong C++: <code> </code><code><pre>void InsertNode(struct node *&treeNode, struct node *newNode) { //Inserts node pointered by "newNode" to the subtree started by "treeNode" if (treeNode == NULL) treeNode = newNode; //Only changes "node" when it is NULL else if (newNode->value < treeNode->value) InsertNode(treeNode->left, newNode); else InsertNode(treeNode->right, newNode); } </pre></code><code></code><code></code> Mã Python: <code><div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre> def binary_tree_insert(node, key, value): if node is None: return TreeNode(None, key, value, None) if key == node.key: return TreeNode(node.left, key, value, node.right) if key < node.key: return TreeNode(binary_tree_insert(node.left, key, value), node.key, node.value, node.right) else: return TreeNode(node.left, node.key, node.value, binary_tree_insert(node.right, key, value)) </pre></div></code> <div class="mw-heading mw-heading3"><h3 id="Xóa_(Deletion)">Xóa (Deletion)</h3>[<a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit&section=5" title="Sửa đổi phần “Xóa (Deletion)”" class="mw-editsection-visualeditor">sửa</a> | <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit&section=5" title="Sửa mã nguồn tại đề mục: Xóa (Deletion)">sửa mã nguồn</a>]</div> Xét các trường hợp sau <ul><li>Xóa một lá: Vì lá không có con nên chỉ cần giải phóng nó khỏi cây.</li></ul> <a href="/wiki/T%E1%BA%ADp_tin:Bstreedeleteleafexample.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/6/6c/Bstreedeleteleafexample.jpg" decoding="async" width="342" height="153" class="mw-file-element" data-file-width="342" data-file-height="153" /></a> <ul><li>Xóa nút có một con: Xóa và thay thế nó bằng con duy nhất của nó.</li></ul> <a href="/wiki/T%E1%BA%ADp_tin:Bstreedeleteonechildexample.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/6/6a/Bstreedeleteonechildexample.jpg" decoding="async" width="701" height="153" class="mw-file-element" data-file-width="701" data-file-height="153" /></a> <ul><li>Xóa một nút có hai con: Xóa nút đó và thay thế nó bằng nút có khóa lớn nhất trong các khóa nhỏ hơn khóa của nó (được gọi là "nút tiền nhiệm" -nút cực phải của cây con trái) hoặc nút có khóa nhỏ nhất trong các khóa lớn hơn nó (được gọi là "nút kế vị" - nút cực trái của cây con phải)</li></ul> Cũng có thể tìm nút tiền nhiệm hoặc nút kế vị đổi chỗ nó với nút cần xóa và sau đó xóa nó. Vì các nút kiểu này có ít hơn hai con nên việc xóa nó được quy về hai trường hợp trước. <a href="/wiki/T%E1%BA%ADp_tin:Bstreedeletenotrightchildexample.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/1/15/Bstreedeletenotrightchildexample.jpg" decoding="async" width="632" height="255" class="mw-file-element" data-file-width="632" data-file-height="255" /></a> Sau đây là mã C++ <pre><code>void DeleteNode(struct node*& node) { if (node->left == NULL) { struct node* temp = node; node = node->right; delete temp; } else if (node->right == NULL) { struct node* temp = node; node = node->left; delete temp; } else { // In-Order predecessor(right most child of left subtree) // Node has two children - get max of left subtree struct node** temp = &(node->left); // get left node of the original node // find the right most child of the subtree of the left node while ((*temp)->right != NULL) { temp = &((*temp)->right); } // copy the value from the right most child of left subtree to the original node node->value = (*temp)->value; // then delete the right most child of left subtree since it's value is // now in the original node DeleteNode(*temp); } }</code> </pre> Mã python: <code><div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre>def findMin(self): ''' Finds the smallest element that is a child of *self* ''' current_node = self while current_node.left_child: current_node = current_node.left_child return current_node def replace_node_in_parent(self, new_value=None): ''' Removes the reference to *self* from *self.parent* and replaces it with *new_value*. ''' if self == self.parent.left_child: self.parent.left_child = new_value else: self.parent.right_child = new_value if new_value: new_value.parent = self.parent def binary_tree_delete(self, key): if key < self.key: self.left_child.binary_tree_delete(key) elif key > self.key: self.right_child.binary_tree_delete(key) else: # delete the key here if self.left_child and self.right_child: # if both children are present # get the smallest node that's bigger than *self* successor = self.right_child.findMin() self.key = successor.key # if *successor* has a child, replace it with that # at this point, it can only have a *right_child* # if it has no children, *right_child* will be "None" successor.replace_node_in_parent(successor.right_child) elif self.left_child or self.right_child: # if the node has only one child if self.left_child: self.replace_node_in_parent(self.left_child) else: self.replace_node_in_parent(self.right_child) else: # this node has no children self.replace_node_in_parent(None) </pre></div></code><code></code><code></code> <div class="mw-heading mw-heading3"><h3 id="Phép_duyệt">Phép duyệt</h3>[<a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit&section=6" title="Sửa đổi phần “Phép duyệt”" class="mw-editsection-visualeditor">sửa</a> | <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit&section=6" title="Sửa mã nguồn tại đề mục: Phép duyệt">sửa mã nguồn</a>]</div> Khi một cây tìm kiếm nhị phân được tạo ra, tất cả các nút có thể được duyệt theo thứ tự giữa nhờ duyệt đệ quy cây con bên trái, in nút đang duyệt, rồi duyệt đệ quy cây con bên phải, tiếp tục làm như vây với mỗi nút của cây trong quá trình đệ quy. Với mọi cây nhị phân, cây có thể được duyệt theo thứ tự trước() hoặc theo thứ tự sau(), cả hai cách đều hữu dụng với cây tìm kiếm nhị phân. Đoạn mã cho duyệt theo thứ giữa được viết dưới đây với C++: <code> </code><code><pre>void traverse_binary_tree(struct node* n) { if(n==null) //Cay rong return NULL; else { traverse_binary_tree(n->left); //Duyet cay con trai theo thu tu giua printf("%d",n.key); //Tham nut traverse_binary_tree(n->right); //Duyet cay con phai theo thu tu giua } } </pre></code><code></code><code></code> Phép duyệt có độ phức tạp tính toán là Ω(n), vì nó phải duyệt qua tất cả các nút. Độ phức tạp trên cũng là O("n"). <div class="mw-heading mw-heading3"><h3 id="Sắp_xếp">Sắp xếp</h3>[<a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit&section=7" title="Sửa đổi phần “Sắp xếp”" class="mw-editsection-visualeditor">sửa</a> | <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit&section=7" title="Sửa mã nguồn tại đề mục: Sắp xếp">sửa mã nguồn</a>]</div> Một cây tìm kiếm nhị phân có thể được sử dụng như một <a href="/wiki/Thu%E1%BA%ADt_to%C3%A1n_s%E1%BA%AFp_x%E1%BA%BFp" title="Thuật toán sắp xếp">giải thuật sắp xếp</a> đơn giản nhưng hiểu quả. Giống như <a href="/wiki/S%E1%BA%AFp_x%E1%BA%BFp_vun_%C4%91%E1%BB%91ng" title="Sắp xếp vun đống">heapsort</a>, chúng ta chèn tất cả các giá trị chúng ta muốn sắp xếp vào một cây tìm kiếm nhị phân và in ra kết quả theo thứ tự: <code><div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre>def build_binary_tree(values): tree = None for v in values: tree = binary_tree_insert(tree, v) return tree def get_inorder_traversal(root): ''' Returns a list containing all the values in the tree, starting at *root*. Traverses the tree in-order(leftChild, root, rightChild). ''' result = [] traverse_binary_tree(root, lambda element: result.append(element)) return result </pre></div></code> Trường hợp xấu nhất của <code>build_binary_tree</code> có độ phức tạp là <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (n^{2})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/215877752c4f392a7276328d4d37709bf7c3f55d" 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 \Theta (n^{2})}">—nếu nhập vào một dãy giá trị đã sắp xếp, cây nhị phân tạo thành sẽ không có các nút trái. Ví dụ, <code>traverse_binary_tree([1, 2, 3, 4, 5])</code> tạo thành cây <code>(1 (2 (3 (4 (5)))))</code>. Có một vài cách để vượt qua trường hợp này với các cây nhị phân đơn giản; cách đơn giản nhất là <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n_t%E1%BB%B1_c%C3%A2n_b%E1%BA%B1ng&action=edit&redlink=1" class="new" title="Cây tìm kiếm nhị phân tự cân bằng (trang không tồn tại)">cây tìm kiếm nhị phân tự cân bằng</a>. Với thủ tục này được sử dụng với cây nhị phân tự cân bằng, trường hợp xấu nhất sẽ có độ phức tạp là O(nlog n). <div class="mw-heading mw-heading2"><h2 id="Mã_giả_bằng_ngôn_ngữ_C">Mã giả bằng ngôn ngữ C</h2>[<a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit&section=8" title="Sửa đổi phần “Mã giả bằng ngôn ngữ C”" class="mw-editsection-visualeditor">sửa</a> | <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit&section=8" title="Sửa mã nguồn tại đề mục: Mã giả bằng ngôn ngữ C">sửa mã nguồn</a>]</div> <div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>#include <conio.h> #include <stdio.h> #include <malloc.h> //Khai bao cay nhi phan typedef char TData; typedef struct TNode{ TData Data; TNode* left; TNode* right; }; typedef TNode* TTree; /*=== Tao cay rong ===*/ void MakeNull_Tree(TTree *T) { (*T)=NULL; } /*=== Kiem tra cay rong ===*/ int EmptyTree(TTree T) { return T==NULL; } /*=== Xac dinh con trai ===*/ TTree LeftChild(TTree T) { if(T != NULL) return T->left; else return NULL; } /*=== Xac dinh con phai ===*/ TTree RightChild(TTree T) { if(T != NULL) return T->right; else return NULL; } /*=== Xac dinh nut la ===*/ int isLeaf(TTree T) { if((T != NULL) && (T->left == NULL) && (T->right == NULL)) return 1; else return NULL; } /*=== Xac dinh so nut cua cay ===*/ int nb_nodes(TTree T) { if(EmptyTree(T)) return 0; else return nb_nodes(T->left)+nb_nodes(T->right)+1; } // Ham xac dinh gia tri lon nhat trong hai so nguyen int max(int value1,int value2) { return ((value1 > value2) ? value1: value2); //xac dinh gia tri lon nhat trong 2 gia tri so nguyen } // Ham xac dinh chieu cao cua cay int TreeHeight(TTree T) { int height=0; if (!EmptyTree(T)) { if (isLeaf(T)) return 0; else height = max(TreeHeight(LeftChild(T)),TreeHeight(RightChild(T)))+1; } return height; } // Ham xac dinh so nut la tren cay int nb_leaf(TTree T) { int leaf=0; if(!EmptyTree(T)) { if (isLeaf(T)) leaf++; else leaf = nb_leaf(LeftChild(T))+nb_leaf(RightChild(T)); }; return leaf; } /*=== Tao cay moi tu hai cay co san ===*/ TTree Create2(TData v,TTree left,TTree right) { TTree N; // Khai bao 1 cay moi N = (TNode*)malloc(sizeof(TNode)); //Cap phat vung nho cho nut N N->Data = v; // Nhan cua nut N la v N->left = left; //Con trai cua N la cay left N->right = right; //Con phai cua N la cay right return N; } /*=== Duyet cay nhi phan ===*/ //Duyet tien tu void NLR(TTree T) { if(!EmptyTree(T)) { printf(" %c",T->Data); //Xu ly nut NLR(LeftChild(T)); //Duyet tien tu con trai NLR(RightChild(T)); //Duyet tien tu con phai } } //Duyet trung tu void LNR(TTree T) { if(!EmptyTree(T)) { LNR(LeftChild(T)); //Duyet trung tu con trai printf(" %c",T->Data);//Xu ly nut LNR(RightChild(T));//Duyet trung tu con phai } } //Duyet hau tu void LRN(TTree T) { if(!EmptyTree(T)) { LRN(LeftChild(T)); //Duyet hau tu con trai LRN(RightChild(T));//Duyet hau tu con phai printf(" %c",T->Data);//Xu ly nut } } </pre></div> <div class="mw-heading mw-heading2"><h2 id="Các_loại_cây_tìm_kiếm_nhị_phân">Các loại cây tìm kiếm nhị phân</h2>[<a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit&section=9" title="Sửa đổi phần “Các loại cây tìm kiếm nhị phân”" class="mw-editsection-visualeditor">sửa</a> | <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit&section=9" title="Sửa mã nguồn tại đề mục: Các loại cây tìm kiếm nhị phân">sửa mã nguồn</a>]</div> Có rất nhiều loại cây tìm kiếm nhị phân. <a href="/wiki/C%C3%A2y_AVL" title="Cây AVL">cây AVL</a> và <a href="/wiki/C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en" title="Cây đỏ đen">cây đỏ đen</a> đều là các dạng của <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n_t%E1%BB%B1_c%C3%A2n_b%E1%BA%B1ng&action=edit&redlink=1" class="new" title="Cây tìm kiếm nhị phân tự cân bằng (trang không tồn tại)">cây tìm kiếm nhị phân tự cân bằng</a>. () là một cây nhị phân có thể tự đẩy các phần mới vào gần nút gốc. Trong một <a href="/wiki/Treap" title="Treap">treap</a> ("cây <a href="/wiki/%C4%90%E1%BB%91ng_(c%E1%BA%A5u_tr%C3%BAc_d%E1%BB%AF_li%E1%BB%87u)" title="Đống (cấu trúc dữ liệu)">heap</a>"), mỗi nút có một sự ưu tiên (priority) và các nút cha có sự ưu tiên cao hơn các nút con của chúng. <div class="mw-heading mw-heading2"><h2 id="Xem_thêm">Xem thêm</h2>[<a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit&section=10" title="Sửa đổi phần “Xem thêm”" class="mw-editsection-visualeditor">sửa</a> | <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit&section=10" title="Sửa mã nguồn tại đề mục: Xem thêm">sửa mã nguồn</a>]</div> <ul><li><a href="/wiki/T%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n" title="Tìm kiếm nhị phân">Tìm kiếm nhị phân</a></li> <li><a href="/wiki/C%C3%A2y_(l%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%93_th%E1%BB%8B)" title="Cây (lý thuyết đồ thị)">cây nhị phân</a></li> <li><a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n_t%E1%BB%B1_c%C3%A2n_b%E1%BA%B1ng&action=edit&redlink=1" class="new" title="Cây tìm kiếm nhị phân tự cân bằng (trang không tồn tại)">Cây tìm kiếm nhị phân tự cân bằng</a></li> <li><a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n_ng%E1%BA%ABu_nhi%C3%AAn&action=edit&redlink=1" class="new" title="Cây tìm kiếm nhị phân ngẫu nhiên (trang không tồn tại)">Cây tìm kiếm nhị phân ngẫu nhiên</a></li> <li><a href="/w/index.php?title=C%C3%A2y_B&action=edit&redlink=1" class="new" title="Cây B (trang không tồn tại)">Cây B</a></li> <li><a href="/wiki/C%E1%BA%A5u_tr%C3%BAc_d%E1%BB%AF_li%E1%BB%87u" title="Cấu trúc dữ liệu">Cấu trúc dữ liệu</a></li> <li><a href="/wiki/B%E1%BA%A3ng_b%C4%83m" title="Bảng băm">bảng băm</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Chú_thích">Chú thích</h2>[<a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit&section=11" title="Sửa đổi phần “Chú thích”" class="mw-editsection-visualeditor">sửa</a> | <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit&section=11" title="Sửa mã nguồn tại đề mục: Chú thích">sửa mã nguồn</a>]</div> <style data-mw-deduplicate="TemplateStyles:r71728118">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist" style="list-style-type: decimal;"> </div> <div class="mw-heading mw-heading2"><h2 id="Tham_khảo">Tham khảo</h2>[<a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit&section=12" title="Sửa đổi phần “Tham khảo”" class="mw-editsection-visualeditor">sửa</a> | <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit&section=12" title="Sửa mã nguồn tại đề mục: Tham khảo">sửa mã nguồn</a>]</div> <ul><li><a href="/wiki/Donald_Knuth" title="Donald Knuth">Donald Knuth</a>. The Art of Compter Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. <a href="/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0201896850" class="internal mw-magiclink-isbn">ISBN 0-201-89685-0</a>. Section 6.2.2: Binary Tree Searching, pp. 426–458.</li> <li><a href="/w/index.php?title=Thomas_H._Cormen&action=edit&redlink=1" class="new" title="Thomas H. Cormen (trang không tồn tại)">Thomas H. Cormen</a>, <a href="/w/index.php?title=Charles_E._Leiserson&action=edit&redlink=1" class="new" title="Charles E. Leiserson (trang không tồn tại)">Charles E. Leiserson</a>, <a href="/w/index.php?title=Ronald_L._Rivest&action=edit&redlink=1" class="new" title="Ronald L. Rivest (trang không tồn tại)">Ronald L. Rivest</a>, and <a href="/w/index.php?title=Clifford_Stein&action=edit&redlink=1" class="new" title="Clifford Stein (trang không tồn tại)">Clifford Stein</a>. <a href="/w/index.php?title=Introduction_to_Algorithms&action=edit&redlink=1" class="new" title="Introduction to Algorithms (trang không tồn tại)">Introduction to Algorithms</a>, Second Edition. MIT Press and McGraw-Hill, 2001. <a href="/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0262032937" class="internal mw-magiclink-isbn">ISBN 0-262-03293-7</a>. Chapter 12: Binary search trees, pp. 253–272. Section 15.5: Optimal binary search trees, pp. 356–363.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Liên_kết_ngoài">Liên kết ngoài</h2>[<a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&veaction=edit&section=13" title="Sửa đổi phần “Liên kết ngoài”" class="mw-editsection-visualeditor">sửa</a> | <a href="/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&action=edit&section=13" title="Sửa mã nguồn tại đề mục: Liên kết ngoài">sửa mã nguồn</a>]</div> <ul><li><a rel="nofollow" class="external autonumber" href="http://www.math.hcmuns.edu.vn/~tatuana/Cau%20Truc%20Du%20Lieu/Bai4.doc">[1]</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20090320042136/http://www.math.hcmuns.edu.vn/~tatuana/Cau%20Truc%20Du%20Lieu/Bai4.doc">Lưu trữ</a> 2009-03-20 tại <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li> <li><a rel="nofollow" class="external text" href="http://jdserver.homelinux.org/wiki/Binary_Search_Tree">Full source code to an efficient implementation in C++</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100328221436/http://jdserver.homelinux.org/wiki/Binary_Search_Tree">Lưu trữ</a> 2010-03-28 tại <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li> <li><a rel="nofollow" class="external text" href="https://wiki.portugal-a-programar.org/c:snippet:binary_search_tree">Implementation of Binary Search Trees in C</a></li> <li><a rel="nofollow" class="external text" href="http://cg.scs.carleton.ca/~dana/pbst">Implementation of a Persistent Binary Search Tree in C</a></li> <li><a rel="nofollow" class="external text" href="http://www.24bytes.com/Binary-Search-Tree.html">Implementation of Binary Search Trees in Java</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100309210259/http://www.24bytes.com/Binary-Search-Tree.html">Lưu trữ</a> 2010-03-09 tại <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li> <li><a rel="nofollow" class="external text" href="http://www.goletas.com/solutions/collections/">Iterative Implementation of Binary Search Trees in C#</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20080613224658/http://www.goletas.com/solutions/collections/">Lưu trữ</a> 2008-06-13 tại <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li> <li><a rel="nofollow" class="external text" href="http://cslibrary.stanford.edu/110/">An introduction to binary trees from Stanford</a></li> <li><a rel="nofollow" class="external text" href="http://www.nist.gov/dads/HTML/binarySearchTree.html">Dictionary of Algorithms and Data Structures - Binary Search Tree</a></li> <li><a rel="nofollow" class="external text" href="http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/286239">Binary Search Tree Example in Python</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20080531054333/http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/286239">Lưu trữ</a> 2008-05-31 tại <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li> <li><a rel="nofollow" class="external text" href="http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm">Java Model illustrating the behaviour of binary search trees(In JAVA Applet)</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20050801080205/http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm">Lưu trữ</a> 2005-08-01 tại <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li> <li><a rel="nofollow" class="external text" href="http://nova.umuc.edu/~jarc/idsv/lesson1.html">Interactive Data Structure Visualizations - Binary Tree Traversals</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20140227082917/http://nova.umuc.edu/~jarc/idsv/lesson1.html">Lưu trữ</a> 2014-02-27 tại <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li> <li><a rel="nofollow" class="external text" href="http://en.literateprograms.org/Category:Binary_search_tree">Literate implementations of binary search trees in various languages</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170421105424/http://en.literateprograms.org/Category:Binary_search_tree">Lưu trữ</a> 2017-04-21 tại <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a> on LiteratePrograms</li> <li><a rel="nofollow" class="external text" href="http://people.ksp.sk/~kuko/bak/index.html">BST Tree Applet</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20150304195520/http://people.ksp.sk/~kuko/bak/index.html">Lưu trữ</a> 2015-03-04 tại <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a> by Kubo Kovac</li> <li><a rel="nofollow" class="external text" href="http://www.algolist.net/Data_structures/Binary_search_tree">Well-illustrated explanation of binary search tree. Implementations in Java and C++</a></li></ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Lấy từ “<a dir="ltr" href="https://vi.wikipedia.org/w/index.php?title=Cây_tìm_kiếm_nhị_phân&oldid=71839321">https://vi.wikipedia.org/w/index.php?title=Cây_tìm_kiếm_nhị_phân&oldid=71839321</a>”</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Th%E1%BB%83_lo%E1%BA%A1i" title="Đặc biệt:Thể loại">Thể loại</a>: <ul><li><a href="/wiki/Th%E1%BB%83_lo%E1%BA%A1i:C%C3%A2y_(c%E1%BA%A5u_tr%C3%BAc)" title="Thể loại:Cây (cấu trúc)">Cây (cấu trúc)</a></li><li><a href="/wiki/Th%E1%BB%83_lo%E1%BA%A1i:Ki%E1%BB%83u_d%E1%BB%AF_li%E1%BB%87u" title="Thể loại:Kiểu dữ liệu">Kiểu dữ liệu</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Thể loại ẩn: <ul><li><a href="/wiki/Th%E1%BB%83_lo%E1%BA%A1i:B%E1%BA%A3n_m%E1%BA%ABu_webarchive_d%C3%B9ng_li%C3%AAn_k%E1%BA%BFt_wayback" title="Thể loại:Bản mẫu webarchive dùng liên kết wayback">Bản mẫu webarchive dùng liên kết wayback</a></li><li><a href="/wiki/Th%E1%BB%83_lo%E1%BA%A1i:Trang_s%E1%BB%AD_d%E1%BB%A5ng_li%C3%AAn_k%E1%BA%BFt_t%E1%BB%B1_%C4%91%E1%BB%99ng_ISBN" title="Thể loại:Trang sử dụng liên kết tự động ISBN">Trang sử dụng liên kết tự động ISBN</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"> Trang này được sửa đổi lần cuối vào ngày 4 tháng 10 năm 2024, 23:42.</li> <li id="footer-info-copyright">Văn bản được phát hành theo <a href="/wiki/Wikipedia:Nguy%C3%AAn_v%C4%83n_Gi%E1%BA%A5y_ph%C3%A9p_Creative_Commons_Ghi_c%C3%B4ng%E2%80%93Chia_s%E1%BA%BB_t%C6%B0%C6%A1ng_t%E1%BB%B1_phi%C3%AAn_b%E1%BA%A3n_4.0_Qu%E1%BB%91c_t%E1%BA%BF" title="Wikipedia:Nguyên văn Giấy phép Creative Commons Ghi công–Chia sẻ tương tự phiên bản 4.0 Quốc tế">Giấy phép Creative Commons Ghi công–Chia sẻ tương tự</a>; có thể áp dụng điều khoản bổ sung. Với việc sử dụng trang web này, bạn chấp nhận <a class="external text" href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use/vi">Điều khoản Sử dụng</a> và <a class="external text" href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/vi">Quy định quyền riêng tư</a>. Wikipedia® là thương hiệu đã đăng ký của <a rel="nofollow" class="external text" href="https://www.wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, một tổ chức phi lợi nhuận.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Quy định quyền riêng tư</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:Gi%E1%BB%9Bi_thi%E1%BB%87u">Giới thiệu Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:Ph%E1%BB%A7_nh%E1%BA%ADn_chung">Lời phủ nhận</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Bộ Quy tắc Ứng xử Chung</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Lập trình viên</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/vi.wikipedia.org">Thống kê</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Tuyên bố về cookie</a></li> <li id="footer-places-mobileview"><a href="//vi.m.wikipedia.org/w/index.php?title=C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Phiên bản di động</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" lang="en" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"> Tìm kiếm </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Tìm kiếm trên Wikipedia"> </div> <input type="hidden" name="title" value="Đặc_biệt:Tìm_kiếm"> </div> <button class="cdx-button cdx-search-input__end-button">Tìm kiếm</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Nội dung" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Đóng mở mục lục" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" > Đóng mở mục lục </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" >Cây tìm kiếm nhị phân</div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"> 34 ngôn ngữ </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"> Thêm đề tài </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-b766959bd-knq98","wgBackendResponseTime":126,"wgPageParseReport":{"limitreport":{"cputime":"0.138","walltime":"0.553","ppvisitednodes":{"value":252,"limit":1000000},"postexpandincludesize":{"value":4015,"limit":2097152},"templateargumentsize":{"value":0,"limit":2097152},"expansiondepth":{"value":5,"limit":100},"expensivefunctioncount":{"value":5,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":32158,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 43.800 1 -total"," 67.39% 29.515 9 Bản_mẫu:Webarchive"," 30.48% 13.350 1 Bản_mẫu:Tham_khảo"]},"scribunto":{"limitreport-timeusage":{"value":"0.013","limit":"10.000"},"limitreport-memusage":{"value":1052080,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-5d75d7759c-dlh9p","timestamp":"20250210100446","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"C\u00e2y t\u00ecm ki\u1ebfm nh\u1ecb ph\u00e2n","url":"https:\/\/vi.wikipedia.org\/wiki\/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n","sameAs":"http:\/\/www.wikidata.org\/entity\/Q623818","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q623818","author":{"@type":"Organization","name":"Nh\u1eefng ng\u01b0\u1eddi \u0111\u00f3ng g\u00f3p v\u00e0o c\u00e1c d\u1ef1 \u00e1n Wikimedia"},"publisher":{"@type":"Organization","name":"Qu\u1ef9 Wikimedia","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2006-10-30T17:23:30Z","dateModified":"2024-10-04T23:42:00Z"}</script> </body> </html>