Читамо линеарне структуре података као што су низ, повезана листа, стек и ред у коме су сви елементи распоређени на секвенцијални начин. Различите структуре података се користе за различите врсте података.

Неки фактори се узимају у обзир за одабир структуре података:

Коју врсту података треба чувати?: Можда постоји могућност да одређена структура података најбоље одговара за неку врсту података.Трошкови операција:Ако желимо да минимизирамо трошкове за операције за најчешће извођене операције. На пример, имамо једноставну листу на којој морамо да извршимо операцију претраживања; затим, можемо креирати низ у којем се елементи чувају у сортираном редоследу да би се извршила бинарно претраживање . Бинарна претрага ради веома брзо за једноставну листу јер дели простор за претрагу на пола.Употреба меморије:Понекад желимо структуру података која користи мање меморије.

Дрво је такође једна од структура података које представљају хијерархијске податке. Претпоставимо да желимо да прикажемо запослене и њихове позиције у хијерархијском облику, онда се то може представити на следећи начин:

Горње дрво показује хијерархија организације неке компаније. У горњој структури, јохн је Директор компаније, а Џон има два директна извештаја названа као Стеве и Рохан . Стив има три имена директног извештаја Ли, Боб, Ела где Стеве је менаџер. Боб има два директна извештаја Хоће и Емма . Емма има два директна извештаја именована Том и Рај . Том има један директни извештај по имену Билл . Ова посебна логичка структура је позната као а Дрво . Његова структура је слична правом стаблу, па је названа а Дрво . У овој структури, корен је на врху, а његове гране се крећу у правцу надоле. Стога можемо рећи да је структура података Трее ефикасан начин складиштења података на хијерархијски начин.

Хајде да разумемо неке кључне тачке структуре података Трее.

• Структура података стабла је дефинисана као колекција објеката или ентитета познатих као чворови који су повезани заједно да представљају или симулирају хијерархију.
• Структура података у стаблу је нелинеарна структура података јер се не складишти на секвенцијални начин. То је хијерархијска структура јер су елементи у стаблу распоређени у више нивоа.
• У структури података Трее, највиши чвор је познат као коренски чвор. Сваки чвор садржи неке податке, а подаци могу бити било ког типа. У горњој структури стабла, чвор садржи име запосленог, тако да би тип података био стринг.
• Сваки чвор садржи неке податке и везу или референцу других чворова који се могу назвати децом.

Неки основни термини који се користе у структури података Трее.

Хајде да размотримо структуру дрвета, која је приказана у наставку:

У горњој структури, сваки чвор је означен неким бројем. Свака стрелица приказана на горњој слици позната је као а линк између два чвора.

Корен:Коријенски чвор је највиши чвор у хијерархији стабла. Другим речима, основни чвор је онај који нема родитеља. У горњој структури, чвор под бројем 1 је коријенски чвор дрвета. Ако је чвор директно повезан са неким другим чвором, то би се назвало односом родитељ-дете.Подређени чвор:Ако је чвор потомак било ког чвора, онда је чвор познат као подређени чвор.Родитељ:Ако чвор садржи било који подчвор, онда се за тај чвор каже да је родитељ тог подчвора.брат и сестра:Чворови који имају истог родитеља познати су као браћа и сестре.Листни чвор: -Чвор дрвета, који нема ниједан подређени чвор, назива се листни чвор. Листни чвор је најдоњи чвор дрвета. У општем стаблу може бити неограничен број чворова листа. Листни чворови се такође могу назвати спољним чворовима.Унутрашњи чворови:Чвор има најмање један подређени чвор познат као ан унутрашњег Чвор предака: -Предак чвора је било који чвор претходник на путу од корена до тог чвора. Коријенски чвор нема претке. У стаблу приказаном на горњој слици, чворови 1, 2 и 5 су преци чвора 10.Потомак:Непосредни наследник датог чвора је познат као потомак чвора. На горњој слици, 10 је потомак чвора 5.

Својства структуре података дрвета

Рекурзивна структура података:Дрво је познато и као а рекурзивна структура података . Стабло се може дефинисати као рекурзивно јер је истакнути чвор у структури података дрвета познат као а коренски чвор . Коренски чвор стабла садржи везу са свим коренима његовог подстабла. Лево подстабло је приказано жутом бојом на доњој слици, а десно подстабло је приказано црвеном бојом. Лево подстабло се може даље поделити на подстабло приказано у три различите боје. Рекурзија значи смањење нечега на себи сличан начин. Дакле, ово рекурзивно својство структуре података стабла имплементирано је у различитим апликацијама.
Број ивица:Ако има н чворова, онда би било н-1 ивица. Свака стрелица у структури представља везу или путању. Сваки чвор, осим основног чвора, имаће најмање једну долазну везу познату као ивица. Постојала би једна веза за однос родитељ-дете.Дубина чвора к:Дубина чвора к може се дефинисати као дужина пута од корена до чвора к. Једна ивица доприноси дужини једне јединице на путањи. Дакле, дубина чвора к се такође може дефинисати као број ивица између коренског чвора и чвора к. Коренски чвор има дубину 0.Висина чвора к:Висина чвора к може се дефинисати као најдужа путања од чвора к до лисног чвора.

