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

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

Двоичные деревья поиска позволяют выполнять бинарный поиск для быстрого поиска, добавления и удаления элементов данных. Поскольку узлы в BST расположены так, что каждое сравнение пропускает около половины оставшегося дерева, производительность поиска пропорциональна производительности двоичного логарифма . BST были разработаны в 1960-х годах для решения проблемы эффективного хранения помеченных данных и приписываются Конвею Бернерсу-Ли и Дэвиду Уилеру .

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

Анализ сложности BST показывает, что в среднем вставка, удаление и поиск занимают для узлов. В худшем случае они деградируют до односвязного списка: . Для решения проблемы безграничного увеличения высоты дерева с произвольными вставками и удалениями вводятся самобалансирующиеся варианты BST, чтобы ограничить наихудшую сложность поиска сложностью двоичного логарифма. Деревья AVL были первыми самобалансирующимися двоичными деревьями поиска, изобретенными в 1962 году Георгием Адельсоном-Вельским и Евгением Ландисом . $O(\log n)$ $n$ $O(n)$

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

История

Алгоритм двоичного дерева поиска был открыт независимо несколькими исследователями, включая П. Ф. Уиндли, Эндрю Дональда Бута , Эндрю Колина , Томаса Н. Хиббарда . ^[1]^[2] Алгоритм приписывается Конвею Бернерсу-Ли и Дэвиду Уиллеру , которые использовали его для хранения помеченных данных на магнитных лентах в 1960 году. ^[3] Одним из самых ранних и популярных алгоритмов двоичного дерева поиска является алгоритм Хиббарда. ^[1]

Временная сложность двоичного дерева поиска неограниченно возрастает с высотой дерева, если узлы вставляются в произвольном порядке, поэтому были введены самобалансирующиеся двоичные деревья поиска, чтобы ограничить высоту дерева до . ^[4] Были введены различные сбалансированные по высоте двоичные деревья поиска, чтобы ограничить высоту дерева, такие как деревья AVL , Treaps и красно-черные деревья . ^[5] $O(\log n)$

Дерево AVL было изобретено Георгием Адельсоном-Вельским и Евгением Ландисом в 1962 году для эффективной организации информации. ^[6]^[7] Это было первое самобалансирующееся бинарное дерево поиска, которое было изобретено. ^[8]

Обзор

Двоичное дерево поиска — это корневое двоичное дерево, в котором узлы расположены в строгом общем порядке , в котором узлы с ключами, большими, чем любой конкретный узел A, хранятся в правых поддеревьях этого узла A , а узлы с ключами, равными или меньшими, чем A, хранятся в левых поддеревьях A, удовлетворяя свойству бинарного поиска . ^[9]^{: 298}^[10]^{: 287}

Двоичные деревья поиска также эффективны в сортировках и алгоритмах поиска . Однако сложность поиска BST зависит от порядка, в котором узлы вставляются и удаляются; поскольку в худшем случае последовательные операции в двоичном дереве поиска могут привести к вырождению и формированию структуры, подобной односвязному списку (или «несбалансированному дереву»), таким образом, имеет ту же самую сложность в худшем случае, что и связанный список . ^[11]^[9]^{: 299-302}

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

Операции

Идет поиск

Поиск определенного ключа в двоичном дереве поиска можно запрограммировать рекурсивно или итеративно .

Поиск начинается с проверки корневого узла . Если дерево равно nil , искомый ключ не существует в дереве. В противном случае, если ключ равен ключу корня, поиск успешен и узел возвращается. Если ключ меньше ключа корня, поиск продолжается путем проверки левого поддерева. Аналогично, если ключ больше ключа корня, поиск продолжается путем проверки правого поддерева. Этот процесс повторяется до тех пор, пока ключ не будет найден или оставшееся поддерево не будет . Если искомый ключ не найден после достижения поддерева, то ключ отсутствует в дереве. ^[10]^{: 290–291} ${\text{ноль}}$ ${\text{ноль}}$

Рекурсивный поиск

