Приложение на дървовидна структура от данни

1. Какво е дървовидна структура на данни и как е различна от другите DS.

Първият ми голям опит в кодирането започна в тренировъчен лагер. По време на подготвителните седмици преди старта на програмата и през първите няколко седмици на bootcamp масивите ни бяха представени като „основна структура от данни“.

През следващите няколко седмици научихме и за свързани списъци, опашки и стекове (по-специално за такова интересно нещо като Call Stack на JavaScript). Тези структури от данни се наричат ​​„линейни“ структури от данни, защото всички те имат логично начало и логичен край.

За разлика от масива и свързания списък, които са линейни структури от данни, дървото е йерархична (или нелинейна) структура от данни. Това означава, че не съхранява данни по линеен начин. Той организира данните йерархично.

Честно казано, организирането и кодирането на дървета изглежда МНОГО объркващо, когато започнете! Но докато продължавате да изучавате структурата на дървовидната структура на данни (PUN ALERT!), това не изглежда ТОЛКОВА страшно.

Какво си представяте, когато мислите за дърво? Вероятно корени, клони и листа? Да, така е! Дървовидната структура на данните в компютърните науки има корени, клони и листа, но е нарисувана с главата надолу (или като вечнозелено дърво, както споменаха в bootcamp).

Примери от реалния живот.

Но защо да използвате дърво за организиране на данни?

Едно от представянията на едно дърво е родословно дърво с връзки от всички поколения: баби и дядовци, родители, деца, братя и сестри и т.н. Ние обикновено организираме родословните дървета йерархично.

Структурата на организацията е друг пример за йерархия.

КРАТКО ТЕХНИЧЕСКО ОПИСАНИЕ НА ДЪРВЕТАТА

В компютърните науки Дървото е колекция от обекти, наречени Възли. Връзките, които свързват възлите, се наричат ​​Ръбове. Всеки възел съдържа някаква Стойност и също може да има или да няма Дъщерен възел.

Първият възел на дървото се нарича корен. Ако този Коренен възел е свързан с друг Възел, Коренът тогава е Родителски възел и свързаният Възел е Дете.

Както споменах преди, всички дървовидни възлиса свързани чрез връзки, наречени Ръбове. Това е важна част от Дървета, защото управлява връзката между Възли.

Листата са последните възли на дървото. Те са възли без деца. Подобно на истинските дървета, те имат Корен, Клонии накрая Листа.

Освен това има понятия като Височина и Дълбочинана дърво.

Височината на едно дърво е дължината на най-дългия път до листа.

Дълбочината на възел е дължината на пътя до неговия Корен.

Резюме на терминологията

• Корене най-горният възел на Дървото
• Edgeе връзката между два Nodes
• Детее възел, който има Родителски възел
• Родителе възел, който има Край към Дъщерен възел
• Листе възел, който няма дъщерен възел в дървото
• Височинатае дължината на най-дългия път до Lлист
• Дълбочинатае дължината на пътя до неговия Корен.

2. Възможни приложения на дървовидна структура на данни

Какво ще кажете за свързани с ИТ примери за дървовидна структура от данни?

Без да навлизаме много в подробности, има толкова много видове дървета, всяко от които служи за различни цели.

Някои от видовете дървета и техните приложения (някои нямат снимки, тъй като е твърде научнопокритие за толкова кратко време):

1. Например, файловата система на компютър е представена от двоично дърво:

2. Освен това в HTML Document Object Model (DOM) формира дървовидна структура.

3. B-Tree и B+Tree: Те се използват за прилагане на индексиране в бази данни.

4. Синтаксисно дърво: Използва се в компилатори на езици за програмиране.

5. Heap е дървовидна структура от данни, която се използва за прилагане на приоритетни опашки и ефективни методи за сортиране.

6. K-D дърво. Дърво за разделяне на пространството, използвано за организиране на точки в K-мерното пространство. Използва се в астрономическата наука от НАСА.

