Кіріспе

Деректер құрылымы

Компьютерлік ғылымда радикс ағашы (радикс триі немесе ықшам префикс ағашы немесе сығылған три) – кеңістікті оңтайландырылған три (префикс ағашы) бейнелейтін деректер құрылымы. Онда жалғыз баласы бар әрбір түйін ата-анасымен біріктіріледі. Нәтижесінде, әрбір ішкі түйіннің балаларының саны радикс ағашының радиксі r-ден аспайды, мұнда r = 2x, x ≥ 1 бүтін саны үшін. Қарапайым ағаштардан айырмашылығы, қабырғалар элементтер тізбегімен де, жеке элементтермен де белгіленуі мүмкін. Бұл радикс ағаштарын кішкентай жиынтықтар үшін (әсіресе, тізбектер ұзын болса) және ұзын префикстерді бөлісетін тізбектер жиынтығы үшін тиімді етеді. Қарапайым ағаштарда (төлігі кілттер бастапқысынан теңсіздікке дейін салыстырылатын болса), радикс ағаштарында әрбір түйіндегі кілт биттердің бөлігімен бөліктеп салыстырылады, ал әлгі түйіндегі биттер саны радикс триінің радиксі r-ге тең. r = 2 болғанда, радикс триі екілік болады (яғни, сол түйіннің кілтінің 1 биттік бөлігі салыстырылады), бұл тридің тереңдігін арттыру есебінен сиректікті азайтады, яғни кілттегі айырмашылығы жоқ биттік тізбектерге дейін. r ≥ 4 және 2-нің дәрежесі болғанда, радикс триі r-арлық три болады, бұл потенциалды сиректік есебінен радикс триінің тереңдігін азайтады. Оптимизация ретінде, қабырға белгілерін (бірінші және соңғы элементтер үшін) тізбекке екі сілтеме арқылы тұрақты көлемде сақтауға болады. Бұл мақалада мысалдар әріптер тізбегі ретінде көрсетілгенімен, тізбек элементтерінің түрін кез келгендей таңдауға болады; мысалы, көп байттық әріптік кодтауларды немесе Юникодты қолданғанда тізбек бейнелеуінің биті немесе байты ретінде.

Қолданбалар

Радикс ағаштары кілттерді жолдар түрінде көрсетуге болатын ассоциативтік массивлерді құруға пайдалы. Олар ерекше пайдалылығын IP маршрутизациясында табады, онда бірнеше ерекшеліктері бар үлкен мәндер диапазондарын қамту мүмкіндігі IP-адрестердің иерархиялық құрылымына өте ыңғайлы. Сонымен қатар, олар ақпаратты іздеуде мәтіндік құжаттардың инверттік индекстері үшін қолданылады.

Операциялар

Радикс ағаштары енгізу, өшіру және іздеу операцияларын қолдайды. Енгізу – сақталған деректер көлемін азайтуға тырыса отырып, триеға жаңа жолды қосу. Өшіру – триеден жолды алып тастау. Іздеу операцияларына (бірақ олармен шектелмейді) нақты іздеу, алдыңғы шаманы табу, келесі шаманы табу және белгілі бір префиксі бар барлық жолдарды табу кіреді. Бұл операциялардың барлығы O(k) күрделігіне ие, мұндағы k – жиынтықтағы барлық жолдардың ең үлкен ұзындығы, ал ұзындық радикс триесінің радиксіне тең биттер санымен өлшенеді.

Кірірілу

Жіпті енгізу үшін ағашты одан әрі іздеу мүмкін болмайынша іздейміз. Осы кезде, кіріс жолдың қалған элементтерімен белгіленген жаңа шығу жиегін қосамыз немесе, егер кіріс жолдың қалған бөлігімен префиксі ортақ болатын шығу жиегі болса, оны екі жиекке бөлеміз (біріншісі ортақ префикспен белгіленген) және одан әрі іздейміз. Бұл бөлу қадамы кез келген түйінде мүмкін тізбек элементтерінен артық балалар болмауын қамтамасыз етеді. Төменде бірнеше енгізу мысалы көрсетілген, бірақ одан да көп болуы мүмкін. Есте сақтаңыз, r жай ғана түбірді көрсетеді. Қажет болған жағдайда, тізбекті аяқтау үшін жиектерді бос тізбектермен белгілеуге болады және түбірдің кіретін жиегі жоқ деп есептеледі. (Жоғарыда сипатталған іздеу алгоритмі бос тізбек жиектерін пайдаланғанда жұмыс істемейді.)

Жою

Ағаштан x жолын өшіру үшін, бірінші кезекте x-ті көрсететін жапырақты анықтаймыз. Егер x болса, тиісті жапырақ түйінін жоямыз. Егер жапырақ түйінінің ата-анасында тек бір ғана басқа баласы болса, онда сол баланың кіріс белгісі ата-анасының кіріс белгісіне қосылады және бала жойылады.

Қосымша операциялар

Бірдей префиксі бар тізбелерді табу: Бірдей префикстен басталатын тізбелер массивін қайтарады. Алдыңғы тізбені табу: Лексикографиялық тәртіп бойынша берілген тізбектен кіші ең үлкен тізбені анықтайды. Келесі тізбені табу: Лексикографиялық тәртіп бойынша берілген тізбектен үлкен ең кіші тізбені анықтайды.

Тарих

