Komprimovaný strom předpon

základní strom

Typ

dřevo

Rok vynálezu

1968

Autor

Donald R. Morrison

	Při nejhorším
Vyhledávání	$OK)$
Vložit	$OK)$
Odstranění	$OK)$

Mediální soubory na Wikimedia Commons

Základní strom ( radix tree , také kompaktní prefixový strom , hlavní strom, zbytkový strom [1] ) je datová struktura, která je paměťově optimalizovanou implementací prefixového stromu. V základním stromu je uzel , který je jediným potomkem uzlu, sloučen s uzlem . $A$ $B$ $B$

Časová náročnost operací vyhledávání, přidávání a odebírání prvku ze základního stromu se odhaduje jako , kde je délka zpracovávaného prvku. Doba běhu nezávisí na počtu prvků ve stromu. $OK)$ $k$

Na rozdíl od konvenčních předponových stromů může být uzel základního stromu označen buď jedním prvkem (znakem, bitem atd.) nebo sekvencí prvků. Díky tomu je základní strom efektivnější pro malé sady řetězců (zejména pokud jsou samotné řetězce dostatečně dlouhé) a také pro sady, které mají malý počet dlouhých prefixů.

Aplikace

Základní strom se používá zejména pro parsování přirozených jazyků [2] .
Základním stromem je jedna z datových struktur linuxového jádra [3] .

Poznámky

↑ Radix Tree struktura pro kompresi dat https://habrahabr.ru/post/141145/ Archivováno 20. prosince 2016 na Wayback Machine
↑ Pymorphy 2 https://m.habrahabr.ru/post/176575/ Archivováno 19. června 2017 na Wayback Machine
↑ Robert Love. Vývoj jádra Linuxu. třetí edice. 2010 https://docs.google.com/file/d/0B1iyZaHiAMfFZE9aXzNBOXR0OGM/edit?pli=1 Archivováno 15. prosince 2015 na Wayback Machine

Odkazy

Algoritmy a datové struktury Výzkum a referenční materiál: PATRICIA , Lloyd Allison, Monash University
Patricia Tree , NIST slovník algoritmů a datových struktur
Crit-bit stromy , Daniel J. Bernstein
Radix Tree API v linuxovém jádru od Jonathana Corbeta
Kart (key alteration radix tree) od Paula Jarce

Strom (datová struktura)
Binární vyhledávací strom Strom (teorie grafů) stromová struktura
Binární stromy	binární strom T-strom
Samovyrovnávací binární stromy	AA strom strom AVL Červeno-černý strom Rozvětvený strom strom s pokutami karteziánský strom Fibonacciho strom B-strom T-strom
B-stromy	2-3-strom B⁺-strom B*-strom B x -strom UB strom 2-3-4 strom (a,b)-strom tančící strom
předponové stromy	příponový strom Komprimovaný strom předpon Ternární vyhledávací strom
Binární dělení prostoru	k-rozměrný strom VP strom
Nebinární stromy	Čtyřstrom oktree Řídký Voxel Octree exponenciální strom PQ strom
Rozbití prostoru	R-strom Hilbertův R-strom R+-strom R*-strom X-strom M-strom Fenwickův strom Segmentový strom
Jiné stromy	halda hash tree prstový strom metrický strom Potahový strom BK-strom Dvouřetězový strom iVzdálenost Link-cut strom LSM strom
Algoritmy	Šířka první hledání Hloubka první hledání Algoritmus DSW protokol spanning tree