Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
В інформатиці де́рево пошуку (як структура даних) — це деревоподібна структура даних, яку застосовують для пошуку конкретних ключів усередині множини. Щоб дерево могло функціонувати як дерево пошуку, ключ кожного вузла повинен бути більшим за будь-які ключі в піддеревах ліворуч і менше будь-яких ключів у піддеревах праворуч.
Перевагою дерев пошуку є їх ефективний час пошуку за умови, що дерево достатньо збалансоване, тобто листя на обох кінцях мають подібну глибину. Існують різні види структур даних, які є деревами пошуку. Деякі з них також дозволяють ефективно додавати та видаляти елементи. Операції на таких деревах потім повинні підтримувати баланс дерева.
Дерева пошуку часто застосовуються для реалізації асоціативного масиву. Алгоритм дерева пошуку використовує ключ від пари ключ-значення, щоб знайти місце, а потім програма зберігає всю пару ключ-значення у цьому конкретному місці.
Загальні відомості
Дерева пошуку призначені для представлення словників як абстрактного типу даних. Як і пріоритетні черги, вони представляють зважені множини, але з іншим набором операцій, а саме:
- Search — пошук елемента із заданим ключем.
- Minimum — пошук елемента з мінімальним ключем.
- Maximum — пошук елемента з максимальним ключем.
- Predecessor — пошук елемента з попереднім ключем.
- Successor — пошук елемента з наступним ключем.
- Insert — вставка елемента зі своїм ключем.
- Delete — видалення зазначеного елемента.
Вважається, що кожен елемент словника має ключ (вагу), що приймає значення з лінійно впорядкованої множини. Такою множиною може бути, наприклад, числова множина або множина слів в деякому алфавіті. В останньому випадку як лінійний можна розглядати лексикографічний порядок. Таким чином, дерево пошуку може бути використано і як словник, і як пріоритетна черга. Час виконання основних операцій пропорційний висоті дерева. Якщо кожен внутрішній вузол двійкового дерева має рівно двох нащадків, то його висота і час виконання основних операцій пропорційні логарифму числа вузлів. І навпаки, якщо дерево являє собою лінійний ланцюжок з n вузлів, цей час виростає до Ο(n). Відомо, що висота випадкового двійкового дерева є Ο(log n), так що в цьому випадку час виконання основних операцій є Ο(log n). Звичайно, що виникаючі на практиці двійкові дерева пошуку можуть бути далекі від випадкових. Однак, прийнявши спеціальні заходи по балансуванню дерев, можна гарантувати, що висота дерев з n вузлами буде O(log n).
Види дерев
Двійкове дерево пошуку
Бінарне дерево пошуку — це структура даних на основі вузлів, де кожен вузол містить ключ і два піддерева, лівий та правий. Для всіх вузлів ключ лівого піддерева повинен бути меншим ніж ключ вузла, а ключ правого піддерева повинен бути більшим ніж ключ вузла. Усі ці піддерева повинні бути двійковими деревами пошуку.
Найгірша часова складність операції пошуку у двійковому дереві пошуку — це (висота дерева), яка може бути такою ж малою, як O (log n) для дерева з n елементами.
Б-дерево
Б-дерева — це узагальнення двійкових дерев пошуку, оскільки будь-який вузол у такому дереві може мати змінну кількість піддерев. Хоча вузли-діти мають заздалегідь визначений розмір(порядок), вони не обов'язково будуть заповнені даними, тобто Б-дерева можуть потенційно займати місце в пам'яті, але не використовувати його. Перевага полягає в тому, що Б-дереву не потрібно перебалансовуватися так часто, як іншим самобалансованим деревам.
Завдяки змінному розміру вузла, Б-дерева оптимізовані для систем, які зчитують великі блоки даних. Вони також часто застосовуються в базах даних.
Часова складність операції пошуку в Б-дереві становить O (log n).
(а, б)-дерево
(а, б)-дерево — це дерево пошуку, в якому всі його листя мають однакову глибину. Кожен вузол має, щонайменше а дітей та щонайбільше б дітей, в той час як корінь має щонайменше 2 дітей і щонайбільше б дітей.
Часова складність пошуку в (a, b)-дереві становить O (log n).
Трійкове дерево пошуку
Трійкове дерево пошуку — це дерево, в якому кожен вузол зберігає один символ, а саме дерево упорядковується так само, як і двійкове дерево пошуку, за винятком можливого третього вузла.
Пошук у трійковому дереві пошуку передбачає передачу стрічки, щоб перевірити, чи містить її якийсь шлях.
Часова складність операції пошуку в збалансованому трійковому дереві пошуку дорівнює O (log n).
Див. також
Джерела
- Thomas H. Cormen, Charles E. Leiserson. Introduction to algorithms.
| Ця стаття потребує додаткових для поліпшення її . (Квітень 2021) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V informatici de revo poshuku yak struktura danih ce derevopodibna struktura danih yaku zastosovuyut dlya poshuku konkretnih klyuchiv useredini mnozhini Shob derevo moglo funkcionuvati yak derevo poshuku klyuch kozhnogo vuzla povinen buti bilshim za bud yaki klyuchi v pidderevah livoruch i menshe bud yakih klyuchiv u pidderevah pravoruch Perevagoyu derev poshuku ye yih efektivnij chas poshuku za umovi sho derevo dostatno zbalansovane tobto listya na oboh kincyah mayut podibnu glibinu Isnuyut rizni vidi struktur danih yaki ye derevami poshuku Deyaki z nih takozh dozvolyayut efektivno dodavati ta vidalyati elementi Operaciyi na takih derevah potim povinni pidtrimuvati balans dereva Dereva poshuku chasto zastosovuyutsya dlya realizaciyi asociativnogo masivu Algoritm dereva poshuku vikoristovuye klyuch vid pari klyuch znachennya shob znajti misce a potim programa zberigaye vsyu paru klyuch znachennya u comu konkretnomu misci Zagalni vidomostiDereva poshuku priznacheni dlya predstavlennya slovnikiv yak abstraktnogo tipu danih Yak i prioritetni chergi voni predstavlyayut zvazheni mnozhini ale z inshim naborom operacij a same Search poshuk elementa iz zadanim klyuchem Minimum poshuk elementa z minimalnim klyuchem Maximum poshuk elementa z maksimalnim klyuchem Predecessor poshuk elementa z poperednim klyuchem Successor poshuk elementa z nastupnim klyuchem Insert vstavka elementa zi svoyim klyuchem Delete vidalennya zaznachenogo elementa Vvazhayetsya sho kozhen element slovnika maye klyuch vagu sho prijmaye znachennya z linijno vporyadkovanoyi mnozhini Takoyu mnozhinoyu mozhe buti napriklad chislova mnozhina abo mnozhina sliv v deyakomu alfaviti V ostannomu vipadku yak linijnij mozhna rozglyadati leksikografichnij poryadok Takim chinom derevo poshuku mozhe buti vikoristano i yak slovnik i yak prioritetna cherga Chas vikonannya osnovnih operacij proporcijnij visoti dereva Yaksho kozhen vnutrishnij vuzol dvijkovogo dereva maye rivno dvoh nashadkiv to jogo visota i chas vikonannya osnovnih operacij proporcijni logarifmu chisla vuzliv I navpaki yaksho derevo yavlyaye soboyu linijnij lancyuzhok z n vuzliv cej chas virostaye do O n Vidomo sho visota vipadkovogo dvijkovogo dereva ye O log n tak sho v comu vipadku chas vikonannya osnovnih operacij ye O log n Zvichajno sho vinikayuchi na praktici dvijkovi dereva poshuku mozhut buti daleki vid vipadkovih Odnak prijnyavshi specialni zahodi po balansuvannyu derev mozhna garantuvati sho visota derev z n vuzlami bude O log n Vidi derevDvijkove derevo poshuku Dokladnishe Dvijkove derevo poshuku Binarne derevo poshuku ce struktura danih na osnovi vuzliv de kozhen vuzol mistit klyuch i dva piddereva livij ta pravij Dlya vsih vuzliv klyuch livogo piddereva povinen buti menshim nizh klyuch vuzla a klyuch pravogo piddereva povinen buti bilshim nizh klyuch vuzla Usi ci piddereva povinni buti dvijkovimi derevami poshuku Najgirsha chasova skladnist operaciyi poshuku u dvijkovomu derevi poshuku ce visota dereva yaka mozhe buti takoyu zh maloyu yak O log n dlya dereva z n elementami B derevo Dokladnishe B derevo B dereva ce uzagalnennya dvijkovih derev poshuku oskilki bud yakij vuzol u takomu derevi mozhe mati zminnu kilkist pidderev Hocha vuzli diti mayut zazdalegid viznachenij rozmir poryadok voni ne obov yazkovo budut zapovneni danimi tobto B dereva mozhut potencijno zajmati misce v pam yati ale ne vikoristovuvati jogo Perevaga polyagaye v tomu sho B derevu ne potribno perebalansovuvatisya tak chasto yak inshim samobalansovanim derevam Zavdyaki zminnomu rozmiru vuzla B dereva optimizovani dlya sistem yaki zchituyut veliki bloki danih Voni takozh chasto zastosovuyutsya v bazah danih Chasova skladnist operaciyi poshuku v B derevi stanovit O log n a b derevo Dokladnishe a b derevo ce derevo poshuku v yakomu vsi jogo listya mayut odnakovu glibinu Kozhen vuzol maye shonajmenshe a ditej ta shonajbilshe b ditej v toj chas yak korin maye shonajmenshe 2 ditej i shonajbilshe b ditej Chasova skladnist poshuku v a b derevi stanovit O log n Trijkove derevo poshuku Dokladnishe Trijkove derevo poshuku Trijkove derevo poshuku ce derevo v yakomu kozhen vuzol zberigaye odin simvol a same derevo uporyadkovuyetsya tak samo yak i dvijkove derevo poshuku za vinyatkom mozhlivogo tretogo vuzla Poshuk u trijkovomu derevi poshuku peredbachaye peredachu strichki shob pereviriti chi mistit yiyi yakijs shlyah Chasova skladnist operaciyi poshuku v zbalansovanomu trijkovomu derevi poshuku dorivnyuye O log n Div takozhDvijkove derevo poshuku B derevo Zbalansovane derevo Chervono chorne derevoDzherelaThomas H Cormen Charles E Leiserson Introduction to algorithms Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno Kviten 2021