Back

ⓘ Радикс стабло




Радикс стабло
                                     

ⓘ Радикс стабло

У рачунарству, радикс стабло је просторно оријентисана структура података у којој се сваки чвор са само једним дететом спојио са својим дететом. Резултат је да сваки унутрашњи чвор има најмање двоје деце. За разлику од редовних префиксних стабала, ивице могу бити означене са секвенцама елемената, као и појединачним елементима. То их чини много ефикаснијим за мале скупове и за групе ниски које имају дуже префиксе.

Као оптимизација, ознаке ивица могу бити смештене у сталној величиниза прве и последње елементе.

Имајте на уму да, иако су примери у овом чланку показују ниске као секвенце карактера, тип ниски у низу елемената може бити произвољно изабран на пример, као бит или бајт репрезентације ниски када се користи кодирање са карактером од више битова или Уникод.

                                     

1. Употреба

Као што је поменуто, радикс стабла су корисна за изградњу асоцијативних низова са кључевима који се могу изразити као ниске. Налазе посебну примену у области ИП рутирања, где је могућност да садрже велике опсеге вредности, са пар изузетака, посебно погодна у хијерархијској организацији ИП адреса. Они се такође користе за инвертовано обележавање текстуалних докумената у преузимању информација.

                                     

2. Операције

Радикс стабла подржавају уметање, брисање и претраживање операције. Убацивање додаје нову ниску у стабло док у исто време покушава да смањи количину података који су додавани. Брисање уклања ниску од стабла. Претраживање операције укључује тачно проналажење, наћи претходника, наћи наследника, и пронаћи све ниске са префиксом. Све ове операције су Оk где је k максимална дужина свих ниски у сету. Овај списак не може бити коначан.

                                     

2.1. Операције Проналажење

Операција проналажења утврђује да ли ниска постоји у стаблу. Већина операција мења овај приступ на неки начин да би се решили своје специфичне задатке. На пример, чвор где ниска престаје може бити од значаја. Ова операција је слична префикс стаблу осим што неке ивице конзумирају више елемената.

Следећи псеудо код претпоставља да ове класе постоје.

Ивица

  • Чвор targetNode
  • ниска label

Чвор

  • функција isLeaf
  • Низ ивица edges
