Трие
From Wikipedia, the free encyclopedia
У рачунарству, трие, или често називано дигитално стабло и понекад радикс стабло или префиксно стабло (пошто се може претраживати по префиксу), је структура података у облику уређеног стабла које се користи за чување елемената динамичког скупа или асоцијативног низа где су кључеви обично ниске карактера. За разлику од бинарног стабла претраге, ниједан чвор у стаблу не чува кључ који одговара том чвору. Уместо тога, сама његова позиција у стаблу одређује кључ који му одговара. Сви наследници неког чвора имају заједнички префикс ниске карактера која одговара том чвору, а корену одговара празна ниска. Уобичајено је да се вредности не додељују сваком чвору већ само листовима и неким унутрашњим чворовима који одговарају траженим кључевима.
Термин трие потиче од енглеске речи retrieval. Овај термин је први пут употребио Едвард Фредкин, који га је изговарао као /ˈtriː/ енгл. као у речи retrieval.[1][2] Међутим, други аутори име ове структуре изговарају као /ˈtraɪ/ енгл. , како би правили разлику од енгл. .[1][2][3]
У приказаном примеру, кључеви су део самих чворова а њихове одговарајуће вредности испод њих. Свака целовита реч има додељену произвољну целобројну вредност. Трие се може посматрати као детерминистички коначни аутомат без петљи. Сваки коначни језик се може генерисати трие аутоматом, и сваки трие се може сабити у Детерминистички ациклични коначни аутомат.
Није неопходно да кључеви буду експлицитно чувани у чворовима. (На слици, речи су приказане само како би се илустровао рад трие структуре).
Иако су код ове структуре, кључеви обично ниске карактер, не морају бити. Исти алгоритам се лако може адаптирати да обавља исте функције са уређеним листама било које конструкције, нпр. пермутације листе цифара или облика. Конкретно, битовски трие ради са кључевима у виду индивидуалних битова.