Следующий псевдокод реализует процедуру поиска BST посредством рекурсии . ^[10]^{: 290}

Рекурсивная процедура продолжается до тех пор, пока не будет найдено искомое слово или . ${\text{ноль}}$ ${\text{ключ}}$

Итеративный поиск

Рекурсивная версия поиска может быть «развернута» в цикл while . На большинстве машин итеративная версия оказывается более эффективной . ^[10]^{: 291}

Поскольку поиск может продолжаться до некоторого листового узла , сложность времени выполнения поиска BST равна , где — высота дерева . Однако наихудший случай для поиска BST равен , где — общее количество узлов в BST, поскольку несбалансированный BST может выродиться в связанный список. Однако, если BST сбалансирован по высоте, то высота равна . ^[10]^{: 290} $O(h)$ $ч$ $O(n)$ $n$ $O(\log n)$

Преемник и предшественник

Для некоторых операций, учитывая узел , нахождение преемника или предшественника имеет решающее значение. Предполагая, что все ключи BST различны, преемником узла в BST является узел с наименьшим ключом, большим, чем ключ '. С другой стороны, предшественником узла в BST является узел с наибольшим ключом, меньшим, чем ключ '. Следующий псевдокод находит преемника и предшественника узла в BST. ^[12]^[13]^[10]^{: 292–293} ${\text{x}}$ ${\text{x}}$ ${\text{x}}$ ${\text{x}}$ ${\text{x}}$ ${\text{x}}$ ${\text{x}}$

Такие операции, как поиск узла в BST, ключ которого является максимальным или минимальным, имеют решающее значение в определенных операциях, таких как определение преемника и предшественника узлов. Ниже приведен псевдокод для операций. ^[10]^{: 291–292}

Вставка

Такие операции, как вставка и удаление, вызывают динамическое изменение представления BST. Структура данных должна быть изменена таким образом, чтобы свойства BST продолжали сохраняться. Новые узлы вставляются как листовые узлы в BST. ^[10]^{: 294–295} Ниже приведена итеративная реализация операции вставки. ^[10]^{: 294}

Процедура поддерживает «конечный указатель» как родительский элемент . После инициализации в строке 2 цикл while в строках 4–11 приводит к обновлению указателей. Если равно , BST пуст, поэтому вставляется как корневой узел двоичного дерева поиска , если нет , вставка продолжается путем сравнения ключей с ключами в строках 15–19, и узел вставляется соответствующим образом. ^[10]^{: 295} ${\text{y}}$ ${\text{x}}$ ${\text{y}}$ ${\text{ноль}}$ ${\text{z}}$ ${\text{T}}$ ${\text{ноль}}$ ${\text{y}}$

Удаление

Удаление узла, скажем , из двоичного дерева поиска имеет три случая: ^[10]^{: 295-297} ${\text{Z}}$ ${\text{БСТ}}$

Если является листовым узлом, родительский узел заменяется на и, следовательно, удаляется из , как показано на (а). ${\text{Z}}$ ${\text{Z}}$ ${\text{NIL}}$ ${\text{Z}}$ ${\text{БСТ}}$
Если имеется только один дочерний узел, то дочерний узел повышается путем изменения родительского узла так, чтобы он указывал на дочерний узел, и, следовательно, занимает положение в дереве, как показано на рисунках (b) и (c). ${\text{Z}}$ ${\text{Z}}$ ${\text{Z}}$ ${\text{Z}}$
Если есть и левые, и правые потомки, то последователем , скажем , является , который смещается в соответствии с двумя случаями: ${\text{Z}}$ ${\text{Z}}$ ${\text{Y}}$ ${\text{Z}}$
1. Если это правый дочерний элемент , как показано в (d), то он смещается , а правый дочерний элемент остается неизменным. ${\text{Y}}$ ${\text{Z}}$ ${\text{Y}}$ ${\text{Z}}$ ${\text{Y}}$
2. Если лежит в правом поддереве , но не является правым потомком , как показано в (e), то сначала заменяется своим собственным правым потомком, а затем смещает позицию в дереве. ${\text{Y}}$ ${\text{Z}}$ ${\text{Z}}$ ${\text{Y}}$ ${\text{Z}}$

