Стабло (структура података)
Појам „стабло“ се у програмирању користи да означи структуру података која има „разгранату“ структуру, по узору на појам стабла у теорији графова.
Стабло је граф који има за 1 мањи број грана од чворова.
Стабло се често користи као главни облик неког спремишта података, због лаког писања одговарајућег кода кроз коришћење рекурзије, брзог уписивања података и брзог приступа траженим подацима. Најчешће коришћено стабло је стабло у којем сваки чвор мора имати тачно двије гране, тј. бинарно стабло.
Терминологија[уреди | уреди извор]
У терминологији стабла као структуре података, користе се слични појмови као код обичног стабла. Тако, чвор који не садржи грану ниједног другог чвора а који посредно или непосредно садржи све друге чворове назива се „коријен“. Чворови који не садрже ниједну грану, тј. налазе се на „врху“ стабла, називају се „листовима“
Такође, постоји терминологија „родитељ-дијете“, у којој се чвор А који садржи чвор Б назива родитељем чвора Б, док се чвор Б назива дјететом чвора А.
Конструкција[уреди | уреди извор]
Стабло се у програмирању остварује коришћењем показивача да би се усмјерило ка одговарајућим гранама. Наиме, сваки чвор се конструише тако да посједује могућност чувања једне или више адреса других чворова, што омогућава „прелажење“ из једног чвора у други, тј. кретање по стаблу.
Будући да стабло може имати неограничен број чворова (условно говорећи, због ограничене количине меморије на рачунарским уређајима), итеративно рјешење конструкције и коришћења стабла најчешће није добро нити лако рјешење. Умјесто тога, пишу се функције које се рекурзивно позивају док једна од инстанци функције не прими тражени чвор као аргумент. Тада се изврши жељена радња (враћање резултата или стварање новог чвора) и рекурзивни ланац се одмотава и завршава. Слабост рекурзивног рјешења лежи у ситуацијама када је стабло велико, те долази до пренатрпавања функцијског стека процеса што може довести до успорености или наглог прекидања цијелог програма.
Док се бинарно стабло у програмирању остварује релативно једноставно, коришћењем тачно два показивача, неограничен број грана по чвору се имплементира на нешто сложенији начин. Потребно је у сваком чвору чувати неку структуру података која подржава неограничен број показивача, што се најчешће чини користећи листе или обичне низове који се проширују по потреби.
Употреба[уреди | уреди извор]
Бинарно стабло се најчешће користи за смјештај података који морају бити у уређеном распореду, тј. сортирани, како би им се могло брзо приступати методом бинарне претраге. Међутим, за смјештај било каквих података чији чворови могу имати више од једног дјетета потребно је вишеструко стабло. На примјер, језик XML по самој својој дефиницији захтијева дрволику структуру података са неограниченим бројем грана по једном чвору. Такође, датотечни систем као дрволика структура захтијева неограничен број грана по једном директоријуму. У појединим имплентацијама видео игара, лавиринти се такође имплементирају као вишеструка стабла, при чему је свако поље у лавиринту представљено једним чвором у стаблу, а поља на која се може прећи из датог поља су представљена као гране одговарајућег чвора. Обично рјешавање проблема излаза из лавиринта се, међутим, најчешће остварује употребом реда.
Види још[уреди | уреди извор]
Спољашње везе[уреди | уреди извор]
- Опис појма у рјечнику алгоритама и структура података (језик: енглески)