На основу својстава структуре података Трее, стабла се класификују у различите категорије.

Имплементација Трее

Структура података стабла се може креирати динамичким креирањем чворова уз помоћ показивача. Дрво у меморији се може представити на следећи начин:

Горња слика приказује приказ структуре података стабла у меморији. У горњој структури, чвор садржи три поља. Друго поље чува податке; прво поље чува адресу левог детета, а треће поље чува адресу десног детета.

минимакс алгоритам

У програмирању, структура чвора се може дефинисати као:

 struct node { int data; struct node *left; struct node *right; } 

Горња структура се може дефинисати само за бинарна стабла јер бинарно стабло може имати највише два детета, а генеричка стабла могу имати више од два детета. Структура чвора за генеричко стабло би била другачија у поређењу са бинарним стаблом.

Примене дрвећа

Следеће су примене дрвећа:

Чување природно хијерархијских података:Стабла се користе за складиштење података у хијерархијској структури. На пример, систем датотека. Датотечни систем који се чува на диск јединици, датотека и фасцикла су у облику природно хијерархијских података и ускладиштени су у облику стабала.Организујте податке:Користи се за организовање података за ефикасно уметање, брисање и претрагу. На пример, бинарно стабло има логН време за претрагу елемента.пробај:То је посебна врста дрвета које се користи за чување речника. То је брз и ефикасан начин за динамичку проверу правописа.Гомила:То је такође структура података дрвета имплементирана помоћу низова. Користи се за имплементацију приоритетних редова.Б-дрво и Б+дрво:Б-Трее и Б+Трее су структуре података стабла које се користе за имплементацију индексирања у базама података.Табела рутирања:Структура података стабла се такође користи за складиштење података у табелама рутирања у рутерима.

Типови структуре података дрвета

Следе типови структуре података стабла:

Опште дрво:Опште дрво је један од типова структуре података стабла. У општем стаблу, чвор може имати или 0 или максимално н број чворова. Нема ограничења на степен чвора (број чворова које чвор може да садржи). Највиши чвор у општем стаблу познат је као коренски чвор. Деца родитељског чвора су позната као подстабла .

Може да буде н број подстабала у општем стаблу. У општем стаблу, подстабла су неуређена јер се чворови у подстаблу не могу поредати.
Свако непразно дрво има ивицу надоле, а ове ивице су повезане са чворовима познатим као дечји чворови . Основни чвор је означен нивоом 0. Чворови који имају исти родитељ су познати као браћа и сестре . Бинарно дрво :Овде, само бинарно име сугерише два броја, тј. 0 и 1. У бинарном стаблу, сваки чвор у стаблу може имати највише два подређена чвора. Овде крајње значи да ли чвор има 0 чворова, 1 чвор или 2 чвора.

Да бисте сазнали више о бинарном стаблу, кликните на везу дату у наставку:
хттпс://ввв.јаватпоинт.цом/бинари-трее Стабло бинарног претраживања :Бинарно стабло претраге је нелинеарна структура података у којој је један чвор повезан н број чворова. То је структура података заснована на чворовима. Чвор може бити представљен у бинарном стаблу претраге са три поља, тј., део података, лево дете и десно дете. Чвор се може повезати са највише два подређена чвора у бинарном стаблу претраге, тако да чвор садржи два показивача (лево дете и десно дете).
Сваки чвор у левом подстаблу мора да садржи вредност мању од вредности коренског чвора, а вредност сваког чвора у десном подстаблу мора бити већа од вредности коренског чвора.

Чвор се може креирати уз помоћ кориснички дефинисаног типа података познатог као структура, како је приказано испод:

 struct node { int data; struct node *left; struct node *right; } 

Горе је структура чвора са три поља: поље података, друго поље је леви показивач типа чвора, а треће поље је десни показивач типа чвора.

Да бисте сазнали више о стаблу бинарне претраге, кликните на везу дату у наставку:

хттпс://ввв.јаватпоинт.цом/бинари-сеарцх-трее

АВЛ дрво

