Arborele de prefix comprimat

arborele de bază

Tip de

lemn

Anul inventiei

1968

Autor

Donald R. Morrison

	În cel mai rău caz
Căutare	$O.K)$
Introduce	$O.K)$
Îndepărtarea	$O.K)$

Fișiere media la Wikimedia Commons

Un arbore de bază ( arbore de bază , arbore de prefix compact , arbore principal, arbore rezidual [1] ) este o structură de date care este o implementare optimizată pentru memorie a unui arbore de prefix. În arborele de bază, nodul care este singurul copil al nodului este îmbinat cu nodul . $A$ $B$ $B$

Complexitatea de timp a operațiunilor de căutare, adăugare și eliminare a unui element din arborele de bază este estimată ca , unde este lungimea elementului procesat. Timpul de rulare nu depinde de numărul de elemente din arbore. $O.K)$ $k$

Spre deosebire de arborii de prefix convențional, un nod de arbore de bază poate fi etichetat fie cu un singur element (caracter, bit etc.) fie cu o secvență de elemente. Acest lucru face ca arborele de bază să fie mai eficient pentru seturi mici de șiruri (mai ales dacă șirurile în sine sunt suficient de lungi), precum și pentru seturile care au un număr mic de prefixe lungi.

Aplicație

Arborele de bază este folosit, în special, pentru analiza limbilor naturale [2] .
Arborele de bază este una dintre structurile de date ale nucleului Linux [3] .

Note

↑ Structura Radix Tree pentru compresia datelor https://habrahabr.ru/post/141145/ Arhivat 20 decembrie 2016 la Wayback Machine
↑ Pymorphy 2 https://m.habrahabr.ru/post/176575/ Arhivat 19 iunie 2017 la Wayback Machine
↑ Robert Love. Dezvoltarea kernelului Linux. A treia editie. 2010 https://docs.google.com/file/d/0B1iyZaHiAMfFZE9aXzNBOXR0OGM/edit?pli=1 Arhivat 15 decembrie 2015 la Wayback Machine

Link -uri

Algoritmi și structuri de date Material de cercetare și referință: PATRICIA , de Lloyd Allison, Universitatea Monash
Patricia Tree , Dicționar NIST de algoritmi și structuri de date
Crit-bit trees , de Daniel J. Bernstein
API-ul Radix Tree în kernelul Linux , de Jonathan Corbet
Kart (cheie alterare radix arbore) , de Paul Jarc

Arborele (structura de date)
Arborele de căutare binar Arborele (teoria graficelor) structura arborelui
Arbori binari	arbore binar T-tree
Arbori binari cu auto-echilibrare	arbore AA arborele AVL Copac roșu-negru Splay arbore copac cu amenzi arbore cartezian Arborele Fibonacci B-arborele T-tree
B-copaci	2-3-copac B⁺-arborele B*-copac B x -arbore arborele UB 2-3-4 arbore (a,b)-copac copac dansant
arbori de prefix	arbore de sufix Arborele de prefix comprimat Arborele de căutare ternar
Partiționarea binară a spațiului	arbore k-dimensional arborele VP
Arbori non-binari	Quadtree octree Voxel rar Octree arbore exponenţial Arborele PQ
Despărțirea spațiului	R-arborele Arborele R Hilbert R+-arborele R*-copac X-arborele M-arbore Arborele Fenwick Arborele de segmente
Alți copaci	morman arbore de hash arborele degetelor arbore metric Arborele de acoperire BK-arborele Copac cu lanțuri duble iDistanța Arbore tăiat de legături Arborele LSM
Algoritmi	Lățimea prima căutare Profunzime prima căutare Algoritmul DSW protocolul spanning tree