Увод у дрвеће у структури података
Пре него што схватимо врсте стабала у структури података, прво ћемо проучити стабла у структури података. Дрво у рачунарском пољу такође се назива и стабло из стварног света, али разлика између стварног света и стабла рачунарског поља је у томе што је оно визуелно приказано наопако и корен на врху и грана се од корена до лишћа дрвећа. Између различитих апликација у стварном свету користи се структура података стабла јер може показати односе између различитих чворова са хијерархијом родитељ-дете. Због тога се назива и хијерархијска структура података. Најпопуларнији је за поједностављивање и убрзавање претраживања и сортирања. Сматра се једном од најјачих и најнапреднијих структура података. Дрво је приказ нелинеарне структуре података. Дрво се може приказати користећи различите кориснички дефинисане или примитивне типове података. За имплементацију стабла можемо користити низове, листе повезане са класама или друге врсте података. То је група чворова који су међусобно повезани. Чворови су причвршћени на ивице како би се демонстрирала веза.
Односи на дрвету: У горе датом дијаграму, П је корен дрвета, а П је родитељ К, Р и С. К је дете П. Дакле, К, Р и С су браћа и сестре. Док је П главни родитељ А, Б, Ц, Д и Е.
Шта су дрвећа?
Дрво је хијерархијска структура података која природно похрањује информације на хијерархијски начин. Структура података о Дрвету једна је од најефикаснијих и најзрелијих. Приказани су чворови повезани преко ивица.
Својства дрвета: Свако дрво има специфичан коријенски чвор. Сваки чвор стабла може се укрстити коријенским чвором. Зове се корен, јер је дрво било једини корен. Свако дете има само једног родитеља, али родитељ може имати много деце.
Врсте стабала у структури података
Испод су врсте стабала у структури података:
1. Генерал Трее
Ако се на хијерархији стабла не ограничава, стабло се назива опћим дрветом. Сваки чвор може имати бесконачан број деце у Генерал Трее-у. Дрво је супер скуп свих осталих стабала.
2. Бинарно дрво
Бинарно дрво је врста дрвета у којем се може наћи највише двоје деце за сваког родитеља. Деца су позната као лево дете и десно дете. Ово је популарније од већине других стабала. Када се одређена ограничења и карактеристике примене у бинарном стаблу, користи се и низ других, као што су АВЛ стабло, БСТ (дрво бинарног претраживања), стабло РБТ итд. Када кренемо напријед, детаљно ћемо објаснити све ове стилове.
3. Бинарно стабло претраге
Бинарно стабло претраживања (БСТ) је бинарно проширење стабла са неколико опционих ограничења. Вредност левог детета у чвору треба да буде мања или једнака родитељској вредности, а вредност десног детета увек треба да буде већа или једнака вредности родитеља. Ово својство Бинарног стабла претраживања чини га идеалним за операције претраживања, јер на сваком чвору можемо тачно одредити да ли је вредност у левом или десном под-стаблу. Због тога је и именовано стабло претраживања.
4. АВЛ Дрво
АВЛ стабло је само-уравнотежујуће бинарно стабло претраживања. У име проналазача Аделсон-Велсхи и Ландис дат је назив АВЛ. Ово је било прво дрво које се динамички уравнотежило. Фактор уравнотежења додјељује се за сваки чвор у АВЛ стаблу, на основу тога је ли дрво уравнотежено или не. Висина клинаца је највише 1. АВЛ винова лоза. У АВЛ стаблу тачан фактор равнотеже је 1, 0 и -1. Ако дрво има нови чвор, оно ће се ротирати како би се осигурало да је дрво уравнотежено. Затим ће се ротирати. Уобичајене операције као што су преглед, уметање и уклањање одузимају О (лог н) време у АВЛ стаблу. Најчешће се примењује када радите са операцијама Лоокупс.
5. Црвено-црно дрво
Друга врста дрвета са аутоматским балансирањем је црвено-црна. Име црвено-црно је дано јер је стабло црвено-црно обојено на сваком чвору црвено или црно у складу са својствима црвено-црног стабла. Одржава равнотежу шуме. Иако ово дрво није у потпуности уравнотежено стабло, операција претраге траје само О (лог н) време. Када се додају нови чворови у Црвено-црно дрво, тада ће се чворови поново ротирати ради одржавања својстава Црвено-Црног стабла.
6. Н-ари Дрво
Максимални број деце у овој врсти стабла који може имати чвор је Н. Бинарно дрво је двогодишње дрво, као и највише 2 деце у сваком бинарном чвору дрвета. Комплетно Н-ари стабло је дрво на коме су деца чвора или 0 или Н.
Предности Дрвета
Сада ћемо разумети Предности Дрвета:
- Дрво се одражава на структурне везе података.
- Дрво се користи за хијерархију.
- Нуди ефикасан поступак претраживања и уметања.
- Дрвеће је флексибилно. То омогућава измештање субтреес уз минималан напор.
Закључак - Врсте стабала у структури података
Дакле, овде у овом чланку видели смо шта је структура дрвећа, које су различите врсте дрвећа у структури података и његове предности. Надам се да сте добили представу о неким уобичајеним дрвећем у структури података.
Препоручени чланци
Ово је водич за Врсте стабала у структури података. Овде смо разговарали о томе шта је дрвеће, 6 врста дрвећа у структури података, са предностима. Можете и да прођете кроз остале сродне чланке да бисте сазнали више -
- АВС Дата Пипелине
- Орацле складиштење података
- Вишедимензионална база података
- Структура података Јава Интервју питања