Следующий псевдокод реализует операцию удаления в бинарном дереве поиска. ^[10]^{: 296-298}

Процедура имеет дело с тремя особыми случаями, упомянутыми выше. Строки 2-3 имеют дело со случаем 1; строки 4-5 имеют дело со случаем 2, а строки 6-16 — со случаем 3. Вспомогательная функция используется в алгоритме удаления с целью замены узла на в бинарном дереве поиска . ^[10]^{: 298} Эта процедура обрабатывает удаление (и замену) из . ${\text{BST-Удалить}}$ ${\text{Сдвиг-Узлы}}$ ${\text{u}}$ ${\text{v}}$ ${\text{БСТ}}$ ${\text{u}}$ ${\text{БСТ}}$

Прохождение

BST можно обойти с помощью трех основных алгоритмов: симметричный , прямой и обратный обходы дерева. ^[10]^{: 287}

Inorder tree walk : Сначала посещаются узлы из левого поддерева, затем корневой узел и правое поддерево. Такой обход посещает все узлы в порядке неубывания ключевой последовательности.
Предварительный обход дерева : сначала посещается корневой узел, затем левое и правое поддеревья.
Обход дерева в обратном порядке : сначала посещаются узлы левого поддерева, затем правого поддерева и, наконец, корня.

Ниже представлена рекурсивная реализация обхода дерева. ^[10]^{: 287–289}

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

Без повторной балансировки вставки или удаления в бинарном дереве поиска могут привести к вырождению, что приведет к высоте дерева (где — количество элементов в дереве), так что производительность поиска ухудшится до уровня линейного поиска. ^[14] Поддержание сбалансированности дерева поиска и ограничения высоты является ключом к полезности бинарного дерева поиска. Это может быть достигнуто с помощью механизмов «самобалансировки» во время операций обновления дерева, разработанных для поддержания высоты дерева в соответствии с двоичной логарифмической сложностью. ^[4]^[15]^{: 50} $n$ $n$ $O(\log n)$

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

Дерево сбалансировано по высоте, если высоты левого поддерева и правого поддерева гарантированно связаны постоянным множителем. Это свойство было введено деревом AVL и продолжено красно-черным деревом . ^[15]^{: 50–51} Высоты всех узлов на пути от корня до измененного листового узла должны наблюдаться и, возможно, корректироваться при каждой операции вставки и удаления в дереве. ^[15]^{: 52}

Деревья со сбалансированным весом

В сбалансированном по весу дереве критерием сбалансированного дерева является количество листьев поддеревьев. Веса левого и правого поддеревьев отличаются не более чем на . ^[16]^[15]^{: 61} Однако разница ограничена отношением весов, поскольку сильное условие баланса не может поддерживаться с помощью работы по перебалансировке во время операций вставки и удаления. Сбалансированные по весу деревья дают целое семейство условий баланса, где каждое левое и правое поддеревья имеют по крайней мере часть от общего веса поддерева. ^[15]^{: 62} $1$ $\альфа$ $1$ $O(\log n)$ $\альфа$ $\альфа$

Типы

Существует несколько самобалансирующихся двоичных деревьев поиска, включая T-дерево , ^[17] дерево treap , ^[18] красно-черное дерево , ^[19] B-дерево , ^[20] дерево 2–3 , ^[21] и дерево Splay . ^[22]

Примеры применения

Сортировать

Бинарные деревья поиска используются в алгоритмах сортировки, таких как сортировка дерева , где все элементы вставляются одновременно, а дерево просматривается в упорядоченном виде. ^[23] BST также используются в быстрой сортировке . ^[24]

Приоритетные операции очереди

Двоичные деревья поиска используются при реализации приоритетных очередей , используя ключ узла в качестве приоритетов. Добавление новых элементов в очередь следует за обычной операцией вставки BST, но операция удаления зависит от типа приоритетной очереди: ^[25]

