CINXE.COM

<!DOCTYPE html> <html class="client-nojs" lang="ru" dir="ltr"> <head> <meta charset="UTF-8"> <title>Двоичное дерево поиска — Википедия</title> <script>(function(){var className="client-js";var cookie=document.cookie.match(/(?:^|; )ruwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":[",\t."," \t,"],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy","wgMonthNames":["","январь","февраль","март","апрель","май","июнь","июль","август","сентябрь","октябрь","ноябрь","декабрь"],"wgRequestId":"585d5c56-052b-4af2-a655-aff9a0375768","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Двоичное_дерево_поиска","wgTitle":"Двоичное дерево поиска","wgCurRevisionId":140880039,"wgRevisionId":140880039, "wgArticleId":259353,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Википедия:Статьи со ссылками на элементы Викиданных без русской подписи","ПРО:ИТ:Статьи по алфавиту","ПРО:ИТ:Последняя правка: в прошлом году","Википедия:Статьи с незавершёнными разделами","Википедия:Статьи с незавершёнными разделами без указанной даты","Википедия:Статьи с шаблонами недостатков по алфавиту","Википедия:Стилистически некорректные статьи","Википедия:Статьи, требующие оформления математических формул","Википедия:Статьи с проблемами в оформлении", "Википедия:Статьи без ссылок на источники","Википедия:Статьи без источников (не распределённые по типам)","Деревья (структуры данных)","Алгоритмы"],"wgPageViewLanguage":"ru","wgPageContentLanguage":"ru","wgPageContentModel":"wikitext","wgRelevantPageName":"Двоичное_дерево_поиска","wgRelevantArticleId":259353,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"accuracy":{"levels":1}}},"wgStableRevisionId":140880039,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"ru","pageLanguageDir":"ltr","pageVariantFallbacks":"ru"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true}, "wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":true,"wgVector2022LanguageInHeader":false,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q623818","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.gadget.common-site":"ready","ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","skins.vector.styles.legacy":"ready","ext.flaggedRevs.basic":"ready","mediawiki.codex.messagebox.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","codex-search-styles" :"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.scribunto.logs","site","mediawiki.page.ready","mediawiki.toc","skins.vector.legacy.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.flaggedRevs.advanced","ext.gadget.collapserefs","ext.gadget.directLinkToCommons","ext.gadget.referenceTooltips","ext.gadget.logo","ext.gadget.edittop","ext.gadget.navboxDefaultGadgets","ext.gadget.wikibugs","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.compactlinks","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","oojs-ui.styles.icons-media","oojs-ui-core.icons"];</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=ru&modules=codex-search-styles%7Cext.cite.styles%7Cext.flaggedRevs.basic%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cmediawiki.codex.messagebox.styles%7Cskins.vector.styles.legacy%7Cwikibase.client.init&only=styles&skin=vector"> <script async="" src="/w/load.php?lang=ru&modules=startup&only=scripts&raw=1&skin=vector"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=ru&modules=ext.gadget.common-site&only=styles&skin=vector"> <link rel="stylesheet" href="/w/load.php?lang=ru&modules=site.styles&only=styles&skin=vector"> <noscript><link rel="stylesheet" href="/w/load.php?lang=ru&modules=noscript&only=styles&skin=vector"></noscript> <meta name="generator" content="MediaWiki 1.44.0-wmf.16"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/1200px-Binary_search_tree.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1000"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/800px-Binary_search_tree.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="667"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/640px-Binary_search_tree.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="533"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Двоичное дерево поиска — Википедия"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//ru.m.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"> <link rel="alternate" type="application/x-wiki" title="Править" href="/w/index.php?title=%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&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="Википедия (ru)"> <link rel="EditURI" type="application/rsd+xml" href="//ru.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" 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"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.ru"> <link rel="alternate" type="application/atom+xml" title="Википедия — Atom-лента" href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%B2%D0%B5%D0%B6%D0%B8%D0%B5_%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B8&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin-vector-legacy mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Двоичное_дерево_поиска rootpage-Двоичное_дерево_поиска skin-vector action-view"><div id="mw-page-base" class="noprint"></div> <div id="mw-head-base" class="noprint"></div> <div id="content" class="mw-body" role="main"> <a id="top"></a> <div id="siteNotice"></div> <div class="mw-indicators"> </div> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Двоичное дерево поиска</span></h1> <div id="bodyContent" class="vector-body"> <div id="siteSub" class="noprint">Материал из Википедии — свободной энциклопедии</div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="contentSub2"></div> <div id="jump-to-nav"></div> <a class="mw-jump-link" href="#mw-head">Перейти к навигации</a> <a class="mw-jump-link" href="#searchInput">Перейти к поиску</a> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="ru" dir="ltr"><table class="infobox infobox-b3ae3587ab37bb72" style="" data-name="Структура данных"><tbody><tr><th colspan="2" scope="colgroup" class="infobox-above" style="">Двоичное дерево поиска</th></tr><tr><td colspan="2" class="infobox-image" style=""> <span data-wikidata-claim-id="Q623818$fb67376f-470d-b5c8-eafc-124a58723204" class="wikidata-claim" data-wikidata-property-id="P18"><span class="wikidata-snak wikidata-main-snak"><span typeof="mw:File/Frameless"><a href="/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Binary_search_tree.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/274px-Binary_search_tree.svg.png" decoding="async" width="274" height="228" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/411px-Binary_search_tree.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/548px-Binary_search_tree.svg.png 2x" data-file-width="300" data-file-height="250" /></a></span></span></span> </td></tr> <tr> <th scope="row" class="plainlist">Тип</th> <td class="plainlist"> <span data-wikidata-property-id="P31" class="no-wikidata">дерево</span></td> </tr> <tr> <th scope="row" class="plainlist">Год изобретения</th> <td class="plainlist"> <span data-wikidata-claim-id="Q623818$E117A9B0-E5E6-49C4-98E4-97DC4F8B131E" class="wikidata-claim" data-wikidata-property-id="P575"><span class="wikidata-snak wikidata-main-snak"><span class="nowrap"><a href="/wiki/1960_%D0%B3%D0%BE%D0%B4" title="1960 год">1960</a></span></span></span></td> </tr> <tr> <th scope="row" class="plainlist">Автор</th> <td class="plainlist"> <span data-wikidata-claim-id="Q623818$af9913c6-4300-76ba-ab41-84b161a5c5f9" class="wikidata-claim" data-wikidata-property-id="P61"><span class="wikidata-snak wikidata-main-snak"><span lang="en"><style data-mw-deduplicate="TemplateStyles:r138326222">.mw-parser-output .ts-Wikidata-redLink a{background:none;padding:0}.mw-parser-output .ts-Wikidata-redLink a.external{color:#ba0000;color:var(--color-link-red,#ba0000)}.mw-parser-output .ts-Wikidata-redLink a.external:visited{color:#a55858;color:var(--color-link-red--visited,#a55858)}</style><span class="ts-Wikidata-redLink plainlinks"><a class="external text" href="https://ru.wikipedia.org/w/index.php?title=Andrew_Donald_Booth&action=edit&editintro=T:Нет_статьи/editintro&preload=T:Нет_статьи/preload&preloadparams%5B%5D=Q3090592&preloadparams%5B%5D=Andrew+Donald+Booth&preloadparams%5B%5D=%D0%9F%D0%B5%D1%80%D1%81%D0%BE%D0%BD%D0%B0">Andrew Donald Booth</a></span><sup class="noprint"><a href="https://www.wikidata.org/wiki/Q3090592#sitelinks-wikipedia" class="extiw" title="d:Q3090592"><span>[вд]</span></a></sup></span></span></span></td> </tr> <tr> <th colspan="2" scope="colgroup" class="infobox-header" style=""><a href="/wiki/%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C" title="Вычислительная сложность">Сложность</a> в <a href="/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D0%BC%D0%B0%D0%BB%D0%BE%D0%B5" title="«O» большое и «o» малое">О-символике</a></th> </tr> <tr> <td colspan="2" class="plainlist" style="text-align:center;padding-left:0; padding-right:0; text-align: left;"> <table style="padding:0; width:100%;"> <tbody><tr> <th> </th> <th>В среднем </th> <th>В худшем случае </th></tr> <tr> <th style="padding-left:0;">Расход памяти </th> <td>O(n) </td> <td>O(n) </td></tr> <tr> <th style="padding-left:0;">Поиск </th> <td>O(log n) </td> <td>O(n) </td></tr> <tr> <th style="padding-left:0;">Вставка </th> <td>O(log n) </td> <td>O(n) </td></tr> <tr> <th style="padding-left:0;">Удаление </th> <td>O(log n) </td> <td>O(n) </td></tr></tbody></table></td> </tr><tr><td colspan="2" class="infobox-below" style=";"><span data-wikidata-claim-id="Q623818$293711d4-4d35-c985-a9c2-a1ed166dedec" class="wikidata-claim" data-wikidata-property-id="P373"><span class="wikidata-snak wikidata-main-snak"><span typeof="mw:File"><a href="https://commons.wikimedia.org/wiki/Category:Binary_search_trees" title="commons:Category:Binary search trees"><img alt="Логотип Викисклада" src="//upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/15px-Commons-logo.svg.png" decoding="async" width="15" height="20" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/23px-Commons-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png 2x" data-file-width="1024" data-file-height="1376" /></a></span> <a href="https://commons.wikimedia.org/wiki/Category:Binary_search_trees" class="extiw" title="commons:Category:Binary search trees">Медиафайлы на Викискладе</a></span></span></td></tr> </tbody></table> <p><b>Двоичное дерево поиска</b> (<a href="/wiki/%D0%90%D0%BD%D0%B3%D0%BB%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA" title="Английский язык">англ.</a> <span lang="en" style="font-style:italic;">binary search tree</span>, BST) — <a href="/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" title="Двоичное дерево">двоичное дерево</a>, для которого выполняются следующие дополнительные условия (<i>свойства дерева поиска</i>): </p> <ul><li>оба поддерева — левое и правое — являются двоичными деревьями поиска;</li> <li>у всех узлов <i>левого</i> поддерева произвольного узла X значения ключей данных <i>меньше либо равны</i>, нежели значение ключа данных самого узла X;</li> <li>у всех узлов <i>правого</i> поддерева произвольного узла X значения ключей данных <i>больше</i>, нежели значение ключа данных самого узла X.</li></ul> <p>Очевидно, данные в каждом узле должны обладать ключами, на которых определена операция сравнения <i>меньше либо равно</i>. </p><p>Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных. Однако это касается реализации, а не природы двоичного дерева поиска. </p><p>Для целей реализации двоичное дерево поиска можно определить так: </p> <ul><li>Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные, привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла — левый и правый сыновья соответственно. Для оптимизации алгоритмов конкретные реализации предполагают также определения поля parent в каждом узле (кроме корневого) — ссылки на родительский элемент.</li> <li>Данные (data) обладают ключом (key), на котором определена операция сравнения «меньше». В конкретных реализациях это может быть пара (key, value) — (ключ, значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё.</li> <li>Для любого узла X выполняются свойства дерева поиска: key[left[X]] ≤ key[X] < key[right[X]], то есть ключи данных родительского узла нестрого больше ключей данных левого сына и меньше ключей данных правого.</li></ul> <p>Двоичное дерево поиска не следует путать с <a href="/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%B0%D1%8F_%D0%BA%D1%83%D1%87%D0%B0" title="Двоичная куча">двоичной кучей</a>, построенной по другим правилам. </p><p>Основным преимуществом двоичного дерева поиска перед другими <a href="/wiki/%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85" title="Структура данных">структурами данных</a> является возможная высокая эффективность реализации основанных на нём алгоритмов <a href="/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85" title="Поиск данных">поиска</a> и <a href="/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8" title="Алгоритм сортировки">сортировки</a>. </p><p>Двоичное дерево поиска применяется для построения более абстрактных структур, таких, как <a href="/wiki/%D0%9C%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE_(%D1%82%D0%B8%D0%BF_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" title="Множество (тип данных)">множества</a>, <a href="/wiki/%D0%9C%D1%83%D0%BB%D1%8C%D1%82%D0%B8%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE" title="Мультимножество">мультимножества</a>, <a href="/wiki/%D0%90%D1%81%D1%81%D0%BE%D1%86%D0%B8%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2" title="Ассоциативный массив">ассоциативные массивы</a>. </p> <div id="toc" class="toc" role="navigation" aria-labelledby="mw-toc-heading"><input type="checkbox" role="button" id="toctogglecheckbox" class="toctogglecheckbox" style="display:none" /><div class="toctitle" lang="ru" dir="ltr"><h2 id="mw-toc-heading">Содержание</h2><span class="toctogglespan"><label class="toctogglelabel" for="toctogglecheckbox"></label></span></div> <ul> <li class="toclevel-1 tocsection-1"><a href="#Основные_операции_в_двоичном_дереве_поиска"><span class="tocnumber">1</span> <span class="toctext">Основные операции в двоичном дереве поиска</span></a> <ul> <li class="toclevel-2 tocsection-2"><a href="#Поиск_элемента_(FIND)"><span class="tocnumber">1.1</span> <span class="toctext">Поиск элемента (FIND)</span></a></li> <li class="toclevel-2 tocsection-3"><a href="#Добавление_элемента_(INSERT)"><span class="tocnumber">1.2</span> <span class="toctext">Добавление элемента (INSERT)</span></a></li> <li class="toclevel-2 tocsection-4"><a href="#Удаление_узла_(REMOVE)"><span class="tocnumber">1.3</span> <span class="toctext">Удаление узла (REMOVE)</span></a></li> <li class="toclevel-2 tocsection-5"><a href="#Обход_дерева_(TRAVERSE)"><span class="tocnumber">1.4</span> <span class="toctext">Обход дерева (TRAVERSE)</span></a></li> <li class="toclevel-2 tocsection-6"><a href="#Разбиение_дерева_по_ключу"><span class="tocnumber">1.5</span> <span class="toctext">Разбиение дерева по ключу</span></a></li> <li class="toclevel-2 tocsection-7"><a href="#Объединение_двух_деревьев_в_одно"><span class="tocnumber">1.6</span> <span class="toctext">Объединение двух деревьев в одно</span></a></li> </ul> </li> <li class="toclevel-1 tocsection-8"><a href="#Балансировка_дерева"><span class="tocnumber">2</span> <span class="toctext">Балансировка дерева</span></a></li> <li class="toclevel-1 tocsection-9"><a href="#См._также"><span class="tocnumber">3</span> <span class="toctext">См. также</span></a></li> <li class="toclevel-1 tocsection-10"><a href="#Примечания"><span class="tocnumber">4</span> <span class="toctext">Примечания</span></a></li> </ul> </div> <div class="mw-heading mw-heading2"><h2 id="Основные_операции_в_двоичном_дереве_поиска"><span id=".D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D0.B5.D1.80.D0.B0.D1.86.D0.B8.D0.B8_.D0.B2_.D0.B4.D0.B2.D0.BE.D0.B8.D1.87.D0.BD.D0.BE.D0.BC_.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.B5_.D0.BF.D0.BE.D0.B8.D1.81.D0.BA.D0.B0"></span>Основные операции в двоичном дереве поиска</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%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&veaction=edit&section=1" title="Редактировать раздел «Основные операции в двоичном дереве поиска»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=%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&action=edit&section=1" title="Редактировать код раздела «Основные операции в двоичном дереве поиска»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Базовый интерфейс двоичного дерева поиска состоит из трёх операций: </p> <ul><li>FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K.</li> <li>INSERT(K, V) — добавление в дерево пары (key, value) = (K, V).</li> <li>REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key = K.</li></ul> <p>Этот абстрактный интерфейс является общим случаем, например, таких интерфейсов, взятых из прикладных задач: </p> <ul><li>«Телефонная книжка» — хранилище записей (имя человека, его телефон) с операциями поиска и удаления записей по имени человека и операцией добавления новой записи.</li> <li>Domain Name Server — хранилище пар (доменное имя, IP адрес) с операциями модификации и поиска.</li> <li>Namespace — хранилище имён переменных с их значениями, возникающее в трансляторах языков программирования.</li></ul> <p>По сути, двоичное дерево поиска — это структура данных, способная хранить таблицу пар (key, value) и поддерживающая три операции: FIND, INSERT, REMOVE. </p><p>Кроме того, интерфейс двоичного дерева включает ещё три дополнительных операции обхода узлов дерева: INFIX_TRAVERSE, PREFIX_TRAVERSE и POSTFIX_TRAVERSE. Первая из них позволяет обойти узлы дерева в порядке неубывания ключей. </p> <div class="mw-heading mw-heading3"><h3 id="Поиск_элемента_(FIND)"><span id=".D0.9F.D0.BE.D0.B8.D1.81.D0.BA_.D1.8D.D0.BB.D0.B5.D0.BC.D0.B5.D0.BD.D1.82.D0.B0_.28FIND.29"></span>Поиск элемента (FIND)</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%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&veaction=edit&section=2" title="Редактировать раздел «Поиск элемента (FIND)»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=%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&action=edit&section=2" title="Редактировать код раздела «Поиск элемента (FIND)»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>Дано</b>: дерево Т и ключ K. </p><p><b>Задача</b>: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел. </p><p><b>Алгоритм</b>: </p> <ul><li>Если дерево пусто, сообщить, что узел не найден, и остановиться.</li> <li>Иначе сравнить K со значением ключа корневого узла X. <ul><li>Если K=X, выдать ссылку на этот узел и остановиться.</li> <li>Если K>X, рекурсивно искать ключ K в правом поддереве Т.</li> <li>Если K<X, рекурсивно искать ключ K в левом поддереве Т.</li></ul></li></ul> <div class="mw-heading mw-heading3"><h3 id="Добавление_элемента_(INSERT)"><span id=".D0.94.D0.BE.D0.B1.D0.B0.D0.B2.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1.8D.D0.BB.D0.B5.D0.BC.D0.B5.D0.BD.D1.82.D0.B0_.28INSERT.29"></span>Добавление элемента (INSERT)</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%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&veaction=edit&section=3" title="Редактировать раздел «Добавление элемента (INSERT)»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=%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&action=edit&section=3" title="Редактировать код раздела «Добавление элемента (INSERT)»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>Дано</b>: дерево Т и пара (K, V). </p><p><b>Задача</b>: вставить пару (K, V) в дерево Т (при совпадении K, заменить V). </p><p><b>Алгоритм</b>: </p> <ul><li>Если дерево пусто, заменить его на дерево с одним корневым узлом ((K, V), null, null) и остановиться.</li> <li>Иначе сравнить K с ключом корневого узла X. <ul><li>Если K>X, рекурсивно добавить (K, V) в правое поддерево Т.</li> <li>Если K<X, рекурсивно добавить (K, V) в левое поддерево Т.</li> <li>Если K=X, заменить V текущего узла новым значением.</li></ul></li></ul> <div class="mw-heading mw-heading3"><h3 id="Удаление_узла_(REMOVE)"><span id=".D0.A3.D0.B4.D0.B0.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1.83.D0.B7.D0.BB.D0.B0_.28REMOVE.29"></span>Удаление узла (REMOVE)</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%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&veaction=edit&section=4" title="Редактировать раздел «Удаление узла (REMOVE)»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=%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&action=edit&section=4" title="Редактировать код раздела «Удаление узла (REMOVE)»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>Дано</b>: дерево Т с корнем <tt>n</tt> и ключом K. </p><p><b>Задача</b>: удалить из дерева Т узел с ключом K (если такой есть). </p><p><b>Алгоритм</b>: </p> <ul><li>Если дерево T пусто, остановиться;</li> <li>Иначе сравнить K с ключом X корневого узла <tt>n</tt>. <ul><li>Если K>X, рекурсивно удалить K из правого поддерева Т;</li> <li>Если K<X, рекурсивно удалить K из левого поддерева Т;</li> <li>Если K=X, то необходимо рассмотреть три случая. <ul><li>Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла;</li> <li>Если одного из детей нет, то значения полей ребёнка <tt>m</tt> ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом <tt>m</tt>;</li> <li>Если оба ребёнка присутствуют, то <ul><li>Если левый узел <tt>m</tt> правого поддерева отсутствует (n->right->left) <ul><li>Копируем из правого узла в удаляемый поля K, V и ссылку на правый узел правого потомка.</li></ul></li> <li>Иначе <ul><li>Возьмём самый левый узел <tt>m</tt>, правого поддерева n->right;</li> <li>Скопируем данные (кроме ссылок на дочерние элементы) из <tt>m</tt> в <tt>n</tt>;</li> <li>Рекурсивно удалим узел <tt>m</tt>.</li></ul></li></ul></li></ul></li></ul></li></ul> <div class="mw-heading mw-heading3"><h3 id="Обход_дерева_(TRAVERSE)"><span id=".D0.9E.D0.B1.D1.85.D0.BE.D0.B4_.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.B0_.28TRAVERSE.29"></span>Обход дерева (TRAVERSE)</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%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&veaction=edit&section=5" title="Редактировать раздел «Обход дерева (TRAVERSE)»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=%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&action=edit&section=5" title="Редактировать код раздела «Обход дерева (TRAVERSE)»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов. </p><p>Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем <a href="/wiki/Callback_(%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5)" title="Callback (программирование)">функцию обратного вызова</a> f, операндом которой является адрес узла. Эта функция обычно работает только с парой (K, V), хранящейся в узле. Операция INFIX_TRAVERSE может быть реализована рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева. </p> <ul><li>INFIX_TRAVERSE (tr) — обойти всё дерево, следуя порядку (левое поддерево, <b>вершина</b>, правое поддерево). Элементы по возрастанию</li> <li>PREFIX_TRAVERSE (tr) — обойти всё дерево, следуя порядку (<b>вершина</b>, левое поддерево, правое поддерево). Элементы, как в дереве</li> <li>POSTFIX_TRAVERSE (tr) — обойти всё дерево, следуя порядку (левое поддерево, правое поддерево, <b>вершина</b>). Элементы в обратном порядке, как в дереве</li></ul> <p>В других источниках эти функции именуются inorder, preorder, postorder соответственно<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p><p><br /> </p> <dl><dt>INFIX_TRAVERSE</dt> <dd></dd></dl> <p><b>Дано</b>: дерево Т и функция f </p><p><b>Задача</b>: применить f ко всем узлам дерева Т в порядке возрастания ключей </p><p><b>Алгоритм</b>: </p> <ul><li>Если дерево пусто, остановиться.</li> <li>Иначе <ul><li>Рекурсивно обойти левое поддерево Т.</li> <li>Применить функцию f к корневому узлу.</li> <li>Рекурсивно обойти правое поддерево Т.</li></ul></li></ul> <p>В простейшем случае функция f может выводить значение пары (K, V). При использовании операции INFIX_TRAVERSE будут выведены все пары в порядке возрастания ключей. Если же использовать PREFIX_TRAVERSE, то пары будут выведены в порядке, соответствующем описанию дерева, приведённого в начале статьи. </p> <div class="mw-heading mw-heading3"><h3 id="Разбиение_дерева_по_ключу"><span id=".D0.A0.D0.B0.D0.B7.D0.B1.D0.B8.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.B0_.D0.BF.D0.BE_.D0.BA.D0.BB.D1.8E.D1.87.D1.83"></span>Разбиение дерева по ключу</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%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&veaction=edit&section=6" title="Редактировать раздел «Разбиение дерева по ключу»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=%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&action=edit&section=6" title="Редактировать код раздела «Разбиение дерева по ключу»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Операция «разбиение дерева по ключу» позволяет разбить одно дерево поиска на два: с ключами <<i>K</i><sub>0</sub> и ≥<i>K</i><sub>0</sub>. </p> <style data-mw-deduplicate="TemplateStyles:r137874932">.mw-parser-output .ambox{border:1px solid var(--border-color-base,#a2a9b1);border-left:10px solid #36c;background:var(--background-color-neutral-subtle,#f8f9fa);box-sizing:border-box;margin:0 10%}html body.mediawiki.skin-minerva .mw-parser-output .ambox{border-width:0 0 0 4px}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid var(--border-color-error,#b32424);background-color:var(--background-color-error-subtle,#fee7e6)}.mw-parser-output .ambox-delete{border-left:10px solid var(--border-color-error,#b32424)}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid var(--color-warning,#edab00)}.mw-parser-output .ambox-good{border-left:10px solid #66cc44}.mw-parser-output .ambox-discussion{border-left:10px solid #339966}.mw-parser-output .ambox-merge{border-left:10px solid #9932cc}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}.mw-parser-output .ambox .mbox-textsmall-div{font-size:90%}html.client-js body.skin-minerva .mw-parser-output .mbox-text-span{margin-left:23px!important}@media(max-width:1366px){.mw-parser-output .ambox{margin-left:6%;margin-right:6%}}@media(max-width:719px){.mw-parser-output .ambox{margin-left:0;margin-right:0}}</style><table class="mbox-Дополнить plainlinks metadata ambox ambox-content" role="presentation"><tbody><tr><td class="mbox-image"><div style="width:52px"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Wiki_letter_w.svg/40px-Wiki_letter_w.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Wiki_letter_w.svg/60px-Wiki_letter_w.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Wiki_letter_w.svg/80px-Wiki_letter_w.svg.png 2x" data-file-width="44" data-file-height="44" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-div">Этот раздел <b>нужно дополнить</b>.</div><div class="mbox-textsmall-div hide-when-compact"><span class="hide-when-compact"> Пожалуйста, <a class="external text" href="https://ru.wikipedia.org/w/index.php?title=%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&action=edit">улучшите</a> и дополните его.</span></div></td></tr></tbody></table> <div class="mw-heading mw-heading3"><h3 id="Объединение_двух_деревьев_в_одно"><span id=".D0.9E.D0.B1.D1.8A.D0.B5.D0.B4.D0.B8.D0.BD.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B4.D0.B2.D1.83.D1.85_.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D1.8C.D0.B5.D0.B2_.D0.B2_.D0.BE.D0.B4.D0.BD.D0.BE"></span>Объединение двух деревьев в одно</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%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&veaction=edit&section=7" title="Редактировать раздел «Объединение двух деревьев в одно»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=%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&action=edit&section=7" title="Редактировать код раздела «Объединение двух деревьев в одно»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Обратная операция: есть два дерева поиска, у одного ключи <<i>K</i><sub>0</sub>, у другого ≥<i>K</i><sub>0</sub>. Объединить их в одно дерево. </p><p>У нас есть два дерева: <i>T</i><sub>1</sub> (меньшее) и <i>T</i><sub>2</sub> (большее). Сначала нужно решить, откуда взять корень: из <i>T</i><sub>1</sub> или <i>T</i><sub>2</sub>. Стандартного метода нет, возможные варианты: </p> <ul><li>Взять наугад (см. <a href="/wiki/%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Декартово дерево">декартово дерево</a>).</li> <li>Если в каждом узле дерева поддерживается размер всей ветви (см. <a href="/w/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D1%81_%D0%BD%D0%B5%D1%8F%D0%B2%D0%BD%D1%8B%D0%BC_%D0%BA%D0%BB%D1%8E%D1%87%D0%BE%D0%BC&action=edit&redlink=1" class="new" title="Дерево с неявным ключом (страница отсутствует)">дерево с неявным ключом</a>), легко можно оценить дисбаланс для того и другого варианта.</li></ul> <pre>алг ОбъединениеДеревьев(T1, T2) если T1 пустое, вернуть T2 если T2 пустое, вернуть T1 если решили сделать корнем T1, то T = ОбъединениеДеревьев(T1.правое, T2) T1.правое = T вернуть T1 иначе T = ОбъединениеДеревьев(T1, T2.левое) T2.левое = T вернуть T2 </pre> <div class="mw-heading mw-heading2"><h2 id="Балансировка_дерева"><span id=".D0.91.D0.B0.D0.BB.D0.B0.D0.BD.D1.81.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B0_.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.B0"></span>Балансировка дерева</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%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&veaction=edit&section=8" title="Редактировать раздел «Балансировка дерева»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=%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&action=edit&section=8" title="Редактировать код раздела «Балансировка дерева»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Всегда желательно, чтобы все пути в дереве от корня до листьев имели примерно одинаковую длину, то есть чтобы глубина и левого, и правого поддеревьев была примерно одинакова в любом узле. В противном случае теряется производительность. </p><p>В вырожденном случае может оказаться, что всё левое дерево пусто на каждом уровне, есть только правые деревья, и в таком случае дерево вырождается в список (идущий вправо). Поиск (а значит, и удаление и добавление) в таком дереве по скорости равен поиску в списке и намного медленнее поиска в сбалансированном дереве. </p><p>Для балансировки дерева применяется операция «поворот дерева». Поворот налево выглядит так: </p><p><span class="mw-default-size" typeof="mw:File"><a href="/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:AVL_LR.GIF" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/ru/b/bc/AVL_LR.GIF" decoding="async" width="300" height="200" class="mw-file-element" data-file-width="300" data-file-height="200" /></a></span> </p> <ul><li>было Left(A) = L, Right(A) = B, Left(B) = C, Right(B) = R</li> <li>поворот меняет местами A и B, получая Left(A) = L, Right(A) = C, Left(B) = A, Right(B) = R</li> <li>также в узле Parent(A) меняется ссылка, ранее указывавшая на A, после поворота она указывает на B.</li></ul> <p>Поворот направо выглядит так же, достаточно заменить в вышеприведенном примере все Left на Right и обратно. Достаточно очевидно, что поворот не нарушает упорядоченность дерева и оказывает предсказуемое (+1 или −1) влияние на глубины всех затронутых поддеревьев. Для принятия решения о том, какие именно повороты нужно совершать после добавления или удаления, используются такие алгоритмы, как «<a href="/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" class="mw-redirect" title="Красно-черное дерево">красно-чёрное дерево</a>» и <a href="/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="АВЛ-дерево">АВЛ</a>. Оба они требуют дополнительной информации в узлах — 1 бит у красно-чёрного или знаковое число у АВЛ. Красно-чёрное дерево требует не более двух поворотов после добавления и не более трёх после удаления, но при этом худший дисбаланс может оказаться до 2 раз (самый длинный путь в 2 раза длиннее самого короткого). АВЛ-дерево требует не более двух поворотов после добавления и до глубины дерева после удаления, но при этом идеально сбалансировано (дисбаланс не более, чем на 1). </p> <div class="mw-heading mw-heading2"><h2 id="См._также"><span id=".D0.A1.D0.BC._.D1.82.D0.B0.D0.BA.D0.B6.D0.B5"></span>См. также</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%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&veaction=edit&section=9" title="Редактировать раздел «См. также»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=%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&action=edit&section=9" title="Редактировать код раздела «См. также»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/%D0%90%D1%81%D1%81%D0%BE%D1%86%D0%B8%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2" title="Ассоциативный массив">Ассоциативный массив</a></li> <li><a href="/wiki/%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Декартово дерево">Декартово дерево</a></li> <li><a href="/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81_%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0" title="Сортировка с помощью двоичного дерева">Сортировка с помощью двоичного дерева</a></li></ul> <p>Сбалансированные деревья: </p> <ul><li><a href="/wiki/B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="B-дерево">B-дерево</a></li> <li><a href="/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="АВЛ-дерево">АВЛ-дерево</a></li> <li><a href="/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D1%91%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Красно-чёрное дерево">Красно-чёрное дерево</a></li> <li><a href="/wiki/Splay-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Splay-дерево">Splay-дерево</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Примечания"><span id=".D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D1.87.D0.B0.D0.BD.D0.B8.D1.8F"></span>Примечания</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%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&veaction=edit&section=10" title="Редактировать раздел «Примечания»" class="mw-editsection-visualeditor"><span>править</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=%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&action=edit&section=10" title="Редактировать код раздела «Примечания»"><span>править код</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="reflist columns" style="list-style-type: decimal;"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text"><span class="citation"><i>Роман Акопов.</i> <span lang="und"><a rel="nofollow" class="external text" href="http://www.rsdn.ru/article/alg/binstree.xml">Двоичные деревья поиска</a></span><span class="hidden-ref" style="display:none;">  <small class="ref-info" style="cursor:help;" title="на неопределённом языке">(неопр.)</small></span>. RSDN Magazine #5-2003 (13 марта 2005). Дата обращения: 1 ноября 2014. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20141101224029/http://rsdn.ru/article/alg/binstree.xml">Архивировано</a> 1 ноября 2014 года.</span></span> </li> </ol></div></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r137874932"><table class="plainlinks metadata ambox ambox-style" role="presentation"><tbody><tr><td class="mbox-image"><div style="width:52px"><span typeof="mw:File"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9A%D0%B0%D0%BA_%D0%BF%D1%80%D0%B0%D0%B2%D0%B8%D1%82%D1%8C_%D1%81%D1%82%D0%B0%D1%82%D1%8C%D0%B8" title="Улучшение статьи"><img alt="Улучшение статьи" src="//upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Wiki_letter_w.svg/40px-Wiki_letter_w.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Wiki_letter_w.svg/60px-Wiki_letter_w.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/6c/Wiki_letter_w.svg/80px-Wiki_letter_w.svg.png 2x" data-file-width="44" data-file-height="44" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-div"><b>Для улучшения этой статьи <a href="/wiki/%D0%A8%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD:Rq/%D0%9F%D0%BE%D1%8F%D1%81%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F" title="Шаблон:Rq/Пояснения">желательно</a>:</b><ul style="margin-top: 0;"> <li>Исправить статью согласно <a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%AF%D0%B7%D1%8B%D0%BA_%D0%B8_%D1%81%D1%82%D0%B8%D0%BB%D1%8C" title="Википедия:Язык и стиль">стилистическим правилам Википедии</a>.</li><li>Оформить <a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D1%8B" title="Википедия:Формулы">математические формулы</a></li><li>Оформить статью по <a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9E%D1%84%D0%BE%D1%80%D0%BC%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81%D1%82%D0%B0%D1%82%D0%B5%D0%B9" title="Википедия:Оформление статей">правилам</a>.</li><li><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2" title="Википедия:Поиск источников">Найти</a> и оформить в виде <a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D0%BD%D0%BE%D1%81%D0%BA%D0%B8" title="Википедия:Сноски">сносок</a> ссылки на независимые <a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%90%D0%B2%D1%82%D0%BE%D1%80%D0%B8%D1%82%D0%B5%D1%82%D0%BD%D1%8B%D0%B5_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%B8" title="Википедия:Авторитетные источники">авторитетные источники</a>, <a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9F%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D1%8F%D0%B5%D0%BC%D0%BE%D1%81%D1%82%D1%8C" title="Википедия:Проверяемость">подтверждающие написанное</a>.</li></ul></div><div class="mbox-textsmall-div hide-when-compact">После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.</div></td></tr></tbody></table> <div role="navigation" class="navbox" aria-labelledby="Дерево_(структура_данных)" data-name="Деревья (структуры данных)"><table class="nowraplinks collapsible collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="colgroup" class="navbox-title" colspan="2"><span class="navbox-gear" style="float:left;text-align:left;width:5em;margin-right:0.5em"><span class="noprint skin-invert-image" typeof="mw:File"><a href="/wiki/%D0%A8%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD:%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D1%8F_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" title="Перейти к шаблону «Деревья (структуры данных)»"><img alt="Перейти к шаблону «Деревья (структуры данных)»" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/14px-Wikipedia_interwiki_section_gear_icon.svg.png" decoding="async" width="14" height="14" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/21px-Wikipedia_interwiki_section_gear_icon.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/28px-Wikipedia_interwiki_section_gear_icon.svg.png 2x" data-file-width="14" data-file-height="14" /></a></span></span><div id="Дерево_(структура_данных)" style="font-size:114%;margin:0 5em"><a href="/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" title="Дерево (структура данных)">Дерево (структура данных)</a></div></th></tr><tr><td class="navbox-abovebelow hlist" colspan="2"><div> <ul><li><a class="mw-selflink selflink">Двоичное дерево поиска</a></li> <li><a href="/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2)" title="Дерево (теория графов)">Дерево (теория графов)</a></li> <li><a href="/wiki/%D0%94%D1%80%D0%B5%D0%B2%D0%BE%D0%B2%D0%B8%D0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0" title="Древовидная структура">Древовидная структура</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px"><a href="/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" title="Двоичное дерево">Двоичные деревья</a></th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/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" title="Двоичное дерево">Двоичное дерево</a></li> <li><a href="/wiki/T-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="T-дерево">T-дерево</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px"><a href="/w/index.php?title=Self-balancing_binary_search_tree&action=edit&redlink=1" class="new" title="Self-balancing binary search tree (страница отсутствует)">Самобалансирующиеся<br /> двоичные деревья</a></th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/w/index.php?title=%D0%90%D0%90-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&action=edit&redlink=1" class="new" title="АА-дерево (страница отсутствует)">АА-дерево</a></li> <li><a href="/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="АВЛ-дерево">АВЛ-дерево</a></li> <li><a href="/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D1%91%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Красно-чёрное дерево">Красно-чёрное дерево</a></li> <li><a href="/wiki/Splay-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Splay-дерево">Splay-дерево</a></li> <li><a href="/w/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D1%81%D0%BE_%D1%88%D1%82%D1%80%D0%B0%D1%84%D0%B0%D0%BC%D0%B8&action=edit&redlink=1" class="new" title="Дерево со штрафами (страница отсутствует)">Дерево со штрафами</a></li> <li><a href="/wiki/%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Декартово дерево">Декартово дерево</a></li> <li><a href="/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8" title="Дерево Фибоначчи">Дерево Фибоначчи</a></li> <li><a href="/wiki/B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="B-дерево">B-дерево</a></li> <li><a href="/wiki/T-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="T-дерево">T-дерево</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px"><a href="/wiki/B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="B-дерево">B-деревья</a></th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/2-3-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="2-3-дерево">2-3-дерево</a></li> <li><a href="/wiki/B%E2%81%BA-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="B⁺-дерево">B⁺-дерево</a></li> <li><a href="/wiki/B*-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="B*-дерево">B*-дерево</a></li> <li><a href="/wiki/Bx-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Bx-дерево">B<sup>x</sup>-дерево</a></li> <li><a href="/wiki/UB-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="UB-дерево">UB-дерево</a></li> <li><a href="/w/index.php?title=2-3-4_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&action=edit&redlink=1" class="new" title="2-3-4 дерево (страница отсутствует)">2-3-4 дерево</a></li> <li><a href="/w/index.php?title=(a,b)-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&action=edit&redlink=1" class="new" title="(a,b)-дерево (страница отсутствует)">(a,b)-дерево</a></li> <li><a href="/wiki/%D0%A2%D0%B0%D0%BD%D1%86%D1%83%D1%8E%D1%89%D0%B5%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Танцующее дерево">Танцующее дерево</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px"><a href="/wiki/%D0%9F%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Префиксное дерево">Префиксные деревья</a></th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%A1%D1%83%D1%84%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Суффиксное дерево">Суффиксное дерево</a></li> <li><a href="/wiki/%D0%A1%D0%B6%D0%B0%D1%82%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Сжатое префиксное дерево">Сжатое префиксное дерево</a></li> <li><a href="/w/index.php?title=Ternary_search_tree&action=edit&redlink=1" class="new" title="Ternary search tree (страница отсутствует)">Ternary search tree</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px"><a href="/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%B0" title="Двоичное разбиение пространства">Двоичное разбиение<br /> пространства</a></th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/K-d-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="K-d-дерево">k-мерное дерево</a></li> <li><a href="/wiki/VP-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="VP-дерево">VP-дерево</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px">Недвоичные деревья</th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D0%BD%D1%82%D0%BE%D0%B2" title="Дерево квадрантов">Дерево квадрантов</a></li> <li><a href="/wiki/%D0%9E%D0%BA%D1%82%D0%BE%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Октодерево">Октодерево</a></li> <li><a href="/wiki/Sparse_Voxel_Octree" title="Sparse Voxel Octree">Sparse Voxel Octree</a></li> <li><a href="/w/index.php?title=%D0%AD%D0%BA%D1%81%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%86%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&action=edit&redlink=1" class="new" title="Экспоненциальное дерево (страница отсутствует)">Экспоненциальное дерево</a></li> <li><a href="/wiki/PQ-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="PQ-дерево">PQ-дерево</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px">Разбиение пространства</th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/R-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" title="R-дерево (структура данных)">R-дерево</a></li> <li><a href="/wiki/R-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%93%D0%B8%D0%BB%D1%8C%D0%B1%D0%B5%D1%80%D1%82%D0%B0" title="R-дерево Гильберта">R-дерево Гильберта</a></li> <li><a href="/w/index.php?title=R%2B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&action=edit&redlink=1" class="new" title="R+-дерево (страница отсутствует)">R+-дерево</a></li> <li><a href="/wiki/R*-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="R*-дерево">R*-дерево</a></li> <li><a href="/w/index.php?title=X-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&action=edit&redlink=1" class="new" title="X-дерево (страница отсутствует)">X-дерево</a></li> <li><a href="/w/index.php?title=M-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&action=edit&redlink=1" class="new" title="M-дерево (страница отсутствует)">M-дерево</a></li> <li><a href="/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%A4%D0%B5%D0%BD%D0%B2%D0%B8%D0%BA%D0%B0" title="Дерево Фенвика">Дерево Фенвика</a></li> <li><a href="/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2" title="Дерево отрезков">Дерево отрезков</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px">Другие деревья</th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%9A%D1%83%D1%87%D0%B0_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" title="Куча (структура данных)">Куча</a></li> <li><a href="/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D1%85%D0%B5%D1%88%D0%B5%D0%B9" title="Дерево хешей">Дерево хешей</a></li> <li><a href="/w/index.php?title=Finger_tree&action=edit&redlink=1" class="new" title="Finger tree (страница отсутствует)">Finger tree</a></li> <li><a href="/w/index.php?title=Metric_tree&action=edit&redlink=1" class="new" title="Metric tree (страница отсутствует)">Metric tree</a></li> <li><a href="/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D0%B9" title="Дерево покрытий">Дерево покрытий</a></li> <li><a href="/w/index.php?title=BK-tree&action=edit&redlink=1" class="new" title="BK-tree (страница отсутствует)">BK-tree</a></li> <li><a href="/w/index.php?title=Doubly-chained_tree&action=edit&redlink=1" class="new" title="Doubly-chained tree (страница отсутствует)">Doubly-chained tree</a></li> <li><a href="/w/index.php?title=IDistance&action=edit&redlink=1" class="new" title="IDistance (страница отсутствует)">iDistance</a></li> <li><a href="/w/index.php?title=Link-cut_tree&action=edit&redlink=1" class="new" title="Link-cut tree (страница отсутствует)">Link-cut tree</a></li> <li><a href="/wiki/LSM-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="LSM-дерево">LSM-дерево</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px">Алгоритмы</th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83" title="Поиск в ширину">Поиск в ширину</a></li> <li><a href="/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83" title="Поиск в глубину">Поиск в глубину</a></li> <li><a href="/w/index.php?title=DSW-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC&action=edit&redlink=1" class="new" title="DSW-алгоритм (страница отсутствует)">DSW-алгоритм</a></li> <li><a href="/wiki/%D0%9F%D1%80%D0%BE%D1%82%D0%BE%D0%BA%D0%BE%D0%BB_%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0" class="mw-redirect" title="Протокол остовного дерева">Протокол остовного дерева</a></li></ul> </div></td></tr></tbody></table></div> <div role="navigation" class="navbox" aria-labelledby="Структуры_данных" data-name="Структуры данных"><table class="nowraplinks collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="colgroup" class="navbox-title" colspan="2"><span class="navbox-gear" style="float:left;text-align:left;width:5em;margin-right:0.5em"><span class="noprint skin-invert-image" typeof="mw:File"><a href="/wiki/%D0%A8%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD:%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85" title="Перейти к шаблону «Структуры данных»"><img alt="Перейти к шаблону «Структуры данных»" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/14px-Wikipedia_interwiki_section_gear_icon.svg.png" decoding="async" width="14" height="14" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/21px-Wikipedia_interwiki_section_gear_icon.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/28px-Wikipedia_interwiki_section_gear_icon.svg.png 2x" data-file-width="14" data-file-height="14" /></a></span></span><div id="Структуры_данных" style="font-size:114%;margin:0 5em"><a href="/wiki/%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85" title="Структура данных">Структуры данных</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1px">Типы</th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%9A%D0%BE%D0%BB%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_(%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5)" title="Коллекция (программирование)">Коллекция</a></li> <li><a href="/wiki/%D0%9A%D0%BE%D0%BD%D1%82%D0%B5%D0%B9%D0%BD%D0%B5%D1%80_(%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5)" title="Контейнер (программирование)">Контейнер</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px"><a href="/wiki/%D0%90%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D1%8B%D0%B9_%D1%82%D0%B8%D0%BF_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85" title="Абстрактный тип данных">Абстрактные</a></th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%90%D1%81%D1%81%D0%BE%D1%86%D0%B8%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2" title="Ассоциативный массив">Ассоциативный массив</a> <ul><li><a href="/w/index.php?title=%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%B0%D1%81%D1%81%D0%BE%D1%86%D0%B8%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2&action=edit&redlink=1" class="new" title="Многомерный ассоциативный массив (страница отсутствует)">Многомерный ассоциативный массив</a></li></ul></li> <li><a href="/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)" title="Список (информатика)">Список</a></li> <li><a href="/wiki/%D0%A1%D1%82%D0%B5%D0%BA" title="Стек">Стек</a></li> <li><a href="/wiki/%D0%9E%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C_(%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5)" title="Очередь (программирование)">Очередь</a> <ul><li><a href="/wiki/%D0%94%D0%B2%D1%83%D1%85%D1%81%D1%82%D0%BE%D1%80%D0%BE%D0%BD%D0%BD%D1%8F%D1%8F_%D0%BE%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C" title="Двухсторонняя очередь">Двухсторонняя очередь</a></li></ul></li> <li><a href="/wiki/%D0%9E%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C_%D1%81_%D0%BF%D1%80%D0%B8%D0%BE%D1%80%D0%B8%D1%82%D0%B5%D1%82%D0%BE%D0%BC_(%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5)" title="Очередь с приоритетом (программирование)">Очередь с приоритетом</a> <ul><li><a href="/w/index.php?title=%D0%94%D0%B2%D1%83%D1%85%D1%81%D1%82%D0%BE%D1%80%D0%BE%D0%BD%D1%8F%D1%8F_%D0%BE%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C_%D1%81_%D0%BF%D1%80%D0%B8%D0%BE%D1%80%D0%B8%D1%82%D0%B5%D1%82%D0%BE%D0%BC&action=edit&redlink=1" class="new" title="Двухстороняя очередь с приоритетом (страница отсутствует)">Двухстороняя очередь с приоритетом</a></li></ul></li> <li><a href="/wiki/%D0%9C%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE_(%D1%82%D0%B8%D0%BF_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" title="Множество (тип данных)">Множество</a> <ul><li><a href="/wiki/%D0%9C%D1%83%D0%BB%D1%8C%D1%82%D0%B8%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE" title="Мультимножество">Мультимножество</a></li> <li><a href="/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BD%D0%B5%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D0%B5%D0%BA%D0%B0%D1%8E%D1%89%D0%B8%D1%85%D1%81%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2" title="Система непересекающихся множеств">Система непересекающихся множеств</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px"><a href="/wiki/%D0%9C%D0%B0%D1%81%D1%81%D0%B8%D0%B2_(%D1%82%D0%B8%D0%BF_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" title="Массив (тип данных)">Массив</a></th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%91%D0%B8%D1%82%D0%BE%D0%B2%D0%B0%D1%8F_%D0%BA%D0%B0%D1%80%D1%82%D0%B0" title="Битовая карта">Битовая карта</a></li> <li><a href="/wiki/%D0%9A%D0%BE%D0%BB%D1%8C%D1%86%D0%B5%D0%B2%D0%BE%D0%B9_%D0%B1%D1%83%D1%84%D0%B5%D1%80" title="Кольцевой буфер">Кольцевой буфер</a></li> <li><a href="/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2" title="Динамический массив">Динамический массив</a></li> <li><a href="/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0" title="Хеш-таблица">Хеш-таблица</a></li> <li><span data-interwiki-lang="en" data-interwiki-article="Hashed array tree"><a href="/w/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D1%85%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B&action=edit&redlink=1" class="new" title="Дерево хеш-таблицы (страница отсутствует)">Дерево хеш-таблицы</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/Hashed_array_tree" class="extiw" title="en:Hashed array tree"><span title="Hashed array tree — версия статьи «Дерево хеш-таблицы» на английском языке">[англ.]</span></a></sup></li> <li><a href="/wiki/%D0%A0%D0%B0%D0%B7%D1%80%D0%B5%D0%B6%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0" title="Разреженная матрица">Разреженная матрица</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px"><span data-interwiki-lang="en" data-interwiki-article="Linked data structure"><a href="/w/index.php?title=%D0%A1%D0%B2%D1%8F%D0%B7%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85&action=edit&redlink=1" class="new" title="Связная структура данных (страница отсутствует)">Связные</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/Linked_data_structure" class="extiw" title="en:Linked data structure"><span title="Linked data structure — версия статьи «Связная структура данных» на английском языке">[англ.]</span></a></sup></th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%90%D1%81%D1%81%D0%BE%D1%86%D0%B8%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA" class="mw-redirect" title="Ассоциативный список">Ассоциативный список</a></li> <li><a href="/wiki/%D0%A1%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA" title="Связный список">Связный список</a></li> <li><a href="/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D1%81_%D0%BF%D1%80%D0%BE%D0%BF%D1%83%D1%81%D0%BA%D0%B0%D0%BC%D0%B8" title="Список с пропусками">Список с пропусками</a></li> <li><a href="/wiki/%D0%A0%D0%B0%D0%B7%D0%B2%D1%91%D1%80%D0%BD%D1%83%D1%82%D1%8B%D0%B9_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA" title="Развёрнутый связный список">Развёрнутый связный список</a></li> <li><a href="/wiki/%D0%9E%D0%B4%D0%BD%D0%BE%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA" class="mw-redirect" title="Односвязный список">Односвязный список</a></li> <li><a href="/wiki/%D0%94%D0%B2%D1%83%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA" class="mw-redirect" title="Двусвязный список">Двусвязный список</a></li> <li><a href="/wiki/XOR-%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA" title="XOR-связный список">XOR-связный список</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px"><a href="/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" title="Дерево (структура данных)">Деревья</a></th><td class="navbox-list navbox-odd hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="B-дерево">B-дерево</a></li></ul> <ul><li><a class="mw-selflink selflink">Двоичное дерево поиска</a> <ul><li><span data-interwiki-lang="en" data-interwiki-article="AA tree"><a href="/w/index.php?title=AA-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&action=edit&redlink=1" class="new" title="AA-дерево (страница отсутствует)">AA-дерево</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/AA_tree" class="extiw" title="en:AA tree"><span title="AA tree — версия статьи «AA-дерево» на английском языке">[англ.]</span></a></sup></li> <li><a href="/wiki/AVL-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" class="mw-redirect" title="AVL-дерево">AVL-дерево</a></li> <li><a href="/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D1%91%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Красно-чёрное дерево">Красно-чёрное дерево</a></li> <li><span data-interwiki-lang="en" data-interwiki-article="Self-balancing binary search tree"><a href="/w/index.php?title=%D0%A1%D0%B0%D0%BC%D0%BE%D0%B1%D0%B0%D0%BB%D0%B0%D0%BD%D1%81%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B5%D0%B5%D1%81%D1%8F_%D0%B4%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&action=edit&redlink=1" class="new" title="Самобалансирующееся двоичное дерево поиска (страница отсутствует)">Самобалансирующееся двоичное дерево поиска</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree" class="extiw" title="en:Self-balancing binary search tree"><span title="Self-balancing binary search tree — версия статьи «Самобалансирующееся двоичное дерево поиска» на английском языке">[англ.]</span></a></sup></li> <li><a href="/wiki/Splay-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Splay-дерево">Splay-дерево</a></li></ul></li></ul> <ul><li><a href="/wiki/%D0%9A%D1%83%D1%87%D0%B0_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" title="Куча (структура данных)">Куча</a> <ul><li><a href="/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%B0%D1%8F_%D0%BA%D1%83%D1%87%D0%B0" title="Двоичная куча">Двоичная куча</a></li> <li><a href="/wiki/%D0%91%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%BA%D1%83%D1%87%D0%B0" title="Биномиальная куча">Биномиальная куча</a></li> <li><a href="/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0" title="Фибоначчиева куча">Фибоначчиева куча</a></li></ul></li></ul> <ul><li><a href="/wiki/R-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" title="R-дерево (структура данных)">R-дерево</a> <ul><li><a href="/wiki/R*-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="R*-дерево">R*-дерево</a></li> <li><span data-interwiki-lang="en" data-interwiki-article="R+ tree"><a href="/w/index.php?title=R%2B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE&action=edit&redlink=1" class="new" title="R+-дерево (страница отсутствует)">R+-дерево</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/R%2B_tree" class="extiw" title="en:R+ tree"><span title="R+ tree — версия статьи «R+-дерево» на английском языке">[англ.]</span></a></sup></li> <li><a href="/wiki/R-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%93%D0%B8%D0%BB%D1%8C%D0%B1%D0%B5%D1%80%D1%82%D0%B0" title="R-дерево Гильберта">R-дерево Гильберта</a></li></ul></li></ul> <ul><li><a href="/wiki/%D0%9F%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Префиксное дерево">Префиксное дерево</a> <ul><li><span data-interwiki-lang="en" data-interwiki-article="Hash tree (persistent data structure)"><a href="/w/index.php?title=Hash_tree&action=edit&redlink=1" class="new" title="Hash tree (страница отсутствует)">Hash tree</a></span><sup class="noprint" style="font-style:normal; font-weight:normal;"><a href="https://en.wikipedia.org/wiki/Hash_tree_(persistent_data_structure)" class="extiw" title="en:Hash tree (persistent data structure)"><span title="Hash tree (persistent data structure) — версия статьи «Hash tree» на английском языке">[англ.]</span></a></sup></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1px"><a href="/wiki/%D0%93%D1%80%D0%B0%D1%84_(%D1%82%D0%B8%D0%BF_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" class="mw-redirect" title="Граф (тип данных)">Графы</a></th><td class="navbox-list navbox-even hlist" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><a href="/wiki/%D0%91%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D0%B0%D1%8F_%D0%B4%D0%B8%D0%B0%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0_%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B9" title="Бинарная диаграмма решений">Бинарная диаграмма решений</a></li> <li><a href="/wiki/%D0%9E%D1%80%D0%B8%D0%B5%D0%BD%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84" title="Ориентированный граф">Ориентированный граф</a></li> <li><a href="/wiki/%D0%9E%D1%80%D0%B8%D0%B5%D0%BD%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D1%86%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B3%D1%80%D0%B0%D1%84" title="Ориентированный ациклический граф">Ориентированный ациклический граф</a></li> <li><a href="/wiki/%D0%93%D0%B8%D0%BF%D0%B5%D1%80%D0%B3%D1%80%D0%B0%D1%84" title="Гиперграф">Гиперграф</a></li></ul> </div></td></tr></tbody></table></div></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="">Источник — <a dir="ltr" href="https://ru.wikipedia.org/w/index.php?title=Двоичное_дерево_поиска&oldid=140880039">https://ru.wikipedia.org/w/index.php?title=Двоичное_дерево_поиска&oldid=140880039</a></div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D0%B8" title="Служебная:Категории">Категории</a>: <ul><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D1%8F_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)" title="Категория:Деревья (структуры данных)">Деревья (структуры данных)</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B" title="Категория:Алгоритмы">Алгоритмы</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Скрытые категории: <ul><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8_%D1%81%D0%BE_%D1%81%D1%81%D1%8B%D0%BB%D0%BA%D0%B0%D0%BC%D0%B8_%D0%BD%D0%B0_%D1%8D%D0%BB%D0%B5%D0%BC%D0%B5%D0%BD%D1%82%D1%8B_%D0%92%D0%B8%D0%BA%D0%B8%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D0%B1%D0%B5%D0%B7_%D1%80%D1%83%D1%81%D1%81%D0%BA%D0%BE%D0%B9_%D0%BF%D0%BE%D0%B4%D0%BF%D0%B8%D1%81%D0%B8" title="Категория:Википедия:Статьи со ссылками на элементы Викиданных без русской подписи">Википедия:Статьи со ссылками на элементы Викиданных без русской подписи</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%9F%D0%A0%D0%9E:%D0%98%D0%A2:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8_%D0%BF%D0%BE_%D0%B0%D0%BB%D1%84%D0%B0%D0%B2%D0%B8%D1%82%D1%83" title="Категория:ПРО:ИТ:Статьи по алфавиту">ПРО:ИТ:Статьи по алфавиту</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%9F%D0%A0%D0%9E:%D0%98%D0%A2:%D0%9F%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BD%D1%8F%D1%8F_%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B0:_%D0%B2_%D0%BF%D1%80%D0%BE%D1%88%D0%BB%D0%BE%D0%BC_%D0%B3%D0%BE%D0%B4%D1%83" title="Категория:ПРО:ИТ:Последняя правка: в прошлом году">ПРО:ИТ:Последняя правка: в прошлом году</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8_%D1%81_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B5%D1%80%D1%88%D1%91%D0%BD%D0%BD%D1%8B%D0%BC%D0%B8_%D1%80%D0%B0%D0%B7%D0%B4%D0%B5%D0%BB%D0%B0%D0%BC%D0%B8" title="Категория:Википедия:Статьи с незавершёнными разделами">Википедия:Статьи с незавершёнными разделами</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8_%D1%81_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B5%D1%80%D1%88%D1%91%D0%BD%D0%BD%D1%8B%D0%BC%D0%B8_%D1%80%D0%B0%D0%B7%D0%B4%D0%B5%D0%BB%D0%B0%D0%BC%D0%B8_%D0%B1%D0%B5%D0%B7_%D1%83%D0%BA%D0%B0%D0%B7%D0%B0%D0%BD%D0%BD%D0%BE%D0%B9_%D0%B4%D0%B0%D1%82%D1%8B" title="Категория:Википедия:Статьи с незавершёнными разделами без указанной даты">Википедия:Статьи с незавершёнными разделами без указанной даты</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8_%D1%81_%D1%88%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD%D0%B0%D0%BC%D0%B8_%D0%BD%D0%B5%D0%B4%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BA%D0%BE%D0%B2_%D0%BF%D0%BE_%D0%B0%D0%BB%D1%84%D0%B0%D0%B2%D0%B8%D1%82%D1%83" title="Категория:Википедия:Статьи с шаблонами недостатков по алфавиту">Википедия:Статьи с шаблонами недостатков по алфавиту</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B8%D0%BB%D0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8_%D0%BD%D0%B5%D0%BA%D0%BE%D1%80%D1%80%D0%B5%D0%BA%D1%82%D0%BD%D1%8B%D0%B5_%D1%81%D1%82%D0%B0%D1%82%D1%8C%D0%B8" title="Категория:Википедия:Стилистически некорректные статьи">Википедия:Стилистически некорректные статьи</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8,_%D1%82%D1%80%D0%B5%D0%B1%D1%83%D1%8E%D1%89%D0%B8%D0%B5_%D0%BE%D1%84%D0%BE%D1%80%D0%BC%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB" title="Категория:Википедия:Статьи, требующие оформления математических формул">Википедия:Статьи, требующие оформления математических формул</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8_%D1%81_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0%D0%BC%D0%B8_%D0%B2_%D0%BE%D1%84%D0%BE%D1%80%D0%BC%D0%BB%D0%B5%D0%BD%D0%B8%D0%B8" title="Категория:Википедия:Статьи с проблемами в оформлении">Википедия:Статьи с проблемами в оформлении</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8_%D0%B1%D0%B5%D0%B7_%D1%81%D1%81%D1%8B%D0%BB%D0%BE%D0%BA_%D0%BD%D0%B0_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%B8" title="Категория:Википедия:Статьи без ссылок на источники">Википедия:Статьи без ссылок на источники</a></li><li><a href="/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%82%D0%B0%D1%82%D1%8C%D0%B8_%D0%B1%D0%B5%D0%B7_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2_(%D0%BD%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D1%91%D0%BD%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE_%D1%82%D0%B8%D0%BF%D0%B0%D0%BC)" title="Категория:Википедия:Статьи без источников (не распределённые по типам)">Википедия:Статьи без источников (не распределённые по типам)</a></li></ul></div></div> </div> </div> <div id="mw-navigation"> <h2>Навигация</h2> <div id="mw-head"> <nav id="p-personal" class="mw-portlet mw-portlet-personal vector-user-menu-legacy vector-menu" aria-labelledby="p-personal-label" > <h3 id="p-personal-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Персональные инструменты</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anonuserpage" class="mw-list-item"><span title="Страница участника для моего IP">Вы не представились системе</span></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%9C%D0%BE%D1%91_%D0%BE%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5" title="Страница обсуждений для моего IP [n]" accesskey="n"><span>Обсуждение</span></a></li><li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%9C%D0%BE%D0%B9_%D0%B2%D0%BA%D0%BB%D0%B0%D0%B4" title="Список правок, сделанных с этого IP-адреса [y]" accesskey="y"><span>Вклад</span></a></li><li id="pt-createaccount" class="mw-list-item"><a href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%BE%D0%B7%D0%B4%D0%B0%D1%82%D1%8C_%D1%83%D1%87%D1%91%D1%82%D0%BD%D1%83%D1%8E_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D1%8C&returnto=%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="Мы предлагаем вам создать учётную запись и войти в систему, хотя это и не обязательно."><span>Создать учётную запись</span></a></li><li id="pt-login" class="mw-list-item"><a href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%92%D1%85%D0%BE%D0%B4&returnto=%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="Здесь можно зарегистрироваться в системе, но это необязательно. [o]" accesskey="o"><span>Войти</span></a></li> </ul> </div> </nav> <div id="left-navigation"> <nav id="p-namespaces" class="mw-portlet mw-portlet-namespaces vector-menu-tabs vector-menu-tabs-legacy vector-menu" aria-labelledby="p-namespaces-label" > <h3 id="p-namespaces-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Пространства имён</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected mw-list-item"><a href="/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="Просмотреть контентную страницу [c]" accesskey="c"><span>Статья</span></a></li><li id="ca-talk" class="mw-list-item"><a href="/wiki/%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%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" rel="discussion" title="Обсуждение основной страницы [t]" accesskey="t"><span>Обсуждение</span></a></li> </ul> </div> </nav> <nav id="p-variants" class="mw-portlet mw-portlet-variants emptyPortlet vector-menu-dropdown vector-menu" aria-labelledby="p-variants-label" > <input type="checkbox" id="p-variants-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-variants" class="vector-menu-checkbox" aria-labelledby="p-variants-label" > <label id="p-variants-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">русский</span> </label> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </nav> </div> <div id="right-navigation"> <nav id="p-views" class="mw-portlet mw-portlet-views vector-menu-tabs vector-menu-tabs-legacy vector-menu" aria-labelledby="p-views-label" > <h3 id="p-views-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Просмотры</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected mw-list-item"><a href="/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"><span>Читать</span></a></li><li id="ca-ve-edit" class="mw-list-item"><a href="/w/index.php?title=%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&veaction=edit" title="Редактировать данную страницу [v]" accesskey="v"><span>Править</span></a></li><li id="ca-edit" class="collapsible mw-list-item"><a href="/w/index.php?title=%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&action=edit" title="Править исходный текст этой страницы [e]" accesskey="e"><span>Править код</span></a></li><li id="ca-history" class="mw-list-item"><a href="/w/index.php?title=%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&action=history" title="Журнал изменений страницы [h]" accesskey="h"><span>История</span></a></li> </ul> </div> </nav> <nav id="p-cactions" class="mw-portlet mw-portlet-cactions emptyPortlet vector-menu-dropdown vector-menu" aria-labelledby="p-cactions-label" title="Больше возможностей" > <input type="checkbox" id="p-cactions-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-cactions" class="vector-menu-checkbox" aria-labelledby="p-cactions-label" > <label id="p-cactions-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Ещё</span> </label> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </nav> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <h3 >Поиск</h3> <form action="/w/index.php" id="searchform" class="vector-search-box-form"> <div id="simpleSearch" class="vector-search-box-inner" data-search-loc="header-navigation"> <input class="vector-search-box-input" type="search" name="search" placeholder="Искать в Википедии" aria-label="Искать в Википедии" autocapitalize="sentences" title="Искать в Википедии [f]" accesskey="f" id="searchInput" > <input type="hidden" name="title" value="Служебная:Поиск"> <input id="mw-searchButton" class="searchButton mw-fallbackSearchButton" type="submit" name="fulltext" title="Найти страницы, содержащие указанный текст" value="Найти"> <input id="searchButton" class="searchButton" type="submit" name="go" title="Перейти к странице, имеющей в точности такое название" value="Перейти"> </div> </form> </div> </div> </div> <div id="mw-panel" class="vector-legacy-sidebar"> <div id="p-logo" role="banner"> <a class="mw-wiki-logo" href="/wiki/%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0" title="Перейти на заглавную страницу"></a> </div> <nav id="p-navigation" class="mw-portlet mw-portlet-navigation vector-menu-portal portal vector-menu" aria-labelledby="p-navigation-label" > <h3 id="p-navigation-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Навигация</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0" title="Перейти на заглавную страницу [z]" accesskey="z"><span>Заглавная страница</span></a></li><li id="n-content" class="mw-list-item"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D0%BE%D0%B4%D0%B5%D1%80%D0%B6%D0%B0%D0%BD%D0%B8%D0%B5"><span>Содержание</span></a></li><li id="n-featured" class="mw-list-item"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%98%D0%B7%D0%B1%D1%80%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D1%81%D1%82%D0%B0%D1%82%D1%8C%D0%B8" title="Статьи, считающиеся лучшими статьями проекта"><span>Избранные статьи</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0" title="Посмотреть случайно выбранную страницу [x]" accesskey="x"><span>Случайная статья</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/%D0%9F%D0%BE%D1%80%D1%82%D0%B0%D0%BB:%D0%A2%D0%B5%D0%BA%D1%83%D1%89%D0%B8%D0%B5_%D1%81%D0%BE%D0%B1%D1%8B%D1%82%D0%B8%D1%8F" title="Статьи о текущих событиях в мире"><span>Текущие события</span></a></li><li id="n-sitesupport" class="mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=ru.wikipedia.org&uselang=ru" title="Поддержите нас"><span>Пожертвовать</span></a></li> </ul> </div> </nav> <nav id="p-participation" class="mw-portlet mw-portlet-participation vector-menu-portal portal vector-menu" aria-labelledby="p-participation-label" > <h3 id="p-participation-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Участие</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-bug_in_article" class="mw-list-item"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D0%BE%D0%BE%D0%B1%D1%89%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D0%B1_%D0%BE%D1%88%D0%B8%D0%B1%D0%BA%D0%B0%D1%85" title="Сообщить об ошибке в этой статье"><span>Сообщить об ошибке</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B0:%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5"><span>Как править статьи</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D0%BE%D0%BE%D0%B1%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%BE" title="О проекте, о том, чем здесь можно заниматься, а также — где что находится"><span>Сообщество</span></a></li><li id="n-forum" class="mw-list-item"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A4%D0%BE%D1%80%D1%83%D0%BC" title="Форум участников Википедии"><span>Форум</span></a></li><li id="n-help" class="mw-list-item"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B0" title="Место расположения Справки"><span>Справка</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%B2%D0%B5%D0%B6%D0%B8%D0%B5_%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B8" title="Список последних изменений [r]" accesskey="r"><span>Свежие правки</span></a></li><li id="n-newpages" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%9D%D0%BE%D0%B2%D1%8B%D0%B5_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B" title="Список недавно созданных страниц"><span>Новые страницы</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%BF%D0%B5%D1%86%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B"><span>Служебные страницы</span></a></li> </ul> </div> </nav> <nav id="p-tb" class="mw-portlet mw-portlet-tb vector-menu-portal portal vector-menu" aria-labelledby="p-tb-label" > <h3 id="p-tb-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Инструменты</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D1%81%D1%8B%D0%BB%D0%BA%D0%B8_%D1%81%D1%8E%D0%B4%D0%B0/%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="Список всех страниц, ссылающихся на данную [j]" accesskey="j"><span>Ссылки сюда</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A1%D0%B2%D1%8F%D0%B7%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%BF%D1%80%D0%B0%D0%B2%D0%BA%D0%B8/%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" rel="nofollow" title="Последние изменения в страницах, на которые ссылается эта страница [k]" accesskey="k"><span>Связанные правки</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=%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&oldid=140880039" title="Постоянная ссылка на эту версию страницы"><span>Постоянная ссылка</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=%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&action=info" title="Подробнее об этой странице"><span>Сведения о странице</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%A6%D0%B8%D1%82%D0%B0%D1%82%D0%B0&page=%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&id=140880039&wpFormIdentifier=titleform" title="Информация о том, как цитировать эту страницу"><span>Цитировать страницу</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:UrlShortener&url=https%3A%2F%2Fru.wikipedia.org%2Fwiki%2F%25D0%2594%25D0%25B2%25D0%25BE%25D0%25B8%25D1%2587%25D0%25BD%25D0%25BE%25D0%25B5_%25D0%25B4%25D0%25B5%25D1%2580%25D0%25B5%25D0%25B2%25D0%25BE_%25D0%25BF%25D0%25BE%25D0%25B8%25D1%2581%25D0%25BA%25D0%25B0"><span>Получить короткий URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:QrCode&url=https%3A%2F%2Fru.wikipedia.org%2Fwiki%2F%25D0%2594%25D0%25B2%25D0%25BE%25D0%25B8%25D1%2587%25D0%25BD%25D0%25BE%25D0%25B5_%25D0%25B4%25D0%25B5%25D1%2580%25D0%25B5%25D0%25B2%25D0%25BE_%25D0%25BF%25D0%25BE%25D0%25B8%25D1%2581%25D0%25BA%25D0%25B0"><span>Скачать QR-код</span></a></li> </ul> </div> </nav> <nav id="p-coll-print_export" class="mw-portlet mw-portlet-coll-print_export vector-menu-portal portal vector-menu" aria-labelledby="p-coll-print_export-label" > <h3 id="p-coll-print_export-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Печать/экспорт</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:DownloadAsPdf&page=%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&action=show-download-screen" title="Скачать эту страницу как файл PDF"><span>Скачать как PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=%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&printable=yes" title="Версия этой страницы для печати [p]" accesskey="p"><span>Версия для печати</span></a></li> </ul> </div> </nav> <nav id="p-wikibase-otherprojects" class="mw-portlet mw-portlet-wikibase-otherprojects vector-menu-portal portal vector-menu" aria-labelledby="p-wikibase-otherprojects-label" > <h3 id="p-wikibase-otherprojects-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">В других проектах</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Binary_search_trees" hreflang="en"><span>Викисклад</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q623818" title="Ссылка на связанный элемент репозитория данных [g]" accesskey="g"><span>Элемент Викиданных</span></a></li> </ul> </div> </nav> <nav id="p-lang" class="mw-portlet mw-portlet-lang vector-menu-portal portal vector-menu" aria-labelledby="p-lang-label" > <h3 id="p-lang-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">На других языках</span> </h3> <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="شجرة بحث ثنائية — арабский" lang="ar" hreflang="ar" data-title="شجرة بحث ثنائية" data-language-autonym="العربية" data-language-local-name="арабский" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE_%D0%B4%D1%8A%D1%80%D0%B2%D0%BE_%D0%B7%D0%B0_%D1%82%D1%8A%D1%80%D1%81%D0%B5%D0%BD%D0%B5" title="Двоично дърво за търсене — болгарский" lang="bg" hreflang="bg" data-title="Двоично дърво за търсене" data-language-autonym="Български" data-language-local-name="болгарский" class="interlanguage-link-target"><span>Български</span></a></li><li class="interlanguage-link interwiki-bs mw-list-item"><a href="https://bs.wikipedia.org/wiki/Binarno_stablo_pretra%C5%BEivanja" title="Binarno stablo pretraživanja — боснийский" lang="bs" hreflang="bs" data-title="Binarno stablo pretraživanja" data-language-autonym="Bosanski" data-language-local-name="боснийский" class="interlanguage-link-target"><span>Bosanski</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Arbre_binari_de_cerca" title="Arbre binari de cerca — каталанский" lang="ca" hreflang="ca" data-title="Arbre binari de cerca" data-language-autonym="Català" data-language-local-name="каталанский" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Bin%C3%A1rn%C3%AD_vyhled%C3%A1vac%C3%AD_strom" title="Binární vyhledávací strom — чешский" lang="cs" hreflang="cs" data-title="Binární vyhledávací strom" data-language-autonym="Čeština" data-language-local-name="чешский" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Bin%C3%A6rt_s%C3%B8getr%C3%A6" title="Binært søgetræ — датский" lang="da" hreflang="da" data-title="Binært søgetræ" data-language-autonym="Dansk" data-language-local-name="датский" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum" title="Binärer Suchbaum — немецкий" lang="de" hreflang="de" data-title="Binärer Suchbaum" data-language-autonym="Deutsch" data-language-local-name="немецкий" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-en badge-Q17437798 badge-goodarticle mw-list-item" title="хорошая статья"><a href="https://en.wikipedia.org/wiki/Binary_search_tree" title="Binary search tree — английский" lang="en" hreflang="en" data-title="Binary search tree" data-language-autonym="English" data-language-local-name="английский" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/%C3%81rbol_binario_de_b%C3%BAsqueda" title="Árbol binario de búsqueda — испанский" lang="es" hreflang="es" data-title="Árbol binario de búsqueda" data-language-autonym="Español" data-language-local-name="испанский" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C_%D8%AF%D9%88%D8%AF%D9%88%DB%8C%DB%8C" title="درخت جستجوی دودویی — персидский" lang="fa" hreflang="fa" data-title="درخت جستجوی دودویی" data-language-autonym="فارسی" data-language-local-name="персидский" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Bin%C3%A4%C3%A4rinen_hakupuu" title="Binäärinen hakupuu — финский" lang="fi" hreflang="fi" data-title="Binäärinen hakupuu" data-language-autonym="Suomi" data-language-local-name="финский" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Arbre_binaire_de_recherche" title="Arbre binaire de recherche — французский" lang="fr" hreflang="fr" data-title="Arbre binaire de recherche" data-language-autonym="Français" data-language-local-name="французский" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A2%D7%A5_%D7%97%D7%99%D7%A4%D7%95%D7%A9" title="עץ חיפוש — иврит" lang="he" hreflang="he" data-title="עץ חיפוש" data-language-autonym="עברית" data-language-local-name="иврит" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-hy mw-list-item"><a href="https://hy.wikipedia.org/wiki/%D4%B2%D5%AB%D5%B6%D5%A1%D6%80_%D5%B8%D6%80%D5%B8%D5%B6%D5%B4%D5%A1%D5%B6_%D5%AE%D5%A1%D5%BC" title="Բինար որոնման ծառ — армянский" lang="hy" hreflang="hy" data-title="Բինար որոնման ծառ" data-language-autonym="Հայերեն" data-language-local-name="армянский" class="interlanguage-link-target"><span>Հայերեն</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Pohon_Pencarian_Biner" title="Pohon Pencarian Biner — индонезийский" lang="id" hreflang="id" data-title="Pohon Pencarian Biner" data-language-autonym="Bahasa Indonesia" data-language-local-name="индонезийский" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Albero_binario_di_ricerca" title="Albero binario di ricerca — итальянский" lang="it" hreflang="it" data-title="Albero binario di ricerca" data-language-autonym="Italiano" data-language-local-name="итальянский" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8" title="二分探索木 — японский" lang="ja" hreflang="ja" data-title="二分探索木" data-language-autonym="日本語" data-language-local-name="японский" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-kn mw-list-item"><a href="https://kn.wikipedia.org/wiki/%E0%B2%AC%E0%B3%88%E0%B2%A8%E0%B2%B0%E0%B2%BF_%E0%B2%B8%E0%B2%B0%E0%B3%8D%E0%B2%9A%E0%B3%8D_%E0%B2%9F%E0%B3%8D%E0%B2%B0%E0%B3%80_(%E0%B2%AC%E0%B3%88%E0%B2%A8%E0%B2%B0%E0%B2%BF_%E0%B2%B9%E0%B3%81%E0%B2%A1%E0%B3%81%E0%B2%95%E0%B2%BE%E0%B2%9F%E0%B2%A6_%E0%B2%9F%E0%B3%8D%E0%B2%B0%E0%B3%80)" title="ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ (ಬೈನರಿ ಹುಡುಕಾಟದ ಟ್ರೀ) — каннада" lang="kn" hreflang="kn" data-title="ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ (ಬೈನರಿ ಹುಡುಕಾಟದ ಟ್ರೀ)" data-language-autonym="ಕನ್ನಡ" data-language-local-name="каннада" class="interlanguage-link-target"><span>ಕನ್ನಡ</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC" title="이진 탐색 트리 — корейский" lang="ko" hreflang="ko" data-title="이진 탐색 트리" data-language-autonym="한국어" data-language-local-name="корейский" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-lmo mw-list-item"><a href="https://lmo.wikipedia.org/wiki/Alber_binari_de_ricerca" title="Alber binari de ricerca — ломбардский" lang="lmo" hreflang="lmo" data-title="Alber binari de ricerca" data-language-autonym="Lombard" data-language-local-name="ломбардский" class="interlanguage-link-target"><span>Lombard</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Binaire_zoekboom" title="Binaire zoekboom — нидерландский" lang="nl" hreflang="nl" data-title="Binaire zoekboom" data-language-autonym="Nederlands" data-language-local-name="нидерландский" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Binarne_drzewo_poszukiwa%C5%84" title="Binarne drzewo poszukiwań — польский" lang="pl" hreflang="pl" data-title="Binarne drzewo poszukiwań" data-language-autonym="Polski" data-language-local-name="польский" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/%C3%81rvore_bin%C3%A1ria_de_busca" title="Árvore binária de busca — португальский" lang="pt" hreflang="pt" data-title="Árvore binária de busca" data-language-autonym="Português" data-language-local-name="португальский" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Arbore_binar_de_c%C4%83utare" title="Arbore binar de căutare — румынский" lang="ro" hreflang="ro" data-title="Arbore binar de căutare" data-language-autonym="Română" data-language-local-name="румынский" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Binarno_stablo_pretrage" title="Binarno stablo pretrage — сербскохорватский" lang="sh" hreflang="sh" data-title="Binarno stablo pretrage" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="сербскохорватский" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Bin%C3%A1rny_vyh%C4%BEad%C3%A1vac%C3%AD_strom" title="Binárny vyhľadávací strom — словацкий" lang="sk" hreflang="sk" data-title="Binárny vyhľadávací strom" data-language-autonym="Slovenčina" data-language-local-name="словацкий" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/Binarno_stablo_pretrage" title="Binarno stablo pretrage — сербский" lang="sr" hreflang="sr" data-title="Binarno stablo pretrage" data-language-autonym="Српски / srpski" data-language-local-name="сербский" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Bin%C3%A4rt_s%C3%B6ktr%C3%A4d" title="Binärt sökträd — шведский" lang="sv" hreflang="sv" data-title="Binärt sökträd" data-language-autonym="Svenska" data-language-local-name="шведский" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%95%E0%B9%89%E0%B8%99%E0%B9%84%E0%B8%A1%E0%B9%89%E0%B8%84%E0%B9%89%E0%B8%99%E0%B8%AB%E0%B8%B2%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B8%97%E0%B8%A7%E0%B8%B4%E0%B8%A0%E0%B8%B2%E0%B8%84" title="ต้นไม้ค้นหาแบบทวิภาค — тайский" lang="th" hreflang="th" data-title="ต้นไม้ค้นหาแบบทวิภาค" data-language-autonym="ไทย" data-language-local-name="тайский" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/%C4%B0kili_arama_a%C4%9Fac%C4%B1" title="İkili arama ağacı — турецкий" lang="tr" hreflang="tr" data-title="İkili arama ağacı" data-language-autonym="Türkçe" data-language-local-name="турецкий" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%94%D0%B2%D1%96%D0%B9%D0%BA%D0%BE%D0%B2%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D1%88%D1%83%D0%BA%D1%83" title="Двійкове дерево пошуку — украинский" lang="uk" hreflang="uk" data-title="Двійкове дерево пошуку" data-language-autonym="Українська" data-language-local-name="украинский" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n" title="Cây tìm kiếm nhị phân — вьетнамский" lang="vi" hreflang="vi" data-title="Cây tìm kiếm nhị phân" data-language-autonym="Tiếng Việt" data-language-local-name="вьетнамский" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9" title="二元搜尋樹 — китайский" lang="zh" hreflang="zh" data-title="二元搜尋樹" data-language-autonym="中文" data-language-local-name="китайский" class="interlanguage-link-target"><span>中文</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9" title="二元搜尋樹 — кантонский" lang="yue" hreflang="yue" data-title="二元搜尋樹" data-language-autonym="粵語" data-language-local-name="кантонский" class="interlanguage-link-target"><span>粵語</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q623818#sitelinks-wikipedia" title="Править ссылки на другие языки" class="wbc-editpage">Править ссылки</a></span></div> </div> </nav> </div> </div> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> Эта страница в последний раз была отредактирована 18 октября 2024 в 19:09.</li> <li id="footer-info-copyright">Текст доступен по <a rel="nofollow" class="external text" href="//creativecommons.org/licenses/by-sa/4.0/deed.ru">лицензии Creative Commons «С указанием авторства — С сохранением условий» (CC BY-SA)</a>; в отдельных случаях могут действовать дополнительные условия. <span class="noprint">Подробнее см. <a class="external text" href="https://foundation.wikimedia.org/wiki/Policy:Terms_of_Use/ru">Условия использования</a>.</span><br /> Wikipedia® — зарегистрированный товарный знак некоммерческой организации <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/ru/">«Фонд Викимедиа» (Wikimedia Foundation, Inc.)</a></li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/ru">Политика конфиденциальности</a></li> <li id="footer-places-about"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9E%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D0%B5">Описание Википедии</a></li> <li id="footer-places-disclaimers"><a href="/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%9E%D1%82%D0%BA%D0%B0%D0%B7_%D0%BE%D1%82_%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D0%BE%D1%81%D1%82%D0%B8">Отказ от ответственности</a></li> <li id="footer-places-contact"><a href="//ru.wikipedia.org/wiki/Википедия:Контакты">Свяжитесь с нами</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Policy:Universal_Code_of_Conduct/ru">Кодекс поведения</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Разработчики</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/ru.wikipedia.org">Статистика</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Заявление о куки</a></li> <li id="footer-places-mobileview"><a href="//ru.m.wikipedia.org/w/index.php?title=%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&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Мобильная версия</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> <script>(RLQ=window.RLQ||[]).push(function(){mw.log.warn("This page is using the deprecated ResourceLoader module \"codex-search-styles\".\n[1.43] Use a CodexModule with codexComponents to set your specific components used: https://www.mediawiki.org/wiki/Codex#Using_a_limited_subset_of_components");mw.config.set({"wgHostname":"mw-web.codfw.main-54bc5bdf84-mvx56","wgBackendResponseTime":157,"wgPageParseReport":{"limitreport":{"cputime":"0.327","walltime":"0.508","ppvisitednodes":{"value":1623,"limit":1000000},"postexpandincludesize":{"value":81455,"limit":2097152},"templateargumentsize":{"value":2898,"limit":2097152},"expansiondepth":{"value":15,"limit":100},"expensivefunctioncount":{"value":15,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":5981,"limit":5000000},"entityaccesscount":{"value":4,"limit":400},"timingprofile":["100.00% 438.328 1 -total"," 46.14% 202.260 1 Шаблон:Структура_данных"," 44.30% 194.178 1 Шаблон:Карточка"," 32.52% 142.562 2 Шаблон:Ambox"," 21.12% 92.583 1 Шаблон:Заготовка_раздела"," 15.54% 68.137 3 Шаблон:Wikidata"," 14.72% 64.510 1 Шаблон:Rq"," 11.11% 48.694 1 Шаблон:Карточка/оригинал_названия"," 9.69% 42.492 16 Шаблон:Rq/"," 8.31% 36.446 2 Шаблон:Навигационная_таблица"]},"scribunto":{"limitreport-timeusage":{"value":"0.190","limit":"10.000"},"limitreport-memusage":{"value":4214662,"limit":52428800},"limitreport-logs":"Loaded datatype time of P575 from wikidata, consider passing datatype argument to formatProperty call or to Wikidata/config\nLoaded datatype wikibase-item of P61 from wikidata, consider passing datatype argument to formatProperty call or to Wikidata/config\n"},"cachereport":{"origin":"mw-web.eqiad.main-868759585b-gxnhd","timestamp":"20250216160427","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"\u0414\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430","url":"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","sameAs":"http:\/\/www.wikidata.org\/entity\/Q623818","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q623818","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"\u0424\u043e\u043d\u0434 \u0412\u0438\u043a\u0438\u043c\u0435\u0434\u0438\u0430","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2006-07-22T22:05:49Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/d\/da\/Binary_search_tree.svg"}</script> </body> </html>