Komprimeret præfikstræ

basistræ
Type	træ
Opfindelsens år	1968
Forfatter	Donald R. Morrison
Kompleksitet i O-symboler
I værste fald Søg Indsæt Fjernelse
Mediefiler på Wikimedia Commons

Et  grundtræ ( radix tree , også kompakt præfikstræ , hovedtræ, residualtræ [1] ) er en datastruktur, der er en hukommelsesoptimeret implementering af et præfikstræ. I basistræet flettes den node , der er det eneste underordnede af noden , med noden .

Tidskompleksiteten af ​​operationerne med at søge, tilføje og fjerne et element fra basistræet estimeres som , hvor  er længden af ​​det element, der behandles. Køretiden afhænger ikke af antallet af elementer i træet.

I modsætning til konventionelle præfikstræer kan en basistræknude mærkes med enten et enkelt element (tegn, bit osv.) eller en sekvens af elementer. Dette gør basistræet mere effektivt for små sæt strenge (især hvis strengene i sig selv er lange nok), og også for sæt, der har et lille antal lange præfikser.

Ansøgning

• Basistræet bruges især til parsing af naturlige sprog [2] .
• Basistræet er en af ​​Linux-kernens datastrukturer [3] .

Noter

1. ↑ Radix Tree-struktur til datakomprimering https://habrahabr.ru/post/141145/ Arkiveret 20. december 2016 på Wayback Machine
2. ↑ Pymorphy 2 https://m.habrahabr.ru/post/176575/ Arkiveret 19. juni 2017 på Wayback Machine
3. ↑ Robert Love. Linux-kerneudvikling. tredje udgave. 2010 https://docs.google.com/file/d/0B1iyZaHiAMfFZE9aXzNBOXR0OGM/edit?pli=1 Arkiveret 15. december 2015 på Wayback Machine

Links

• Algoritmer og datastrukturer Forskning og referencemateriale: PATRICIA , af Lloyd Allison, Monash University
• Patricia Tree , NIST Dictionary of Algoritms and Data Structures
• Crit-bit trees , af Daniel J. Bernstein
• Radix Tree API i Linux-kernen , af Jonathan Corbet
• Kart (key alteration radix tree) , af Paul Jarc