function lookupstring x { // Почети у корену без пронађених елемената Node traverseNode:= root ; int elementsFound:= 0; // Пролазити док се не нађе лист или није могуће наставити while traverseNode!= null &&!traverseNode.isLeaf && elementsFound < x.length { // Узети следећу ивицу за истраживање на основу елемената који још нису пронађени у Х Edge nextEdge:= select edge from traverseNode.edges where edge.label is a prefix of x.suffixelementsFound // x.suffixelementsFound враћа задњи x.length - elementsFound елемент од x // Да ли је пронађена ивица? if nextEdge!= null { // Ставити следећи чвор да се истражује traverseNode:= nextEdge.targetNode; // Повећавати пронађене елементе на основу ознака постављених код ивица elementsFound += nextEdge.label.length; } else { // Прекинути петљу traverseNode:= null ; } } // Подударност је пронађена ако стигнемо до чвора листа и искоришћено је тачно x.length елемената return traverseNode!= null && traverseNode.isLeaf && elementsFound == x.length; }


                                     

2.2. Операције Уношење

Да бисте унели ниску, тражимо дрво док се не може направити никакав даљи напредак. У овом тренутку можемо или додати нову одлазећу ивицу означену са свим преосталим елементима у улазну ниску, или ако већ постоји одлазећи ивица која дели префикс са преосталим улазним стрингом, можемо их поделити на две ивице први означен са заједничким префиксом и наставити. Ово раздвајање осигурава да ниједан чвор нема више деце него што има могућих елемената стринга.

Неколико случајева убацивања су приказани испод, мада још постоји. Имајте на уму да r једноставно представља корен. Претпоставља се да ивице могу бити означене са празним нискама да прекину ниске где је то потребно и да корен нема долазну ивицу.

                                     

2.3. Операције Брисање

Да бисте избрисали х стринг са стабла, прво пронађите лист који представља х. Затим, под претпоставком да постоји х, уклонимо одговарајући чвор листа. Ако родитељ нашег чвора листа има само једно друго дете, онда та долазна ознака детета се додаје родитељској надолазећој ознаци и дете се уклони.

                                     

2.4. Операције Додатне операције

  • Пронаћи претходника: лоцира највећу ниску мању од задатог низа, по лексикографском поретку.
  • Пронаћи све низове са заједничким префиксом: Враћа низ ниски који почињу истим префиксом.
  • Пронаћи наследника: Проналази најмању ниску већу од задатог низа, по лексикографском поретку.
                                     

3. Историја

Доналд Р. МорисонDonald R. Morrison први је описао оно што је он назвао "Патрициа дрвеће" 1968-е, назив потиче од акронима Патрициа, што је скраћеница за Практични алгоритам претраживања информација кодирана алфанумерички ". Гернот ГвехенбергерGernot Gwehenberger самостално је изумео и описао структуру података у отприлике исто време.

                                     

4. Поређење са другим структурама података

У следећим поређењима, претпоставља се да су кључеви дужине k и структура података садржи n чланова.

За разлику од само-балансирајућих стабала, радикс стабла дозвољавају проналажење, уметање, брисање и у времену Оk, а не Оlog n. Ово не изгледа као предност, јер нормално k ≥ log n, али у балансираном стаблу свако поређење је поређење ниски које захтева Оk у најгорем случају, од којих су многи у пракси спори због дугих заједничких префикса у случају где поређење почне на почетку ниске. У префикс стаблу, ова поређења захтевају константно време, али је потребно m поређења да се пронађе низ дужине m. Радикс стабла може да обавља ове операције са мање поређења, и захтева много мање чворова.

Радикс стабла такође деле мане префикс стабала, ипак: као што се они могу применити само на низове елемената или елементе са ефикасним повратним мапирањем низова, немају потпуну општост избалансираних претраживања дрвећа, који се односе на било који тип података са укупно наручивања. Обртно мапирање за ниске може да се користи за производњу потребне тоталне наруџбине за балансирану претрагу дрвећа, али не и обрнуто. Ово такође може бити проблематично уколико тип података само пружа поређење операције, али не десеријализацију операција.

Код хеш табела се обично каже да је очекивано О1 пута убацивања и брисања, али то важи само када је у питању обрачунавање хеш кључева да буде константа временска операција. Када се хешинг кључа узима у обзир, за хеш табеле се очекује Оk пута убацивања и брисања, али може да траје дуже у најгорем случају у зависности од тога како се рукује са сударима. Радикс стабла имају најгори случај Оk убацивања и брисања. Наследник/претходник операције радикс стабала се такође не спроводе преко хеш табеле.



                                     

5. Варијанте

Заједнички продужетак радикс стабала користи две боје чворова, "црне" и "беле". Да бисте проверили да ли дата ниска се чува у дрвету, претраживање почиње од врха и прати ивице улазне ниске док се напредак не може више остварити. Ако се тражена ниска конзумира и коначни чвор је црни чвор, претраживање није успело, а ако је беле боје, претрага је успела. То нам омогућава да додамо велики асортиман ниски са заједничким префиксом у стабло, користећи беле чворове, а затим уклонити мали скуп "изузетака" просторски ефикасним начином убацивања помоћу црних чворова.

                                     

6. Спољашње везе

  • Patricia Tree, NIST Dictionary of Algorithms and Data Structures
  • Kart key alteration radix tree, by Paul Jarc
  • Algorithms and Data Structures Research & Reference Material: PATRICIA, by Lloyd Allison, Monash University
  • Radix Tree API in the Linux Kernel, by Jonathan Corbet
  • Crit-bit trees, by Daniel J. Bernstein
                                     
  • специјализованим за посебне врсте кључева као што су радикс стабла Џуди низови или фон Емде Боа стабла али су те имплементације мање ефикасне од хеш табела
  • polinomijalnoj veličini BDD Model checking Radiks stablo Binary key metod indetifikacije vrsta u biologiji pomoću binarnih stabla Barrington s teorema Graph - Based
  • подручја и слично, све док не буду испоручена. Овај метод је повезан и са радикс сортирањем, описаним за сортирање бушених картица још 1929. године. Стратегија
  • могуће је и сортирање алгоритмима који не користе поређење елемената, попут радикс сортирања и сортирања пребројавањем. Бољи начин од сортирања целог низа

Users also searched:

...