Мәліметтер құрылымын 1968 жылы Дональд Р. Моррисон ойлап тапты, онымен ең көп байланысты және Гернот Гвеенбергер де қатысты. Дональд Кнут, "Компьютерлік бағдарламалау өнері" кітабының III томының 498-500 беттерінде оларды "Патриция ағаштары" деп атайды, бұл Моррисонның мақаласының тақырыбындағы аббревиатурадан туындаған: "ПАТРИЦИЯ – әріптік-сандық кодталған ақпаратты іздеудің практикалық алгоритмі". Бүгінде Патриция ағаштары радиксі 2-ге тең радикстік ағаштар ретінде қарастырылады, яғни кілттің әрбір биті жеке салыстырылады және әрбір түйін екі тармақты (сол және оң) бөлімге бөлінеді.

Басқа дерек құрылымдарымен салыстыру

(Келесі салыстыруларда кілттердің ұзындығы k және деректер құрылымында n мүше бар деп есептеледі.) Теңгерімделген ағаштардан айырмашылығы, радикс ағаштары іздеу, енгізу және жою операцияларын O(log n) емес, O(k) уақытында орындайды. Бұл артықшылық сияқты көрінбейді, өйткені көбінесе k ≥ log n, бірақ теңгерімді ағашта әрбір салыстыру O(k) ең нашар жағдай уақытын қажет ететін жол (string) салыстыру болып табылады, және ұзақ ортақ префикстердің болуына байланысты олардың көпшілігі іс жүзінде баяу болады (егер салыстырулар жолдың басынан басталатын болса). Триде барлық салыстырулар тұрақты уақытты қажет етеді, бірақ ұзындығы m болатын жолды іздеу үшін m салыстыру қажет. Радикс ағаштары осы операцияларды аз салыстырулармен орындай алады және оларға көптеген түйіндер қажет емес. Дегенмен, радикс ағаштары трилердің кемшіліктерін де бөліседі: оларды тек элементтердің жолдарына немесе жолдарға тиімді түрлендірілетін элементтерге ғана қолдануға болады, сондықтан теңгерімді іздеу ағаштарының толық мүмкіндігінен айырылады, олар толық реттелген кез келген дерек типіне қолданылады. Теңгерімді іздеу ағаштары үшін қажетті толық реттілікке жолдарға кері түрлендіруді қолдануға болады, бірақ керісінше емес. Бұл мәселелі болуы мүмкін, егер дерек типі тек салыстыру операциясын ғана ұсынса, бірақ (серияландыру/десериализация) операциясын ұсынбаса. Хеш-кестелерге қатысты, олардың күтілетін енгізу және жою уақыты O(1) деп жиі айтылады, бірақ бұл кілттің хешін есептеу операциясы тұрақты уақытты қажет етеді деп есептелген кезде ғана дұрыс. Кілттің хештелуі ескерілгенде, хеш-кестелердің күтілетін енгізу және жою уақыты O(k) құрайды, бірақ қақтығыстарды қалай басқаруға байланысты ең нашар жағдайда одан да көп уақыт қажет болуы мүмкін. Радикс ағаштарында енгізу және жою операцияларының ең нашар жағдай уақыты O(k) құрайды. Сондай-ақ, радикс ағаштарының ізбасар/алдын ала операциялары хеш-кестелерде іске асырылмайды.

Нұсқалар

Радикс ағаштарының кең таралған кеңейтімі түйіндердің екі түсін, "қара" және "ақ" түстерін пайдаланады. Берілген жол ағашта сақталған-жоқпын тексеру үшін іздеу жоғарыдан басталады және кіріс жолының жиектерімен жүреді, одан әрі ілгерілеу мүмкін болмайынша. Егер іздеу жолы толып, соңғы түйін қара түйін болса, іздеу сәтсіз аяқталады; егер ол ақ болса, іздеу сәтті аяқталады. Бұл бізге ағашқа ортақ алдыңғы қосымшасы бар көптеген жолдарды ақ түйіндерді пайдалану арқылы қосуға және содан кейін оларды қара түйіндерді пайдалану арқылы кеңістікті тиімді түрде "ерекшеліктердің" кішкентай жиынтығын жоюға мүмкіндік береді. HAT trie – радикс ағаштарына негізделген, кэшті ескеретін деректер құрылымы, ол тиімді жолдарды сақтау және алу, сондай-ақ реттелген итерацияларды ұсынады. Уақыт және кеңістік тұрғысынан өнімділік кэшті ескеретін хэш-кестемен салыстыруға болады. PATRICIA trie – radix 2 (бинарлық) trie-нің ерекше түрі, онда түйіндер әрбір кілттің әрбір битін нақты сақтаудың орнына, екі кіші ағашты ажырататын бірінші биттің орнын ғана сақтайды. Итерация кезінде алгоритм іздеу кілтінің индекстелген битін тексереді және тиісті жағдайда сол немесе оң кіші ағашты таңдайды. PATRICIA trie-нің ерекше ерекшеліктері – trie сақталған әрбір бірегей кілт үшін тек бір түйіннің енгізілуін қажет етеді, бұл PATRICIA-ны стандартты бинарлық trie-ден әлдеқайда ықшам етеді. Сонымен қатар, нақты кілттер енді нақты сақталмайтындықтан, сәйкестікті растау үшін индекстелген жазбада толық кілтті салыстыру қажет. Осы тұрғыдан PATRICIA хэш-кесте арқылы индекстеуге ұқсас. Бір ғана баласы бар ата-аналарды рұқсат етпеу шарттарын жеңілдету, ата-ана деректер жиынтығында жарамды кілтті білдіретін жағдайларда, бұл кең таралған тәжірибе. Бұл радикс ағашының түрі тек екі баласы бар ішкі түйіндерге рұқсат беруге қарағанда кеңістікті тиімділігін арттырады.