7. Trie: Използва се за прилагане на речници с търсене на префикс.

8. Дърво на суфиксите: За бързо търсене на шаблони във фиксиран текст.

9. Spanning Tree дървета се използват в комутатори в компютърни мрежи (Здравей Spanning Tree Protocol!)

11. Двоично дърво за търсене е дърво, което позволява бързо търсене, вмъкване, изтриване на сортирани данни и също така позволява намирането на най-близкия елемент.

3. Внедряване и използване на двоично дърво за търсене

По време на проучването си открих, че повечето от гореспоменатите дървовидни структури от данни всъщност са базирани на двоична дървовиднаструктура.

„В компютърните науки двоичното дърво е дървовидна структура от данни, в която всеки възел има най-много две деца, които се наричат ​​ляво дете и дясно дете.“ — Уикипедия

С други думи в двоичното дърво всеки възел може да има нула, един или два дъщерни възела.

Една от най-често срещаните и популярни реализации на двоично дърво е Двоично дърво за търсене.

„Дървото за двоично търсене понякога се нарича подредено или сортирано двоично дърво и то запазва своите стойности в сортиран ред, така че търсенето и другите операции да могат да използват принципа на двоично търсене“ — Wikipedia

Най-специфичната и важна характеристика на Двоично дърво за търсене (BST)е, че стойността на всеки възел Двоично дърво за търсенее по-голяма от стойността на всяко дете отляво дете, но по-малка от стойността на всяко дете на неговото дясно дете.

Пример:

Както можем да видим, всички леви деца на коренния възел имат по-малка стойност от собствената си стойност. Обратно, всички деца отдясно имат по-голяма стойност. Същото правило се прилага за всеки възел в дървото.

Внедряване на BST

Двоичното дърво за търсене има три основни операции/функции, които могат да се използват в него — създаване на възел, търсене на възел, премахване на възел (операция за изтриване). Нека само да разгледаме изпълнението на JavaScript за създаването на дървото и неговите възли.

Пример за клас BST възел:

Тук създаваме клас възел с три свойства: стойност, leftChild и rightChild. По подразбиране стойностите на дъщерните възли са празни (нулеви).Подаваме aстойносткогато създаваме нов обект на възел от този клас .

Сега нека видим пример за клас на двоично дърво за търсене и методи, които ни помагат да вмъкваме възли на правилното място в дърво.

Нека бързо да преминем през стъпките, които внедрихме по-горе:

1. Задаваме корена на всеки нов обект на null
2. В рамките на вмъкванепомощенметодние създаваме нов възел и го инициализираме с данни
3. Ако root е null, тогава възел ще бъде добавен към дървото и ще бъде превърнат в root.
4. Ако root вече съществува, извикваме метода insertNode, който намира правилната позиция в дървото и поставя възела там

insertNodeметодлогика:

1. Ако стойността е по-малка от стойността на възела, преминете към лявото дете на дървото
2. Ако leftChild е null, вмъкваме възел там
3. Ако leftChild не е null, ние използваме рекурсия, докато намерим null
4. Ако стойността е по-голяма от стойността на възела, преместваме надясно Child на дървото
5. Ако rightChild е null, вмъкваме възел там
6. Ако rightChild не е null, ние използваме рекурсия, докато намерим null

Използване

BST се използват широко в много области за множество различни нужди:

1. Да се ​​прилагат алгоритми за сортиране. Два основни фактора, които правят двоичното дърво за търсене оптимално решение за всякакви проблеми от реалния свят, са скоростта и точността.
2. BST се използват за индексиране и многостепенно индексиране.
3. Могат да се използват като приоритетни опашки.
4. Използва се в много приложения за търсене, където данни непрекъснато влизат и излизат като стабилна игрова логика, дейности за автоматично завършване и графики.

Благодаря ви за вниманието и се надявам тази статия да ви е помогнала да разберете поне малко по-добре дървовидната структура на данните!

РЕФЕРЕНЦИИ