То је један од типова бинарног стабла, или можемо рећи да је варијанта бинарног стабла претраге. АВЛ стабло задовољава својство бинарно дрво као и на бинарно стабло претраге . То је самобалансирајуће стабло бинарног претраживања које је измислио Аделсон Велски Линдас . Овде самобалансирање значи балансирање висина левог подстабла и десног подстабла. Ово балансирање се мери у смислу фактор равнотеже .

Можемо сматрати стабло АВЛ стаблом ако се дрво повинује бинарном стаблу претраге као и фактор равнотеже. Балансни фактор се може дефинисати као разлика између висине левог подстабла и висине десног подстабла . Вредност фактора равнотеже мора бити или 0, -1 или 1; стога, сваки чвор у АВЛ стаблу треба да има вредност фактора балансирања или као 0, -1 или 1.

Да бисте сазнали више о АВЛ стаблу, кликните на везу дату у наставку:

хттпс://ввв.јаватпоинт.цом/авл-трее

Црвено-црно дрво

Црвено-црно дрво је бинарно стабло претраге. Предуслов црвено-црног стабла је да знамо за бинарно стабло претраге. У бинарном стаблу претраге, вредност левог подстабла треба да буде мања од вредности тог чвора, а вредност десног подстабла треба да буде већа од вредности тог чвора. Као што знамо да је временска сложеност бинарне претраге у просечном случају лог₂н, најбољи случај је О(1), а најгори случај О(н).

Када се било која операција изврши на стаблу, желимо да наше дрво буде избалансирано тако да све операције као што су претраживање, уметање, брисање итд., трају мање времена, а све ове операције ће имати временску сложеност Пријава₂н.

Црвено-црно дрво је самобалансирајуће стабло бинарног претраживања. АВЛ стабло је такође бинарно стабло претраге за балансирање висине зашто нам је потребно црвено-црно дрво . У АВЛ стаблу, не знамо колико би ротација било потребно да би се стабло балансирало, али у црвено-црном стаблу су потребне највише 2 ротације да би се уравнотежило дрво. Садржи један додатни бит који представља или црвену или црну боју чвора како би се осигурало балансирање стабла.

Сплаи трее

Структура података стабла с приказом је такође бинарно стабло претраге у коме се недавно приступљеном елементу поставља на основну позицију стабла извођењем неких операција ротације. овде, прскање означава чвор којем се недавно приступило. То је самобалансирање бинарно стабло претраге које нема експлицитни услов равнотеже као АВЛ дрво.

Можда постоји могућност да висина стабла приказа није избалансирана, тј. висина левог и десног подстабла може да се разликује, али операције у стаблу приказа имају редослед мирно време где н је број чворова.

Сплаи стабло је уравнотежено стабло али се не може сматрати стаблом избалансираног по висини јер се након сваке операције врши ротација што доводи до уравнотеженог стабла.

Треап

Структура података Треап долази из структуре података Трее и Хеап. Дакле, садржи својства и структуре података у облику дрвета и хрпе. У бинарном стаблу претраге, сваки чвор на левом подстаблу мора бити једнак или мањи од вредности коренског чвора и сваки чвор на десном подстаблу мора бити једнак или већи од вредности коренског чвора. У структури података гомиле, и десно и лево подстабло садрже веће кључеве од корена; стога можемо рећи да коренски чвор садржи најнижу вредност.

У структури података треап-а, сваки чвор има обоје кључ и приоритет где је кључ изведен из стабла бинарног претраживања, а приоритет је изведен из структуре података гомиле.

Тхе Треап структура података прати два својства која су дата у наставку:

• Десно дете чвора>=тренутни чвор и лево дете чвора<=current node (binary tree)< li>
• Деца било ког подстабла морају бити већа од чвора (гомиле)

Б-стабло

Б-стабло је уравнотежено м-пут дрво где м дефинише редослед стабла. До сада смо читали да чвор садржи само један кључ, али б-стабло може имати више од једног кључа и више од 2 детета. Увек одржава сортиране податке. У бинарном стаблу, могуће је да лисни чворови могу бити на различитим нивоима, али у б-стаблу сви чворови листа морају бити на истом нивоу.

Ако је ред м онда чвор има следећа својства:

• Сваки чвор у б-стаблу може имати максимум м деца
• За минималну децу, листни чвор има 0 деце, коренски чвор има најмање 2 деце, а унутрашњи чвор има минимални плафон од м/2 деце. На пример, вредност м је 5 што значи да чвор може имати 5 деце, а унутрашњи чворови могу да садрже највише 3 деце.
• Сваки чвор има максимум (м-1) кључева.

Основни чвор мора да садржи најмање 1 кључ, а сви остали чворови морају да садрже најмање плафон од м/2 минус 1 кључеви.