Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
У програмуванні двійкове дерево — структура даних у вигляді дерева, в якому кожна вершина має не більше двох дітей. Зазвичай такі діти називаються правим та лівим. На базі двійкових дерев будуються такі структури, як двійкові дерева пошуку та двійкові купи.
Різновиди двійкових дерев
- Двійкове дерево — таке кореневе дерево, в якому кожна вершина має не більше двох дітей.
- Повне (закінчене) двійкове дерево — таке двійкове дерево, в якому кожна вершина має нуль або двох дітей.
- Ідеальне двійкове дерево — це таке повне двійкове дерево, в якому листя (вершини без дітей) лежать на однаковій глибині (відстані від кореня).
Двійкове дерево на кожному n-му рівні має від 1 до 2n вершин.
Обхід двійкового дерева
Часто виникає необхідність обійти усі вершини дерева для аналізу інформації, що в них знаходиться. Існують декілька порядків такого обходу, кожний з яких має певні властивості, важливі в тих чи інших алгоритмах: прямий (preorder), центрований (inorder) та зворотний (postorder).
Втілення двійкових дерев
Залежно від задач, які вирішуються цими структурами та можливостей тої чи іншої мови програмування, існує декілька варіантів конструювання двійкових дерев.
Реалізація з використанням вказівників передбачає зберігання в кожній вершині дерева x, разом із даними власне цієї вершини, також двох полів — правого та лівого (right[x] та left[x]), які містять вказівники на відповідних дітей цієї вершини.
Також іноді додається вказівник p[x] на батьківську вершину. Це спрощує деякі алгоритми та виявляється корисним, коли необхідно забезпечити швидкий доступ до батьківської вершини. Іноді достатньо тільки вказівника на батьківську вершину. Взагалі будь-яке орієнтоване дерево можна описати, знаючи тільки зв'язки від дітей до батьківської вершини.
Деякі різновиди двійкових дерев (наприклад, червоно-чорні дерева або AVL-дерева), вимагають збереження в вершинах і деякої додаткової інформації. Якщо у вершини відсутня одна чи обидві дитини, відповідні вказівники ініціалізуються спеціальними «пустими» значеннями.
Двійкові дерева також можуть бути побудовані на базі масивів. Такий метод набагато ефективніший щодо економії пам'яті. В такому представленні, якщо вершина має порядковий номер i, то її діти знаходяться за індексами 2i+1 та 2i+2, а батьківська вершина за індексом ((i-1)/2) (за умов, що коренева вершина має індекс 0).
Інший варіант зберігання дерева в масиві — зберігати індекси дітей.
Представлення n-арних дерев як двійкових
Існує єдине та взаємооднозначне відображення довільного впорядкованого дерева в двійкове.
Для цього слід послідовно зв'язати усіх дітей кожної сім'ї з першою дитиною та видалити усі вертикальні з'єднання за виключенням з'єднання батька з першою дитиною в сім'ї. Тобто кожна вершина N впорядкованого n-арного дерева відповідає вершині M деякого двійкового дерева. Ліва дитина вершини M відповідає першій дитині вершини N, а права дитина M відповідає першому з наступних братів N (тобто першому з наступних дітей батька вершини N).
Така відповідність має назву природної відповідності між n-арним та двійковим деревом.
Література
- Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — .(англ.)
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 12. Двійкові дерева пошуку. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
- Parmar, Anand K. (22 січня 2020). Different Types of Binary Tree with colourful illustrations. Medium (англ.). Процитовано 24 січня 2020.
Посилання
- Dung X. Nguyen (2003). Binary Tree Structure. rice.edu. Процитовано 28 грудня 2010.
- Binary trees entry in the FindStat database
- Binary Tree Proof by Induction
- Balanced binary search tree on array How to create bottom-up an Ahnentafel list, or a balanced binary search tree on array
- Binary trees and Implementation of the same with working code examples
- Binary Tree JavaScript Implementation with source code
 | Це незавершена стаття про структури даних. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U programuvanni dvijkove derevo struktura danih u viglyadi dereva v yakomu kozhna vershina maye ne bilshe dvoh ditej Zazvichaj taki diti nazivayutsya pravim ta livim Na bazi dvijkovih derev buduyutsya taki strukturi yak dvijkovi dereva poshuku ta dvijkovi kupi Dvijkove derevo Zmist 1 Riznovidi dvijkovih derev 2 Obhid dvijkovogo dereva 3 Vtilennya dvijkovih derev 4 Predstavlennya n arnih derev yak dvijkovih 5 Literatura 6 PosilannyaRiznovidi dvijkovih derevred Dvijkove derevo take koreneve derevo v yakomu kozhna vershina maye ne bilshe dvoh ditej Povne zakinchene dvijkove derevo take dvijkove derevo v yakomu kozhna vershina maye nul abo dvoh ditej Idealne dvijkove derevo ce take povne dvijkove derevo v yakomu listya vershini bez ditej lezhat na odnakovij glibini vidstani vid korenya Dvijkove derevo na kozhnomu n mu rivni maye vid 1 do 2n vershin Obhid dvijkovogo derevared Dokladnishe Obhid dereva Chasto vinikaye neobhidnist obijti usi vershini dereva dlya analizu informaciyi sho v nih znahoditsya Isnuyut dekilka poryadkiv takogo obhodu kozhnij z yakih maye pevni vlastivosti vazhlivi v tih chi inshih algoritmah pryamij preorder centrovanij inorder ta zvorotnij postorder Vtilennya dvijkovih derevred nbsp Realizaciya dvijkovogo dereva Kozhna vershina mistit vkazivniki na pravu ta livu ditinu left ta right Zalezhno vid zadach yaki virishuyutsya cimi strukturami ta mozhlivostej toyi chi inshoyi movi programuvannya isnuye dekilka variantiv konstruyuvannya dvijkovih derev Realizaciya z vikoristannyam vkazivnikiv peredbachaye zberigannya v kozhnij vershini dereva x razom iz danimi vlasne ciyeyi vershini takozh dvoh poliv pravogo ta livogo right x ta left x yaki mistyat vkazivniki na vidpovidnih ditej ciyeyi vershini nbsp Zminena realizaciya dvijkovogo dereva Kozhna vershina mistit takozh vkazivnik na batkivsku vershinu Takozh inodi dodayetsya vkazivnik p x na batkivsku vershinu Ce sproshuye deyaki algoritmi ta viyavlyayetsya korisnim koli neobhidno zabezpechiti shvidkij dostup do batkivskoyi vershini Inodi dostatno tilki vkazivnika na batkivsku vershinu Vzagali bud yake oriyentovane derevo mozhna opisati znayuchi tilki zv yazki vid ditej do batkivskoyi vershini Deyaki riznovidi dvijkovih derev napriklad chervono chorni dereva abo AVL dereva vimagayut zberezhennya v vershinah i deyakoyi dodatkovoyi informaciyi Yaksho u vershini vidsutnya odna chi obidvi ditini vidpovidni vkazivniki inicializuyutsya specialnimi pustimi znachennyami nbsp Dvijkove derevo na bazi masivu Dvijkovi dereva takozh mozhut buti pobudovani na bazi masiviv Takij metod nabagato efektivnishij shodo ekonomiyi pam yati V takomu predstavlenni yaksho vershina maye poryadkovij nomer i to yiyi diti znahodyatsya za indeksami 2i 1 ta 2i 2 a batkivska vershina za indeksom i 1 2 za umov sho koreneva vershina maye indeks 0 Inshij variant zberigannya dereva v masivi zberigati indeksi ditej Predstavlennya n arnih derev yak dvijkovihred Isnuye yedine ta vzayemoodnoznachne vidobrazhennya dovilnogo vporyadkovanogo dereva v dvijkove nbsp Dlya cogo slid poslidovno zv yazati usih ditej kozhnoyi sim yi z pershoyu ditinoyu ta vidaliti usi vertikalni z yednannya za viklyuchennyam z yednannya batka z pershoyu ditinoyu v sim yi Tobto kozhna vershina N vporyadkovanogo n arnogo dereva vidpovidaye vershini M deyakogo dvijkovogo dereva Liva ditina vershini M vidpovidaye pershij ditini vershini N a prava ditina M vidpovidaye pershomu z nastupnih brativ N tobto pershomu z nastupnih ditej batka vershini N Taka vidpovidnist maye nazvu prirodnoyi vidpovidnosti mizh n arnim ta dvijkovim derevom Literaturared Donald Knut Fundamental Algorithms The Art of Computer Programming 3rd Massachusetts Addison Wesley 1997 T 1 650 s ISBN 0 201 89683 4 angl T Kormen Ch Lejzerson R Rivest K Stajn 2009 1990 12 Dvijkovi dereva poshuku Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4 Parmar Anand K 22 sichnya 2020 Different Types of Binary Tree with colourful illustrations Medium angl Procitovano 24 sichnya 2020 Posilannyared Dung X Nguyen 2003 Binary Tree Structure rice edu Procitovano 28 grudnya 2010 Binary trees entry in the FindStat database Binary Tree Proof by Induction Balanced binary search tree on array How to create bottom up an Ahnentafel list or a balanced binary search tree on array Binary trees and Implementation of the same with working code examples Binary Tree JavaScript Implementation with source code nbsp Ce nezavershena stattya pro strukturi danih Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org w index php title Dvijkove derevo amp oldid 42914820