У овом упутству ћете научити о структури података стабла. Такође ћете научити о различитим врстама дрвећа и терминологијама које се користе у дрвету.
Стабло је нелинеарна хијерархијска структура података која се састоји од чворова повезаних ивицама.
Дрво
Зашто структура података о дрвету?
Остале структуре података као што су низови, повезана листа, стог и ред су линеарне структуре података које секвенцијално чувају податке. Да би се извршила било која операција у линеарној структури података, временска сложеност се повећава са повећањем величине података. Али, то није прихватљиво у данашњем рачунарском свету.
Различите структуре података стабла омогућавају бржи и лакши приступ подацима јер је то нелинеарна структура података.
Терминологије дрвећа
Чвор
Чвор је ентитет који садржи кључ или вредност и показује на своје подређене чворове.
Последњи чворови сваке путање називају се чворови листова или спољни чворови који не садрже везу / показивач на подређене чворове.
Чвор који има најмање подређени чвор назива се интерним чвором .
Ивица
То је веза између било која два чвора.
Чворови и ивице дрвета
Корен
То је највиши чвор дрвета.
Висина чвора
Висина чвора је број ивица од чвора до најдубљег листа (тј. Најдужа путања од чвора до чвора листа).
Дубина чвора
Дубина чвора је број ивица од корена до чвора.
Висина дрвета
Висина дрвета је висина кореновог чвора или дубина најдубљег чвора.
Висина и дубина сваког чвора у дрвету
Степен чвора
Степен чвора је укупан број грана тог чвора.
Шума
Збирка раздвојених стабала назива се шума.
Стварање шуме од дрвета
Можете створити шуму сечењем корена дрвета.
Врсте дрвета
- Бинарно дрво
- Бинарно стабло претраживања
- АВЛ Трее
- Б-дрво
Прелазак дрвета
Да бисте извршили било коју операцију на дрвету, морате доћи до одређеног чвора. Алгоритам преласка стабла помаже у посети потребном чвору на дрвету.
Да бисте сазнали више, посетите обилазак дрвета.
Трее Апплицатионс
- Бинарна стабла за претрагу (БСТ) користе се за брзу проверу да ли је елемент присутан у скупу или не.
- Хрпа је врста дрвета које се користи за сортирање гомиле.
- Измењена верзија стабла под називом Триес користи се у модерним рутерима за чување информација о рутирању.
- Најпопуларније базе података користе Б-дрвеће и Т-дрвеће, које су варијанте структуре стабла које смо горе научили за чување њихових података
- Преводитељи користе стабло синтаксе да потврде синтаксу сваког програма који напишете.
