www.wikidata.uk-ua.nina.az

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

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

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

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

Різновиди двійкових дерев Редагувати

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

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

Обхід двійкового дерева Редагувати

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

Втілення двійкових дерев Редагувати

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

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

Реалізація з використанням вказівників передбачає зберігання в кожній вершині дерева 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-арним та двійковим деревом.

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

Література Редагувати

Посилання Редагувати

Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки.
Матеріал без джерел може бути піддано сумніву та вилучено. (червень 2023)
Це незавершена стаття про структури даних.
Ви можете допомогти проєкту, виправивши або дописавши її.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
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 Div takozh 6 Literatura 7 PosilannyaRiznovidi dvijkovih derev RedaguvatiDvijkove 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 dereva RedaguvatiDokladnishe Obhid derevaChasto 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 derev Redaguvati 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 vershinuTakozh 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 masivuDvijkovi 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 dvijkovih RedaguvatiIsnuye 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 Div takozh RedaguvatiDvijkove derevo poshuku Zbalansovane derevo AVL derevo B derevo Chervono chorne derevo Prefiksne derevo Spisok struktur danihLiteratura RedaguvatiParmar Anand K 22 sichnya 2020 Different Types of Binary Tree with colourful illustrations Medium angl Procitovano 24 sichnya 2020 Introduction to algorithms Cormen Thomas H Cormen Thomas H vid 2nd Cambridge Mass MIT Press 2001 s 128 ISBN 0 262 03293 7 OCLC 46792720 Posilannya RedaguvatiDung 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 codeCya 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 cherven 2023 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 39836557