Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Двійкове (або Бінарне) дéрево пóшуку (англ. binary search tree, BST) в інформатиці — двійкове дерево, в якому кожній вершині x зіставлене певне значення val[x]. При цьому такі значення повинні задовольняти умові впорядкованості:
- нехай x — довільна вершина двійкового дерева пошуку. Якщо вершина y знаходиться в лівому піддереві вершини x, то val[y] ≤ val[x].
- Якщо у знаходиться у правому піддереві x, то val[y] ≥ val[x].
| Двійкове дерево пошуку | ||
|---|---|---|
| Тип | Дерево | |
| Винайдено | 1960 | |
| Обчислювальна складність у записі великого О | ||
| Середня | Найгірша | |
| Простір | O(n) | O(n) |
| Пошук | O(log n) | O(n) |
| Вставляння | O(log n) | O(n) |
| Видалення | O(log n) | O(n) |
Таке структурування дозволяє надрукувати усі значення у зростаючому порядку за допомогою простого алгоритму центрованого обходу дерева.
Представляється таке дерево вузлами наступного вигляду:
*Node = (element, key, left, right, parent). Доступ до дерева T здійснюється за допомогою посилання root.
Бінарні дерева пошуку набагато ефективніші в операціях пошуку, аніж лінійні структури, в яких витрати часу на пошук пропорційні O(n), де n — розмір масиву даних, тоді як в повному бінарному дереві цей час пропорційний в середньому O(log2n) або O(h), де h — висота дерева (хоча гарантувати, що h не перевищує log2n можна лише для збалансованих дерев, які є ефективнішими в алгоритмах пошуку, аніж прості бінарні дерева пошуку).[]
Операції з двійковим деревом пошуку
Найпоширенішою операцією, яка виконується з бінарним деревом пошуку, є пошук в ньому певного ключа. Крім того, бінарні дерева пошуку підтримують такі запити, як пошук мінімального і максимального елемента, а також попереднього і наступного.
Пошук
Для пошуку вузла із заданим ключем в бінарному дереві пошуку використовується наступна процедура Tree_Search, яка отримує як параметри покажчик на корінь бінарного дерева і ключ k, а повертає покажчик на вузол з цим ключем (якщо такий існує; в іншому випадку повертається значення NIL).
| Tree_Search (x, k) |
|---|
1. if х = nil або k = key [x] 2. then return х 3. if k < key [x] 4. then return Tree_Search (left [x], k) 5. else return Tree_Search (right [x], k) |
Процедура пошуку починається з кореня дерева і проходить вниз по дереву. Для кожного вузла х на шляху вниз його ключ key[x] порівнюється з переданим як параметр ключем k. Якщо ключі однакові, пошук завершується. Якщо k менше key[х], пошук триває в лівому піддереві х; якщо більше — то пошук переходить в праве піддерево. Ту ж процедуру можна записати ітеративно, «розгортаючи» рекурсію в цикл while.
Ітеративна версія процедури Пошук
| Iterative_Tree_Search(x, k) |
|---|
1. while x ≠ NIL и k ≠ key[х] 2.do if k ← key[х] 3.then х ← left[x] 4.else х ← right[x] 5. return x |
Пошук мінімального (максимального) елемента
Алгоритм пошуку мінімального елемента. Елемент з мінімальним значенням ключа легко знайти, слідуючи за вказівниками left від кореневого вузла до тих пір, поки не зустрінеться значення NIL. Процедура TREE_MINIMUM(x) повертає покажчик на знайдений елемент піддерева з коренем x.
| TREE_MINIMUM(X) |
|---|
1. while left[x] ≠ NIL 2.do x ← left[x] 3. return x |
Алгоритм пошуку максимального елемента симетричний:
| TREE_MAXIMUM(X) |
|---|
1. while right[x] ≠ NIL 2.do x ← right[x] 3. return x |
Обидва алгоритми вимагають часу O(h), де h — висота дерева.
Наступний і попередній елементи
Якщо x — покажчик на деякий вузол дерева, то процедура TREE_SUCCESSOR(X) повертає покажчик на вузол з наступним за x елементом або nil, якщо зазначений елемент — останній в дереві:
| TREE_SUCCESSOR(X) |
|---|
1. if right[x] ≠ NIL 2.then return TREE_MINIMUM(right[x]) 3. у ← p[x] 4. while y ≠ NIL та x = right[y] 5.do x ← у 6.у ← p[y] 7. return у |
Наведена процедура окремо розглядає два випадки. Якщо праве піддерево вершини не пусте, то наступний за x елемент є крайнім лівим вузлом у правому піддереві, який виявляється процедурою TREE_MlNlMUM(right[x]). З іншого боку, якщо праве піддерево вузла x пусте, та у x існує наступний за ним елемент y, то y є найменшим предком x, чий лівий вузол також є предком x. Для того щоб знайти y, ми просто піднімаємося вгору по дереву до тих пір, поки не зустрінемо вузол, який є лівим дочірнім вузлом свого батька. Ця дія виконується в рядках 3-7 алгоритму.
Час роботи алгоритму TREE_SUCCESSOR в дереві заввишки h складає O(h), оскільки ми або рухаємося по шляху вниз від вихідного вузла, або по шляху нагору. Процедура пошуку подальшого вузла в дереві TREE_PREDECESSOR симетрична процедурі TREE_SUCCESSOR і також має час роботи O(h).
Якщо в дереві є вузли з однаковими ключами, ми можемо просто визначити наступний і попередній вузли як ті, що повертаються процедурами TREE_SUCCESSOR та TREE_PREDECESSOR відповідно.
Додавання елемента
Для вставки нового значення v в бінарне дерево пошуку Т ми скористаємося процедурою TREE_INSERT. Процедура отримує як параметр вузол z, у якого key[z] = v, left[z] = NIL і right[z] = NIL, після чого вона таким чином змінює Т і деякі поля z, що z виявляється вставленим в відповідну позицію в дереві.
| TREE_INSERT (T, Z) |
|---|
1. у ← NIL 2. х ← root[T] 3. while x ≠ NIL 4.do у ← x 5.if key[z] < key [x] 6. then x ← left[x] 7.else x ← right[x] 8. p [z] ← у 9. if у = NIL 10.then root[T] ← z// Дерево T - пусте 11.else if key[z] <key[y] 12. then left[y] ← z 13.else right[у] ← z |
Видалення елемента
Процедура видалення даного вузла z з бінарного дерева пошуку отримує як аргумент покажчик на z. Процедура розглядає три можливі ситуації:
- Якщо у вузла z немає дочірніх вузлів, то ми просто змінюємо його батьківський вузол р[z], замінюючи в ньому покажчик на z значенням NIL.
- Якщо у вузла z лише один дочірній вузол, то ми видаляємо вузол z, створюючи новий зв'язок між батьківським і дочірнім вузлом вузла z.
- Якщо у вузла z два дочірніх вузла, то ми знаходимо наступний за ним вузол у, у якого немає лівого дочірнього вузла, прибираємо його з позиції, де він перебував раніше, шляхом створення нового зв'язку між його батьком і нащадком, і замінюємо ним вузол Z.
DELETE (T, z) 1 if left[z] = NULL or right[z]=NULL 2 then y:=z 3 else y:=SUCCESSOR(z) 4 if left[y] <> NULL 5 then x:=left[y] 6 else x:= right[y] 7 if x <> NULL 8 then p[x]:=p[y] 9 if p[y]:=NULL 10 then root[T]:=x 11 else if y=left[p[y] ] 12 then left[p[y] ] :=x 13 else right[p[y] ]:=x 14 if y <> z 15 then val[z]:=val[y] 16 //копіювання додаткових даних з y 17 return y
Час на виконання цієї процедури є також O(h)
Див. також
| У Вікіджерелах є приклади реалізацій алгоритмів роботи з бінарними деревами пошуку |
Примітки
- Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. Розділ 12: Двійкові дерева пошуку. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
Джерела
- Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
- Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — .(англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Dvijkove abo Binarne derevo poshuku angl binary search tree BST v informatici dvijkove derevo v yakomu kozhnij vershini x zistavlene pevne znachennya val x Pri comu taki znachennya povinni zadovolnyati umovi vporyadkovanosti nehaj x dovilna vershina dvijkovogo dereva poshuku Yaksho vershina y znahoditsya v livomu pidderevi vershini x to val y val x Yaksho u znahoditsya u pravomu pidderevi x to val y val x Dvijkove derevo poshuku Tip Derevo Vinajdeno 1960 Obchislyuvalna skladnist u zapisi velikogo O Serednya Najgirsha Prostir O n O n Poshuk O log n O n Vstavlyannya O log n O n Vidalennya O log n O n Binarne derevo Take strukturuvannya dozvolyaye nadrukuvati usi znachennya u zrostayuchomu poryadku za dopomogoyu prostogo algoritmu centrovanogo obhodu dereva Predstavlyayetsya take derevo vuzlami nastupnogo viglyadu Node element key left right parent Dostup do dereva T zdijsnyuyetsya za dopomogoyu posilannya root Binarni dereva poshuku nabagato efektivnishi v operaciyah poshuku anizh linijni strukturi v yakih vitrati chasu na poshuk proporcijni O n de n rozmir masivu danih todi yak v povnomu binarnomu derevi cej chas proporcijnij v serednomu O log2n abo O h de h visota dereva hocha garantuvati sho h ne perevishuye log2n mozhna lishe dlya zbalansovanih derev yaki ye efektivnishimi v algoritmah poshuku anizh prosti binarni dereva poshuku dzherelo Operaciyi z dvijkovim derevom poshukuNajposhirenishoyu operaciyeyu yaka vikonuyetsya z binarnim derevom poshuku ye poshuk v nomu pevnogo klyucha Krim togo binarni dereva poshuku pidtrimuyut taki zapiti yak poshuk minimalnogo i maksimalnogo elementa a takozh poperednogo i nastupnogo Poshuk Dlya poshuku vuzla iz zadanim klyuchem v binarnomu derevi poshuku vikoristovuyetsya nastupna procedura Tree Search yaka otrimuye yak parametri pokazhchik na korin binarnogo dereva i klyuch k a povertaye pokazhchik na vuzol z cim klyuchem yaksho takij isnuye v inshomu vipadku povertayetsya znachennya NIL Tree Search x k 1 if h nil abo k key x 2 then return h 3 if k lt key x 4 then return Tree Search left x k 5 else return Tree Search right x k Procedura poshuku pochinayetsya z korenya dereva i prohodit vniz po derevu Dlya kozhnogo vuzla h na shlyahu vniz jogo klyuch key x porivnyuyetsya z peredanim yak parametr klyuchem k Yaksho klyuchi odnakovi poshuk zavershuyetsya Yaksho k menshe key h poshuk trivaye v livomu pidderevi h yaksho bilshe to poshuk perehodit v prave pidderevo Tu zh proceduru mozhna zapisati iterativno rozgortayuchi rekursiyu v cikl while Iterativna versiya proceduri Poshuk Iterative Tree Search x k 1 while x NIL i k key h 2 do if k key h 3 then h left x 4 else h right x 5 return x Poshuk minimalnogo maksimalnogo elementa Algoritm poshuku minimalnogo elementa Element z minimalnim znachennyam klyucha legko znajti sliduyuchi za vkazivnikami left vid korenevogo vuzla do tih pir poki ne zustrinetsya znachennya NIL Procedura TREE MINIMUM x povertaye pokazhchik na znajdenij element piddereva z korenem x TREE MINIMUM X 1 while left x NIL 2 do x left x 3 return x Algoritm poshuku maksimalnogo elementa simetrichnij TREE MAXIMUM X 1 while right x NIL 2 do x right x 3 return x Obidva algoritmi vimagayut chasu O h de h visota dereva Nastupnij i poperednij elementi Yaksho x pokazhchik na deyakij vuzol dereva to procedura TREE SUCCESSOR X povertaye pokazhchik na vuzol z nastupnim za x elementom abo nil yaksho zaznachenij element ostannij v derevi TREE SUCCESSOR X 1 if right x NIL 2 then return TREE MINIMUM right x 3 u p x 4 while y NIL ta x right y 5 do x u 6 u p y 7 return u Navedena procedura okremo rozglyadaye dva vipadki Yaksho prave pidderevo vershini ne puste to nastupnij za x element ye krajnim livim vuzlom u pravomu pidderevi yakij viyavlyayetsya proceduroyu TREE MlNlMUM right x Z inshogo boku yaksho prave pidderevo vuzla x puste ta u x isnuye nastupnij za nim element y to y ye najmenshim predkom x chij livij vuzol takozh ye predkom x Dlya togo shob znajti y mi prosto pidnimayemosya vgoru po derevu do tih pir poki ne zustrinemo vuzol yakij ye livim dochirnim vuzlom svogo batka Cya diya vikonuyetsya v ryadkah 3 7 algoritmu Chas roboti algoritmu TREE SUCCESSOR v derevi zavvishki h skladaye O h oskilki mi abo ruhayemosya po shlyahu vniz vid vihidnogo vuzla abo po shlyahu nagoru Procedura poshuku podalshogo vuzla v derevi TREE PREDECESSOR simetrichna proceduri TREE SUCCESSOR i takozh maye chas roboti O h Yaksho v derevi ye vuzli z odnakovimi klyuchami mi mozhemo prosto viznachiti nastupnij i poperednij vuzli yak ti sho povertayutsya procedurami TREE SUCCESSOR ta TREE PREDECESSOR vidpovidno Dodavannya elementa Dlya vstavki novogo znachennya v v binarne derevo poshuku T mi skoristayemosya proceduroyu TREE INSERT Procedura otrimuye yak parametr vuzol z u yakogo key z v left z NIL i right z NIL pislya chogo vona takim chinom zminyuye T i deyaki polya z sho z viyavlyayetsya vstavlenim v vidpovidnu poziciyu v derevi TREE INSERT T Z 1 u NIL 2 h root T 3 while x NIL 4 do u x 5 if key z lt key x 6 then x left x 7 else x right x 8 p z u 9 if u NIL 10 then root T z Derevo T puste 11 else if key z lt key y 12 then left y z 13 else right u z Vidalennya elementa Procedura vidalennya danogo vuzla z z binarnogo dereva poshuku otrimuye yak argument pokazhchik na z Procedura rozglyadaye tri mozhlivi situaciyi Yaksho u vuzla z nemaye dochirnih vuzliv to mi prosto zminyuyemo jogo batkivskij vuzol r z zaminyuyuchi v nomu pokazhchik na z znachennyam NIL Yaksho u vuzla z lishe odin dochirnij vuzol to mi vidalyayemo vuzol z stvoryuyuchi novij zv yazok mizh batkivskim i dochirnim vuzlom vuzla z Yaksho u vuzla z dva dochirnih vuzla to mi znahodimo nastupnij za nim vuzol u u yakogo nemaye livogo dochirnogo vuzla pribirayemo jogo z poziciyi de vin perebuvav ranishe shlyahom stvorennya novogo zv yazku mizh jogo batkom i nashadkom i zaminyuyemo nim vuzol Z DELETE T z 1 if left z NULL or right z NULL 2 then y z 3 else y SUCCESSOR z 4 if left y lt gt NULL 5 then x left y 6 else x right y 7 if x lt gt NULL 8 then p x p y 9 if p y NULL 10 then root T x 11 else if y left p y 12 then left p y x 13 else right p y x 14 if y lt gt z 15 then val z val y 16 kopiyuvannya dodatkovih danih z y 17 return y Chas na vikonannya ciyeyi proceduri ye takozh O h Div takozhU Vikidzherelah ye prikladi realizacij algoritmiv roboti z binarnimi derevami poshuku VikiPidruchnik VikiPidruchnik Mova programuvannya Lisp maye dani stosovno Dereva Zbalansovane derevo AVL derevo B derevo Chervono chorne derevo Spisok struktur danih Sortuvannya dvijkovim derevomPrimitkiTomas Kormen Charlz Lejzerson Ronald Rivest Kliford Stajn 2009 1990 Rozdil 12 Dvijkovi dereva poshuku Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4 DzherelaTomas Kormen Charlz Lejzerson Ronald Rivest Kliford Stajn 2009 1990 Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4 Donald Knut Sorting and Searching The Art of Computer Programming Massachusetts Addison Wesley 1998 T 3 780 s ISBN 0 201 89685 0 angl