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

Двоичное дерево поиска
Тип дерево
Год изобретения 1960
Автор Andrew Donald Booth[вд]
Сложность в О-символике
В среднем В худшем случае
Расход памяти 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 текущего узла новым значением.

Удаление узла (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 раз (самый длинный путь в 2 раза длиннее самого короткого). АВЛ-дерево требует не более двух поворотов после добавления и до глубины дерева после удаления, но при этом идеально сбалансировано (дисбаланс не более, чем на 1).

См. также

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

Примечания

  1. Роман Акопов. Двоичные деревья поиска. RSDN Magazine #5-2003 (13 марта 2005). Дата обращения: 1 ноября 2014. Архивировано 1 ноября 2014 года.

Read other articles:

Untuk pesepak bola Inggris abad ke-19, lihat James F. M. Prinsep. James PrinsepJames Prinsep digambarkan dalam medali yang dibuat sekitar tahun 1840 dari National Portrait GalleryLahir20 Agustus 1799InggrisMeninggal22 April 1840(1840-04-22) (umur 40)London, InggrisKarya akademisMinat utamaNumismatik, Filologi, Metalurgi dan MeteorologiKarya terkenalJournal of the Asiatic Society of BengalPemikiran pentingMeneliti aksara-aksara Kharosthi dan Brahmi James Prinsep FRS (20 Agustus 1799 ...

 

 

Harry BenhamCuplikan Benham merancang sebuah pistol dalam serial Thanhouser tahun 1914 Zudora.Lahir(1884-02-26)26 Februari 1884Valparaiso, Indiana, Amerika SerikatMeninggal17 Juli 1969(1969-07-17) (umur 85)Sarasota, Florida, Amerika SerikatPekerjaanPemeran, penyanyiSuami/istriEthyle CookeAnak2 Harry Benham (26 Februari 1884 – 17 Juli 1969) adalah seorang pemeran film bisu Amerika Serikat. Latar belakang Benham dengan istrinya Ethyle Cooke beserta anak-anaknya Leland dan ...

 

 

Kasmidi Bulang Wakil Bupati Kutai Timur ke-4PetahanaMulai menjabat 26 Februari 2021PresidenJoko WidodoGubernurIsran NoorMasa jabatan17 Februari 2016 – 3 Juli 2020PresidenJoko WidodoGubernurAwang Faroek IshakRestuardy Daud (Pj.)Isran Noor PendahuluArdiansyah SulaimanPenggantiPetahanaPelaksana Tugas Bupati Kutai TimurMasa jabatan3 Juli 2020 – 17 Februari 2021PresidenJoko WidodoGubernurIsran Noor PendahuluIsmunandarPenggantiArdiansyah Sulaiman Informasi pribadiLahir...

العلاقات الإكوادورية الباكستانية الإكوادور باكستان   الإكوادور   باكستان تعديل مصدري - تعديل   العلاقات الإكوادورية الباكستانية هي العلاقات الثنائية التي تجمع بين الإكوادور وباكستان.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية �...

 

 

Part of a series onBritish law Acts of Parliament of the United Kingdom Year      1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 ...

 

 

Election for the governorship of the U.S. state of South Dakota 1960 South Dakota gubernatorial election ← 1958 November 8, 1960 1962 →   Nominee Archie M. Gubbrud Ralph Herseth Party Republican Democratic Popular vote 154,530 150,095 Percentage 50.73% 49.27% County results Gubbrud:      50-60%      60-70%      70-80% Herseth:      50–60%    ...

This article is about the Moste District. For the former village of Moste, see Moste (Ljubljana). District in Upper Carniola, SloveniaMoste District Četrtna skupnost MosteDistrictMap of districts in Ljubljana. The Moste District is number 7.Moste DistrictLocation in SloveniaCoordinates: 46°04′07″N 14°32′02″E / 46.06861°N 14.53389°E / 46.06861; 14.53389Country SloveniaTraditional regionUpper CarniolaStatistical regionCentral SloveniaMunicipalityLjubljanaAre...

 

 

بيثيسدا سوفت ووركسBethesda Softworks, LLCالشعارمعلومات عامةسميت باسم بركة بيت حسدا البلد  الولايات المتحدة[1] التأسيس 1986 في بيثيسداالنوع شركة تابعة لـ زيني ماكس ميدياالشكل القانوني شركة ذات مسؤولية محدودة المقر الرئيسي روكفيل[2][3][1] على الخريطة موقع الويب bethesda.net ...

 

 

此條目可能包含不适用或被曲解的引用资料,部分内容的准确性无法被证實。 (2023年1月5日)请协助校核其中的错误以改善这篇条目。详情请参见条目的讨论页。 各国相关 主題列表 索引 国内生产总值 石油储量 国防预算 武装部队(军事) 官方语言 人口統計 人口密度 生育率 出生率 死亡率 自杀率 谋杀率 失业率 储蓄率 识字率 出口额 进口额 煤产量 发电量 监禁率 死刑 国债 ...

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl(英文)(波兰文)2020年夏季奥林匹克运动会(東京)2021年7月23日至8月8日(受2019冠状病毒病疫情影响推迟,但仍保留原定名称)運動員206參賽項目24个大项旗手开幕式:帕维尔·科热尼奥夫斯基(游泳)和马娅·沃什乔夫斯卡(自行车)[1]闭幕式:卡罗利娜·纳亚(皮划艇)&#...

 

 

Turkish-American data and computer scientist (born 1977) Ilkay Altintasİlkay AltıntaşAltintas in 2019Bornİlkay Altıntaş1977 (age 46–47)Aydın, TurkeyCitizenshipTurkeyUnited StatesAlma materMiddle East Technical UniversityUniversity of AmsterdamKnown forKepler scientific workflow system[2]Scientific careerFields Data science Big data Workflow management Distributed computing Provenance Reproducibility[1] InstitutionsUniversity of California, San Diego...

 

 

ثقافة — جغرافيا — تاريخ — علوم — مجتمع — تقانة — رياضة قائمة البوابات بوابات شقيقة بوابة الإسلام بوابة القرآن بوابة محمد بوابة المدينة المنورة بوابة القدس بوابة مساجد بوابة التاريخ الإسلامي بوابة العلم في عصر الحضارة الإسلامية بوابة السعودية عدّل  مُقدّمة مكة المكر...

Radio transmission site on the Isle of Wight, England Chillerton DownThe Chillerton Down transmitting stationChillerton Down transmitting station (Isle of Wight)Mast height228.9 metres (751 ft)Coordinates50°38′57″N 1°19′44″W / 50.649167°N 1.328889°W / 50.649167; -1.328889Grid referenceSZ475835Built30 August 1958ITV regionSouthern Television (1958-1981)TVS (1982-1985) The Chillerton Down transmitting station is a broadcasting facility for FM and DAB ra...

 

 

České Budějovice BudweisKotaFrom top: Alun-alun Ottokar II., Kolam renang kota, Katedral St. Nicholas, Máj Centre, Pusat perbelanjaan IGY, Fakultas Filsafat Universitas Bohemia Selatan, Rumah sakit BenderaLambang kebesaranWordmarkČeské BudějoviceLokasi kota di Republik CekoKoordinat: 48°58′29″N 14°28′29″E / 48.97472°N 14.47472°E / 48.97472; 14.47472Negara CekoRegionBohemia SelatanDistrikČeské BudějovicePertama disebut1251Pemerintahan •...

 

 

Beragam jenis kapasitor Ukuran beragam jenis kapasitor Kapasitor adalah komponen listrik yang digunakan untuk menyimpan muatan listrik. Bahan penyusun kapasitor yaitu dua keping atau dua lembaran penghantar listrik yang dipisahkan menggunakan isolator listrik berupa bahan dielektrik. Masing-masing keping atau lembaran penghantar listrik diberi muatan listrik dalam jumlah yang sama tetapi berlainan jenis, yaitu muatan positif dan muatan negatif. Secara keseluruhan kapasitor sesungguhnya bermua...

← 1955 1954 1953 1956 في السعودية → 1957 1958 1959 عقود: طالع أيضاً:أحداث أخرى في 1956تاريخ السعودية تحتوي هذه المقالة على أهم الأحداث التي شهدتها السعودية في 1956، إضافة إلى أهم الشخصيات السعودية التي وُلدت أو تُوفيت في هذه السنة. السياسة الحكم الملك: سعود بن عبد العزيز آل سعود تعيينات تعيي�...

 

 

Radio station at North Carolina State University WKNC-FMRaleigh, North CarolinaUnited StatesBroadcast areaRaleigh-Durham, North CarolinaFrequency88.1 (MHz) (HD Radio)ProgrammingFormatIndie rock, electronic, hip-hop and heavy metalSubchannelsHD2: Indie rock,electronic, hip-hop and heavy metalHD3: Dance musicOwnershipOwnerNorth Carolina State UniversityHistoryFirst air dateOctober 9, 1966 (1966-10-09) (at 88.1 FM)Technical information[1]Licensing authorityFCCFacility ID49...

 

 

Kinot Lecture de kinot au pied du mur occidental à la veille de Tisha Beav, 2004 Sources halakhiques Textes dans la Loi juive relatifs à cet article Bible Lamentations Talmud de Jérusalem Shabbat 16, p. 15c Choulhan Aroukh Orah Hayim 559:2, 3, 5-7 Autres références rabbiniques Soferim 18:3 modifier  Les kinot (hébreu : קינות qinot « complaintes » ou « lamentations » ; singulier kina) sont des pièces liturgiques juives de lamentation, prenant...

French mathematician (1602–1675) Gilles de RobervalPortrait of Gilles Personne de Roberval (1602-1675) at the inauguration of the French Academy of Sciences, 1666, where he was a founding member.Born(1602-08-10)August 10, 1602Roberval near Beauvais, FranceDiedOctober 27, 1675(1675-10-27) (aged 73)Paris, FranceNationalityFrenchKnown forRoberval BalanceCoining the term 'trochoid'Scientific careerFieldsMathematicianInstitutionsGervais College, ParisRoyal College of FranceAcademic adv...

 

 

諸子百家 儒家 道家 法家 墨家 名家 陰陽家 縦横家 雑家 農家 小説家 兵家 表話編歴 カテゴリ 諸子百家(しょしひゃっか)とは、中国の春秋戦国時代に現れた学者・学派の総称。「諸子」は孔子・老子・荘子・墨子・孟子・荀子などの人物を指す。「百家」は儒家・道家・墨家・名家・法家などの学派を指す。 分類 諸子百家の「~家」の分類は、漢代の学者が後から与�...