www.wikidata.uk-ua.nina.az

Двійкове дерево пошуку Двійкове або Бінарне дéрево пóшуку 1 англ binary search tree BST в інформатиці двійкове дерево в

Двійкове дерево пошуку

Двійкове (або Бінарне) дéрево пóшуку (англ. 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. Процедура розглядає три можливі ситуації:

  1. Якщо у вузла z немає дочірніх вузлів, то ми просто змінюємо його батьківський вузол р[z], замінюючи в ньому покажчик на z значенням NIL.
  2. Якщо у вузла z лише один дочірній вузол, то ми видаляємо вузол z, створюючи новий зв'язок між батьківським і дочірнім вузлом вузла z.
  3. Якщо у вузла 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)

Див. також Редагувати

У Вікіджерелах є
приклади реалізацій алгоритмів роботи з бінарними деревами пошуку
ВікіПідручник
ВікіПідручник Мова програмування Лісп має дані стосовно:
Дерева

Примітки Редагувати

  1. ↑ Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Розділ 12: Двійкові дерева пошуку. Вступ до алгоритмів (вид. 3). К.І.С. с. 301–322. ISBN 978-617-684-239-2. 

Джерела Редагувати

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Dvijkove abo Binarne derevo poshuku 1 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 1 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 poshukuTip DerevoVinajdeno 1960Obchislyuvalna skladnistu zapisi velikogo OSerednya NajgirshaProstir 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 1 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 Zmist 1 Operaciyi z dvijkovim derevom poshuku 1 1 Poshuk 1 2 Iterativna versiya proceduri Poshuk 1 3 Poshuk minimalnogo maksimalnogo elementa 1 4 Nastupnij i poperednij elementi 1 5 Dodavannya elementa 1 6 Vidalennya elementa 2 Div takozh 3 Primitki 4 DzherelaOperaciyi z dvijkovim derevom poshuku RedaguvatiNajposhirenishoyu 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 Redaguvati 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 Redaguvati 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 xPoshuk minimalnogo maksimalnogo elementa Redaguvati 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 xAlgoritm poshuku maksimalnogo elementa simetrichnij TREE MAXIMUM X 1 while right x NIL 2 do x right x 3 return xObidva algoritmi vimagayut chasu O h de h visota dereva Nastupnij i poperednij elementi Redaguvati 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 uNavedena 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 Redaguvati 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 zVidalennya elementa Redaguvati 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 takozh RedaguvatiU Vikidzherelah ye prikladi realizacij algoritmiv roboti z binarnimi derevami poshuku nbsp VikiPidruchnik VikiPidruchnik Mova programuvannya Lisp maye dani stosovno Dereva Zbalansovane derevo AVL derevo B derevo Chervono chorne derevo Spisok struktur danih Sortuvannya dvijkovim derevomPrimitki Redaguvati a b v Kormen Tomas Lejzerson Charlz Rivest Ronald Stajn Kliford 2019 Rozdil 12 Dvijkovi dereva poshuku Vstup do algoritmiv vid 3 K I S s 301 322 ISBN 978 617 684 239 2 Dzherela RedaguvatiTomas Kormen Charlz Lejzerson Ronald Rivest Vstup do algoritmiv MIT Press i McGraw Hill Iskusstvo programmirovanie Sortirovka i poisk Donald Knut ros Otrimano z https uk wikipedia org w index php title Dvijkove derevo poshuku amp oldid 32402904