Двоичное дерево поиска

Поделись знанием:
Перейти к: навигация, поиск
Двоичное дерево поиска
Тип Дерево
Временная сложность
в О-символике
В среднем В худшем случае
Расход памяти O(n) O(n)
Поиск O(log n) O(n)
Вставка O(log n) O(n)
Удаление O(log n) O(n)

Двоичное дерево поиска (англ. binary search tree, BST) — это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

  • Оба поддерева — левое и правое — являются двоичными деревьями поиска.
  • У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
  • У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равно, нежели значение ключа данных самого узла X.

Очевидно, данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.

Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных. Однако это касается реализации, а не природы двоичного дерева поиска.

Для целей реализации двоичное дерево поиска можно определить так:

  • Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные, привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла — левый и правый сыновья соответственно. Для оптимизации алгоритмов конкретные реализации предполагают также определения поля parent в каждом узле (кроме корневого) — ссылки на родительский элемент.
  • Данные (data) обладают ключом (key), на котором определена операция сравнения «меньше». В конкретных реализациях это может быть пара (key, value) — (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё.
  • Для любого узла X выполняются свойства дерева поиска: key[left[X]] < key[X] ≤ key[right[X]], то есть ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого.

Двоичное дерево поиска не следует путать с двоичной кучей, построенной по другим правилам.

Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нём алгоритмов поиска и сортировки.

Двоичное дерево поиска применяется для построения более абстрактных структур, таких, как множества, мультимножества, ассоциативные массивы.





Основные операции в двоичном дереве поиска

Базовый интерфейс двоичного дерева поиска состоит из трех операций:

  • FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K.
  • INSERT(K,V) — добавление в дерево пары (key, value) = (K, V).
  • REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key = K.

Этот абстрактный интерфейс является общим случаем, например, таких интерфейсов, взятых из прикладных задач:

  • «Телефонная книжка» — хранилище записей (имя человека, его телефон) с операциями поиска и удаления записей по имени человека, и операцией добавления новой записи.
  • Domain Name Server — хранилище пар (доменное имя, IP адрес) с операциями модификации и поиска.
  • Namespace — хранилище имен переменных с их значениями, возникающее в трансляторах языков программирования.

По сути, двоичное дерево поиска — это структура данных, способная хранить таблицу пар (key, value) и поддерживающая три операции: FIND, INSERT, REMOVE.

Кроме того, интерфейс двоичного дерева включает ещё три дополнительных операции обхода узлов дерева: INFIX_TRAVERSE, PREFIX_TRAVERSE и POSTFIX_TRAVERSE. Первая из них позволяет обойти узлы дерева в порядке неубывания ключей.

Поиск элемента (FIND)

Дано: дерево Т и ключ K.

Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.

Алгоритм:

  • Если дерево пусто, сообщить, что узел не найден, и остановиться.
  • Иначе сравнить K со значением ключа корневого узла X.
    • Если K=X, выдать ссылку на этот узел и остановиться.
    • Если K>X, рекурсивно искать ключ K в правом поддереве Т.
    • Если K<X, рекурсивно искать ключ K в левом поддереве Т.

Добавление элемента (INSERT)

Дано: дерево Т и пара (K,V).

Задача: вставить пару (K, V) в дерево Т (при совпадении K, заменить V).

Алгоритм:

  • Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться.
  • Иначе сравнить K с ключом корневого узла X.
    • Если K>X, циклически добавить (K,V) в правое поддерево Т.
    • Если K<X, циклически добавить (K,V) в левое поддерево Т.
    • Если K=X, заменить V текущего узла новым значением (хотя можно и организовать список значений V, но это другая тема).

Удаление узла (REMOVE)

Дано: дерево Т с корнем n и ключом K.

Задача: удалить из дерева Т узел с ключом K (если такой есть).

Алгоритм:

  • Если дерево T пусто, остановиться;
  • Иначе сравнить K с ключом X корневого узла n.
    • Если K>X, циклически удалить K из правого поддерева Т;
    • Если K<X, циклически удалить K из левого поддерева Т;
    • Если K=X, то необходимо рассмотреть три случая.
      • Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла;
      • Если одного из детей нет, то значения полей ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m;
      • Если оба ребёнка присутствуют, то
        • Если левый узел m правого поддерева отсутствует (n->right->left)
          • Копируем из правого узла в удаляемый поля K, V и ссылку на правый узел правого потомка.
        • Иначе
          • Возьмём самый левый узел m, правого поддерева n->right;
          • Скопируем данные (кроме ссылок на дочерние элементы) из m в n;
          • Рекурсивно удалим узел m.

Обход дерева (TRAVERSE)

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов.

Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию обратного вызова f, операндом которой является адрес узла. Эта функция обычно работает только с парой (K,V), хранящейся в узле. Операция INFIX_TRAVERSE может быть реализована рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.

  • INFIX_TRAVERSE (tr) — обойти всё дерево, следуя порядку (левое поддерево, вершина, правое поддерево). Элементы по возрастанию
  • PREFIX_TRAVERSE (tr) — обойти всё дерево, следуя порядку (вершина, левое поддерево, правое поддерево). Элементы, как в дереве
  • POSTFIX_TRAVERSE (tr) — обойти всё дерево, следуя порядку (левое поддерево, правое поддерево', вершина). Элементы в обратном порядке, как в дереве

В других источниках эти функции именуются inorder, preorder, postorder соответственно[1]


INFIX_TRAVERSE

Дано: дерево Т и функция f

Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей

Алгоритм:

  • Если дерево пусто, остановиться.
  • Иначе
    • Рекурсивно обойти левое поддерево Т.
    • Применить функцию f к корневому узлу.
    • Рекурсивно обойти правое поддерево Т.

В простейшем случае функция f может выводить значение пары (K,V). При использовании операции INFIX_TRAVERSE будут выведены все пары в порядке возрастания ключей. Если же использовать PREFIX_TRAVERSE, то пары будут выведены в порядке, соответствующем описанию дерева, приведённого в начале статьи.

Разбиение дерева по ключу

Операция «разбиение дерева по ключу» позволяет разбить одно дерево поиска на два: с ключами <K0 и ≥K0.


Этот раздел не завершён.
Вы поможете проекту, исправив и дополнив его.

Объединение двух деревьев в одно

Обратная операция: есть два дерева поиска, у одного ключи <K0, у другого ≥K0. Объединить их в одно дерево.

У нас есть два дерева: T1 (меньшее) и T2 (большее). Сначала нужно решить, откуда взять корень: из T1 или T2. Стандартного метода нет, возможные варианты: 

алг ОбъединениеДеревьев(T1, T2)
если T1 пустое, вернуть T2
если T2 пустое, вернуть T1
если решили сделать корнем T1, то
  T = ОбъединениеДеревьев(T1.правое, T2)
  T1.правое = T
  вернуть T1
иначе
  T = ОбъединениеДеревьев(T1, T2.левое)
  T2.левое = T
  вернуть T2

Балансировка дерева

Всегда желательно, чтобы все пути в дереве от корня до листьев имели примерно одинаковую длину, то есть чтобы глубина и левого, и правого поддеревьев была примерно одинакова в любом узле. В противном случае теряется производительность.

В вырожденном случае может оказаться, что все левое дерево пусто на каждом уровне, есть только правые деревья, и в таком случае дерево вырождается в список (идущий вправо). Поиск (а значит, и удаление и добавление) в таком дереве по скорости равен поиску в списке и намного медленнее поиска в сбалансированном дереве.

Для балансировки дерева применяется операция «поворот дерева». Поворот налево выглядит так:

  • было Left(A) = L, Right(A) = B, Left(B) = C, Right(B) = R
  • поворот меняет местами A и B, получая Left(A) = L, Right(A) = C, Left(B) = A, Right(B) = R
  • также меняется в узле Parent(A) ссылка, ранее указывавшая на A, после поворота она указывает на B.

Поворот направо выглядит так же, достаточно заменить в вышеприведенном примере все Left на Right и обратно.

Достаточно очевидно, что поворот не нарушает упорядоченность дерева, и оказывает предсказуемое (+1 или −1) влияние на глубины всех затронутых поддеревьев.

Для принятия решения о том, какие именно повороты нужно совершать после добавления или удаления, используются такие алгоритмы, как «красно-чёрное дерево» и АВЛ.

Оба они требуют дополнительной информации в узлах — 1 бит у красно-черного или знаковое число у АВЛ.

Красно-черное дерево требует <= 2 поворотов после добавления и <= 3 после удаления, но при этом худший дисбаланс может оказаться до 2 раз (самый длинный путь в 2 раза длиннее самого короткого).

АВЛ-дерево требует <= 2 поворотов после добавления и до глубины дерева после удаления, но при этом идеально сбалансировано (дисбаланс не более, чем на 1).

См. также

Сбалансированные деревья:

Напишите отзыв о статье "Двоичное дерево поиска"

Примечания

  1. ↑ Роман Акопов. [www.rsdn.ru/article/alg/binstree.xml Двоичные деревья поиска]. RSDN Magazine #5-2003 (13.03.2005). Проверено 1 ноября 2014.

Ссылки

  • [kvodo.ru/dvoichnoe-derevo-poiska.html Двоичное дерево поиска]


<imagemap>: неверное или отсутствующее изображение

 Для улучшения этой статьи желательно?:
Типы
Массивы

Ассоциативный массив • Ассоциативный мультимассив • Множество • Мультимножество • Хеш-таблица

Списки
Деревья

B-дерево • Двоичное дерево поиска • Куча

Графы

Отрывок, характеризующий Двоичное дерево поиска

– Уйдет! Нет, это невозможно! – думал Николай, продолжая кричать охрипнувшим голосом.
– Карай! Улюлю!… – кричал он, отыскивая глазами старого кобеля, единственную свою надежду. Карай из всех своих старых сил, вытянувшись сколько мог, глядя на волка, тяжело скакал в сторону от зверя, наперерез ему. Но по быстроте скока волка и медленности скока собаки было видно, что расчет Карая был ошибочен. Николай уже не далеко впереди себя видел тот лес, до которого добежав, волк уйдет наверное. Впереди показались собаки и охотник, скакавший почти на встречу. Еще была надежда. Незнакомый Николаю, муругий молодой, длинный кобель чужой своры стремительно подлетел спереди к волку и почти опрокинул его. Волк быстро, как нельзя было ожидать от него, приподнялся и бросился к муругому кобелю, щелкнул зубами – и окровавленный, с распоротым боком кобель, пронзительно завизжав, ткнулся головой в землю.
– Караюшка! Отец!.. – плакал Николай…
Старый кобель, с своими мотавшимися на ляжках клоками, благодаря происшедшей остановке, перерезывая дорогу волку, был уже в пяти шагах от него. Как будто почувствовав опасность, волк покосился на Карая, еще дальше спрятав полено (хвост) между ног и наддал скоку. Но тут – Николай видел только, что что то сделалось с Караем – он мгновенно очутился на волке и с ним вместе повалился кубарем в водомоину, которая была перед ними.
Та минута, когда Николай увидал в водомоине копошащихся с волком собак, из под которых виднелась седая шерсть волка, его вытянувшаяся задняя нога, и с прижатыми ушами испуганная и задыхающаяся голова (Карай держал его за горло), минута, когда увидал это Николай, была счастливейшею минутою его жизни. Он взялся уже за луку седла, чтобы слезть и колоть волка, как вдруг из этой массы собак высунулась вверх голова зверя, потом передние ноги стали на край водомоины. Волк ляскнул зубами (Карай уже не держал его за горло), выпрыгнул задними ногами из водомоины и, поджав хвост, опять отделившись от собак, двинулся вперед. Карай с ощетинившейся шерстью, вероятно ушибленный или раненый, с трудом вылезал из водомоины.
– Боже мой! За что?… – с отчаянием закричал Николай.
Охотник дядюшки с другой стороны скакал на перерез волку, и собаки его опять остановили зверя. Опять его окружили.
Николай, его стремянной, дядюшка и его охотник вертелись над зверем, улюлюкая, крича, всякую минуту собираясь слезть, когда волк садился на зад и всякий раз пускаясь вперед, когда волк встряхивался и подвигался к засеке, которая должна была спасти его. Еще в начале этой травли, Данила, услыхав улюлюканье, выскочил на опушку леса. Он видел, как Карай взял волка и остановил лошадь, полагая, что дело было кончено. Но когда охотники не слезли, волк встряхнулся и опять пошел на утек. Данила выпустил своего бурого не к волку, а прямой линией к засеке так же, как Карай, – на перерез зверю. Благодаря этому направлению, он подскакивал к волку в то время, как во второй раз его остановили дядюшкины собаки.
Данила скакал молча, держа вынутый кинжал в левой руке и как цепом молоча своим арапником по подтянутым бокам бурого.
Николай не видал и не слыхал Данилы до тех пор, пока мимо самого его не пропыхтел тяжело дыша бурый, и он услыхал звук паденья тела и увидал, что Данила уже лежит в середине собак на заду волка, стараясь поймать его за уши. Очевидно было и для собак, и для охотников, и для волка, что теперь всё кончено. Зверь, испуганно прижав уши, старался подняться, но собаки облепили его. Данила, привстав, сделал падающий шаг и всей тяжестью, как будто ложась отдыхать, повалился на волка, хватая его за уши. Николай хотел колоть, но Данила прошептал: «Не надо, соструним», – и переменив положение, наступил ногою на шею волку. В пасть волку заложили палку, завязали, как бы взнуздав его сворой, связали ноги, и Данила раза два с одного бока на другой перевалил волка.
С счастливыми, измученными лицами, живого, матерого волка взвалили на шарахающую и фыркающую лошадь и, сопутствуемые визжавшими на него собаками, повезли к тому месту, где должны были все собраться. Молодых двух взяли гончие и трех борзые. Охотники съезжались с своими добычами и рассказами, и все подходили смотреть матёрого волка, который свесив свою лобастую голову с закушенною палкой во рту, большими, стеклянными глазами смотрел на всю эту толпу собак и людей, окружавших его. Когда его трогали, он, вздрагивая завязанными ногами, дико и вместе с тем просто смотрел на всех. Граф Илья Андреич тоже подъехал и потрогал волка.
– О, материщий какой, – сказал он. – Матёрый, а? – спросил он у Данилы, стоявшего подле него.
– Матёрый, ваше сиятельство, – отвечал Данила, поспешно снимая шапку.
Граф вспомнил своего прозеванного волка и свое столкновение с Данилой.
– Однако, брат, ты сердит, – сказал граф. – Данила ничего не сказал и только застенчиво улыбнулся детски кроткой и приятной улыбкой.


Старый граф поехал домой; Наташа с Петей обещались сейчас же приехать. Охота пошла дальше, так как было еще рано. В середине дня гончих пустили в поросший молодым частым лесом овраг. Николай, стоя на жнивье, видел всех своих охотников.
Насупротив от Николая были зеленя и там стоял его охотник, один в яме за выдавшимся кустом орешника. Только что завели гончих, Николай услыхал редкий гон известной ему собаки – Волторна; другие собаки присоединились к нему, то замолкая, то опять принимаясь гнать. Через минуту подали из острова голос по лисе, и вся стая, свалившись, погнала по отвершку, по направлению к зеленям, прочь от Николая.
Он видел скачущих выжлятников в красных шапках по краям поросшего оврага, видел даже собак, и всякую секунду ждал того, что на той стороне, на зеленях, покажется лисица.
Охотник, стоявший в яме, тронулся и выпустил собак, и Николай увидал красную, низкую, странную лисицу, которая, распушив трубу, торопливо неслась по зеленям. Собаки стали спеть к ней. Вот приблизились, вот кругами стала вилять лисица между ними, всё чаще и чаще делая эти круги и обводя вокруг себя пушистой трубой (хвостом); и вот налетела чья то белая собака, и вслед за ней черная, и всё смешалось, и звездой, врозь расставив зады, чуть колеблясь, стали собаки. К собакам подскакали два охотника: один в красной шапке, другой, чужой, в зеленом кафтане.
«Что это такое? подумал Николай. Откуда взялся этот охотник? Это не дядюшкин».
Охотники отбили лисицу и долго, не тороча, стояли пешие. Около них на чумбурах стояли лошади с своими выступами седел и лежали собаки. Охотники махали руками и что то делали с лисицей. Оттуда же раздался звук рога – условленный сигнал драки.
– Это Илагинский охотник что то с нашим Иваном бунтует, – сказал стремянный Николая.
Николай послал стремяного подозвать к себе сестру и Петю и шагом поехал к тому месту, где доезжачие собирали гончих. Несколько охотников поскакало к месту драки.
Николай слез с лошади, остановился подле гончих с подъехавшими Наташей и Петей, ожидая сведений о том, чем кончится дело. Из за опушки выехал дравшийся охотник с лисицей в тороках и подъехал к молодому барину. Он издалека снял шапку и старался говорить почтительно; но он был бледен, задыхался, и лицо его было злобно. Один глаз был у него подбит, но он вероятно и не знал этого.
– Что у вас там было? – спросил Николай.
– Как же, из под наших гончих он травить будет! Да и сука то моя мышастая поймала. Поди, судись! За лисицу хватает! Я его лисицей ну катать. Вот она, в тороках. А этого хочешь?… – говорил охотник, указывая на кинжал и вероятно воображая, что он всё еще говорит с своим врагом.
Николай, не разговаривая с охотником, попросил сестру и Петю подождать его и поехал на то место, где была эта враждебная, Илагинская охота.
Охотник победитель въехал в толпу охотников и там, окруженный сочувствующими любопытными, рассказывал свой подвиг.
Дело было в том, что Илагин, с которым Ростовы были в ссоре и процессе, охотился в местах, по обычаю принадлежавших Ростовым, и теперь как будто нарочно велел подъехать к острову, где охотились Ростовы, и позволил травить своему охотнику из под чужих гончих.
Николай никогда не видал Илагина, но как и всегда в своих суждениях и чувствах не зная середины, по слухам о буйстве и своевольстве этого помещика, всей душой ненавидел его и считал своим злейшим врагом. Он озлобленно взволнованный ехал теперь к нему, крепко сжимая арапник в руке, в полной готовности на самые решительные и опасные действия против своего врага.
Едва он выехал за уступ леса, как он увидал подвигающегося ему навстречу толстого барина в бобровом картузе на прекрасной вороной лошади, сопутствуемого двумя стремянными.
Вместо врага Николай нашел в Илагине представительного, учтивого барина, особенно желавшего познакомиться с молодым графом. Подъехав к Ростову, Илагин приподнял бобровый картуз и сказал, что очень жалеет о том, что случилось; что велит наказать охотника, позволившего себе травить из под чужих собак, просит графа быть знакомым и предлагает ему свои места для охоты.
Наташа, боявшаяся, что брат ее наделает что нибудь ужасное, в волнении ехала недалеко за ним. Увидав, что враги дружелюбно раскланиваются, она подъехала к ним. Илагин еще выше приподнял свой бобровый картуз перед Наташей и приятно улыбнувшись, сказал, что графиня представляет Диану и по страсти к охоте и по красоте своей, про которую он много слышал.
Илагин, чтобы загладить вину своего охотника, настоятельно просил Ростова пройти в его угорь, который был в версте, который он берег для себя и в котором было, по его словам, насыпано зайцев. Николай согласился, и охота, еще вдвое увеличившаяся, тронулась дальше.
Итти до Илагинского угоря надо было полями. Охотники разровнялись. Господа ехали вместе. Дядюшка, Ростов, Илагин поглядывали тайком на чужих собак, стараясь, чтобы другие этого не замечали, и с беспокойством отыскивали между этими собаками соперниц своим собакам.


Источник — «http://wiki-org.ru/wiki/index.php?title=Двоичное_дерево_поиска&oldid=79598614»