Если это очередь с возрастающим приоритетом, удаление элемента с самым низким приоритетом выполняется путем обхода BST влево.
Если это очередь с убывающим приоритетом, удаление элемента с наивысшим приоритетом выполняется посредством правого обхода BST.

Смотрите также

Ссылки

^ ab Culberson, J.; Munro, JI (1 января 1989 г.). «Объяснение поведения двоичных деревьев поиска при длительных обновлениях: модель и моделирование». The Computer Journal . 32 (1): 68–69. doi : 10.1093/comjnl/32.1.68 .
^ Калберсон, Дж.; Манро, Дж.И. (28 июля 1986 г.). «Анализ стандартных алгоритмов удаления в бинарных деревьях поиска с точным соответствием домена». Algorithmica . 5 (1–4). Springer Publishing , Университет Ватерлоо : 297. doi :10.1007/BF01840390. S2CID 971813.
^ PF Windley (1 января 1960 г.). «Деревья, леса и перестановка». The Computer Journal . 3 (2): 84. doi : 10.1093/comjnl/3.2.84 .
^ ab Knuth, Donald (1998). "Раздел 6.2.3: Сбалансированные деревья". Искусство программирования (PDF) . Том 3 (2-е изд.). Addison-Wesley . С. 458–481. ISBN 978-0201896855. Архивировано (PDF) из оригинала 2022-10-09.
^ Пол Э. Блэк, «красно-черное дерево», в Словаре алгоритмов и структур данных [онлайн], Пол Э. Блэк, ред. 12 ноября 2019 г. (дата обращения: 19 мая 2022 г.) с: https://www.nist.gov/dads/HTML/redblack.html
^ Майерс, Эндрю. "CS 312 Lecture: AVL Trees". Корнелльский университет , кафедра компьютерных наук. Архивировано из оригинала 27 апреля 2021 г. Получено 19 мая 2022 г.
^ Адельсон-Вельский, Георгий; Ландис, Евгений (1962). «Алгоритм организации информации». Известия АН СССР . 146 : 263–266.Перевод на английский язык Майрона Дж. Риччи в сборнике «Советская математика» — Доклады , 3:1259–1263, 1962.
^ Pitassi, Toniann (2015). "CSC263: Balanced BSTs, AVL tree" (PDF) . Университет Торонто , Кафедра компьютерных наук. стр. 6. Архивировано (PDF) из оригинала 14 февраля 2019 г. . Получено 19 мая 2022 г. .
^ ab Thareja, Reema (13 октября 2018 г.). «Хеширование и коллизия». Data Structures Using C (2-е изд.). Oxford University Press . ISBN 9780198099307.
^ abcdefghijklmno Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). Введение в алгоритмы (2-е изд.). МТИ Пресс . ISBN 0-262-03293-7.
^ RA Frost; MM Peterson (1 февраля 1982 г.). «Краткая заметка о бинарных деревьях поиска». The Computer Journal . 25 (1). Oxford University Press : 158. doi :10.1093/comjnl/25.1.158.
^ Junzhou Huang. «Проектирование и анализ алгоритмов» (PDF) . Техасский университет в Арлингтоне . стр. 12. Архивировано (PDF) из оригинала 13 апреля 2021 г. . Получено 17 мая 2021 г. .
^ Рэй, Рэй. «Двоичное дерево поиска». Университет Лойола Мэримаунт , кафедра компьютерных наук . Получено 17 мая 2022 г.
^ Торнтон, Алекс (2021). «ICS 46: Двоичные деревья поиска». Калифорнийский университет в Ирвайне . Архивировано из оригинала 4 июля 2021 г. Получено 21 октября 2021 г.
^ abcde Брасс, Питер (январь 2011 г.). Расширенная структура данных. Cambridge University Press . doi :10.1017/CBO9780511800191. ISBN 9780511800191.
^ Блюм, Норберт; Мельхорн, Курт (1978). «О среднем числе операций перебалансировки в деревьях с весовым балансом» (PDF) . Теоретическая информатика . 11 (3): 303–320. doi :10.1016/0304-3975(80)90018-3. Архивировано (PDF) из оригинала 2022-10-09.
^ Леман, Тобин Дж.; Кэри, Майкл Дж. (25–28 августа 1986 г.). Исследование структур индексов для систем управления базами данных с основной памятью . Двенадцатая международная конференция по сверхбольшим базам данных (VLDB 1986). Киото. ISBN 0-934613-18-4.
^ Арагон, Сесилия Р.; Зайдель, Раймунд (1989), «Рандомизированные деревья поиска» (PDF) , 30-й ежегодный симпозиум по основам компьютерной науки , Вашингтон, округ Колумбия: IEEE Computer Society Press, стр. 540–545, doi :10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1, архив (PDF) из оригинала 2022-10-09
^ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). «Красно-черные деревья». Введение в алгоритмы (второе изд.). MIT Press. стр. 273–301. ISBN 978-0-262-03293-3.
↑ Комер, Дуглас (июнь 1979 г.), «Вездесущее B-дерево», Computing Surveys , 11 (2): 123–137, doi : 10.1145/356770.356776 , ISSN 0360-0300, S2CID 101673
^ Кнут, Дональд М (1998). "6.2.4". Искусство программирования . Том 3 (2-е изд.). Эддисон Уэсли. ISBN 9780201896855Деревья 2–3 , определенные в конце раздела 6.2.3, эквивалентны B-деревьям порядка 3.
^ Sleator, Daniel D. ; Tarjan, Robert E. (1985). «Саморегулирующиеся двоичные деревья поиска» (PDF) . Journal of the ACM . 32 (3): 652–686. doi :10.1145/3828.3835. S2CID 1165848.
^ Нараянан, Арвинд (2019). «COS226: Двоичные деревья поиска». Школа инженерии и прикладных наук Принстонского университета . Архивировано из оригинала 22 марта 2021 г. Получено 21 октября 2021 г. – через cs.princeton.edu.
^ Сюн, Ли. «Связь между двоичными деревьями поиска и быстрой сортировкой». Оксфордский колледж Университета Эмори , Кафедра математики и компьютерных наук. Архивировано из оригинала 26 февраля 2021 г. Получено 4 июня 2022 г.
^ Майерс, Эндрю. «CS 2112 Lecture and Recitation Notes: Priority Queues and Heaps». Корнелльский университет , кафедра компьютерных наук . Архивировано из оригинала 21 октября 2021 г. Получено 21 октября 2021 г.

