Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

У програмуванні двійкове дерево структура даних у вигляді дерева в якому кожна вершина має не більше двох дітей Зазвичай

Двійкове дерево

У програмуванні двійкове дерево — структура даних у вигляді дерева, в якому кожна вершина має не більше двох дітей. Зазвичай такі діти називаються правим та лівим. На базі двійкових дерев будуються такі структури, як двійкові дерева пошуку та двійкові купи.

image
Двійкове дерево

Різновиди двійкових дерев

  • Двійкове дерево — таке кореневе дерево, в якому кожна вершина має не більше двох дітей.
  • Повне (закінчене) двійкове дерево — таке двійкове дерево, в якому кожна вершина має нуль або двох дітей.
  • Ідеальне двійкове дерево — це таке повне двійкове дерево, в якому листя (вершини без дітей) лежать на однаковій глибині (відстані від кореня).

Двійкове дерево на кожному n-му рівні має від 1 до 2n вершин.

Обхід двійкового дерева

Докладніше: (Обхід дерева)

Часто виникає необхідність обійти усі вершини дерева для аналізу інформації, що в них знаходиться. Існують декілька порядків такого обходу, кожний з яких має певні властивості, важливі в тих чи інших алгоритмах: прямий (preorder), центрований (inorder) та зворотний (postorder).

Втілення двійкових дерев

image
Реалізація двійкового дерева. Кожна вершина містить вказівники на праву та ліву дитину (left та right)

Залежно від задач, які вирішуються цими структурами та можливостей тої чи іншої мови програмування, існує декілька варіантів конструювання двійкових дерев.

Реалізація з використанням вказівників передбачає зберігання в кожній вершині дерева x, разом із даними власне цієї вершини, також двох полів — правого та лівого (right[x] та left[x]), які містять вказівники на відповідних дітей цієї вершини.

image
Змінена реалізація двійкового дерева. Кожна вершина містить також вказівник на батьківську вершину

Також іноді додається вказівник p[x] на батьківську вершину. Це спрощує деякі алгоритми та виявляється корисним, коли необхідно забезпечити швидкий доступ до батьківської вершини. Іноді достатньо тільки вказівника на батьківську вершину. Взагалі будь-яке орієнтоване дерево можна описати, знаючи тільки зв'язки від дітей до батьківської вершини.

Деякі різновиди двійкових дерев (наприклад, червоно-чорні дерева або (AVL-дерева)), вимагають збереження в вершинах і деякої додаткової інформації. Якщо у вершини відсутня одна чи обидві дитини, відповідні вказівники ініціалізуються спеціальними «пустими» значеннями.

image
Двійкове дерево на базі масиву

Двійкові дерева також можуть бути побудовані на базі масивів. Такий метод набагато ефективніший щодо економії пам'яті. В такому представленні, якщо вершина має порядковий номер i, то її діти знаходяться за індексами 2i+1 та 2i+2, а батьківська вершина за індексом ((i-1)/2) (за умов, що коренева вершина має індекс 0).

Інший варіант зберігання дерева в масиві — зберігати індекси дітей.

Представлення n-арних дерев як двійкових

Існує єдине та взаємооднозначне відображення довільного впорядкованого дерева в двійкове.

image

Для цього слід послідовно зв'язати усіх дітей кожної сім'ї з першою дитиною та видалити усі вертикальні з'єднання за виключенням з'єднання батька з першою дитиною в сім'ї. Тобто кожна вершина N впорядкованого n-арного дерева відповідає вершині M деякого двійкового дерева. Ліва дитина вершини M відповідає першій дитині вершини N, а права дитина M відповідає першому з наступних братів N (тобто першому з наступних дітей батька вершини N).

Така відповідність має назву природної відповідності між n-арним та двійковим деревом.

Література

  • Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (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.

Посилання


image Це незавершена стаття про структури даних.
Ви можете проєкту, виправивши або дописавши її.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, 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 derevoRiznovidi dvijkovih derevDvijkove 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 derevaDokladnishe 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 derevRealizaciya 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 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 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 dvijkovihIsnuye yedine ta vzayemoodnoznachne vidobrazhennya dovilnogo vporyadkovanogo dereva v dvijkove 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 LiteraturaTomas Kormen Charlz Lejzerson Ronald Rivest Kliford 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 PosilannyaDung 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 Ce nezavershena stattya pro strukturi danih Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi
Топ