Въведение в дърветата в структурата на данните
Преди да разберем типовете дървета в структурата на данните, първо, ще проучим дърветата в структурата на данните. Дървото в компютърното поле също се нарича дърво в реалния свят, но разликата между реалния свят и дървото на изчислителните полета е, че се визуализира като обърната надолу и корен отгоре и се разклонява от корена към листата на дървото. Сред различни приложения в реалния свят се използва структурата на данните на дървото, тъй като може да демонстрира връзки между различни възли с йерархията родител-дете. Поради това се нарича йерархична структура на данни. Той е най-популярен за опростяване и ускоряване на търсенето и сортирането. Той се счита за една от най-силните и най-модерни структури от данни. Дърво е представяне на нелинейната структура на данните. Дърво може да бъде показано с помощта на различни дефинирани от потребителя или примитивни типове данни. Можем да използваме масиви, списъци, свързани със класове, или други видове структури от данни, за да реализираме дървото. Това е група възли, които са взаимосвързани. Възлите са прикрепени към краищата, за да демонстрират връзката.
Връзки в едно дърво: В дадената по-горе диаграма P е коренът на дървото, също P е родител на Q, R и S. Q е дете на P. Следователно Q, R и S са братя и сестри. Като има предвид, че P е прародител на A, B, C, D и E.
Какво са дърветата?
Дърво е структура на йерархични данни, която естествено съхранява информацията по йерархичен начин. Структурата на данните на Дървото е една от най-ефективните и зрели. Представени са възлите, свързани с краищата.
Свойства на дървото: Всяко дърво има специфичен корен възел. Всеки възел на дърво може да бъде пресечен от корен възел. Нарича се корен, тъй като дървото е било единственият корен. Всяко дете има само един родител, но родителят може да има много деца.
Видове дървета в структурата на данните
По-долу са видовете дървета в структурата на данните:
1. Общо дърво
Ако върху йерархията на дървото не се поставя ограничение, едно дърво се нарича общо дърво. Всеки възел може да има безкраен брой деца в General Tree. Дървото е супер набор от всички други дървета.
2. Двоично дърво
Двоичното дърво е видът дърво, в който могат да се намерят най-много две деца за всеки родител. Децата са известни като лявото дете и дясното дете. Това е по-популярно от повечето други дървета. Когато някои ограничения и характеристики се прилагат в двоично дърво, се използват и редица други като AVL дърво, BST (Binary Search Tree), RBT tree и др. Когато продължим напред, ще обясним подробно всички тези стилове.
3. Двоично дърво за търсене
Двоично дърво за търсене (BST) е двоично разширение на дърво с няколко незадължителни ограничения. Стойността на лявото дете на даден възел трябва да бъде по-малка или равна на родителската стойност, а дясната стойност на детето винаги трябва да бъде по-голяма или равна на стойността на родителя. Това свойство на Binary Search Tree го прави идеален за операции за търсене, тъй като можем точно да определим на всеки възел дали стойността е в лявото или дясното дърво. Ето защо дървото за търсене е кръстено.
4. AVL дърво
AVL дърво е самобалансиране на двоично дърво за търсене. От името на изобретателите Аделсън-Велши и Ландис е дадено името AVL. Това беше първото дърво, което балансира динамично. Балансиращ фактор се разпределя за всеки възел в AVL дървото въз основа на това дали дървото е балансирано или не. Височината на децата възли е най-много 1. AVL лоза. В AVL дървото правилният коефициент на баланс е 1, 0 и -1. Ако дървото има нов възел, то ще се завърти, за да се гарантира, че дървото е балансирано. След това ще се завърти. Честите операции като преглед, вмъкване и премахване отнемат O (log n) време в AVL дървото. Прилага се най-вече при работа с операции Lookups.
5. Червено-черно дърво
Друг вид дърво за автоматично балансиране е червено-черно. Името червено-черно е дадено, защото червено-черното дърво има или червено, или черно, боядисано на всеки възел според свойствата на червено-черното дърво. Поддържа баланса на гората. Въпреки че това дърво не е напълно балансирано дърво, операцията за търсене отнема само O (log n) време. Когато новите възли са добавени в Червено-Черно дърво, тогава възлите ще бъдат завъртени отново, за да се поддържат свойствата на Червено-Черно дърво.
6. N-ary Tree
Максималният брой деца в този тип дърво, които могат да имат възел, е N. Бинарното дърво е двугодишно дърво, като най-много 2 деца във всеки бинарен възел. Пълно N-ary дърво е дърво, където децата на възел или са 0 или N.
Предимства на Дървото
Сега ще разберем предимствата на дървото:
- Дървото се отразява в структурните връзки на данните.
- Дървото се използва за йерархия.
- Той предлага ефективна процедура за търсене и вмъкване.
- Дърветата са гъвкави. Това позволява да се преместят подредовете с минимални усилия.
Заключение - Видове дървета в структурата на данните
Така че тук в тази статия видяхме какво е дървесна структура, какви са различните видове дървета в структурата на данните и нейните ползи. Надявам се да имате представа за някои от обикновените дървета в структурата на данните.
Препоръчителни статии
Това е ръководство за Видовете дървета в структурата на данните. Тук обсъждаме какво е дървета, 6 вида дървета в структурата на данните, с предимства. Можете също да прегледате и другите ни свързани статии, за да научите повече -
- AWS тръбопровод за данни
- Складиране на данни на Oracle
- Многоизмерна база данни
- Структура на данните Въпроси за интервю на Java