Дальнейшее чтение

В этой статье использованы материалы, находящиеся в открытом доступе, от Пола Э. Блэка. «Двоичное дерево поиска». Словарь алгоритмов и структур данных . NIST .
Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "12: Двоичные деревья поиска, 15.5: Оптимальные бинарные деревья поиска". Введение в алгоритмы (2-е изд.). MIT Press . стр. 253–272, 356–363. ISBN 0-262-03293-7.
Jarc, Duane J. (3 декабря 2005 г.). "Binary Tree Traversals". Interactive Data Structure Visualizations . University of Maryland . Архивировано из оригинала 27 февраля 2014 г. Получено 30 апреля 2006 г.
Кнут, Дональд (1997). "6.2.2: Поиск в двоичном дереве". Искусство программирования . Том 3: "Сортировка и поиск" (3-е изд.). Addison-Wesley. С. 426–458. ISBN 0-201-89685-0.
Лонг, Шон. "Двоичное дерево поиска" ( PPT ) . Визуализация структур данных и алгоритмов — подход на основе слайдов PowerPoint . SUNY Oneonta .
Парланте, Ник (2001). «Двоичные деревья». Библиотека CS Education . Стэнфордский университет . Архивировано из оригинала 2022-01-30.

Внешние ссылки

На Викискладе есть медиафайлы по теме «Двоичные деревья поиска» .

Бен Пфафф: Введение в двоичные деревья поиска и сбалансированные деревья. (PDF; 1675 кБ) 2004.
Визуализатор двоичного дерева (JavaScript-анимация различных структур данных на основе BT)