Pakattu etuliitepuu

peruspuu

Tyyppi

puu

Keksintövuosi

1968

Tekijä

Donald R. Morrison

	Pahimmillaan
Hae	$O(k)$
Lisää	$O(k)$
Poistaminen	$O(k)$

Mediatiedostot Wikimedia Commonsissa

Peruspuu ( kantalukupuu , myös kompakti etuliitepuu , pääpuu , jäännöspuu [1] ) on tietorakenne, joka on etuliitepuun muistiin optimoitu toteutus. Peruspuussa solmu , joka on solmun ainoa lapsi, yhdistetään solmuun . $A$ $B$ $B$

Elementin etsintä-, lisäys- ja poistooperaatioiden aikamonimutkaisuus peruspuusta on arvioitu muodossa , jossa on käsiteltävän elementin pituus. Ajoaika ei riipu puun elementtien määrästä. $O(k)$ $k$

Perinteisistä etuliitepuista poiketen peruspuusolmu voidaan merkitä joko yhdellä elementillä (merkki, bitti jne.) tai elementtien sarjalla. Tämä tekee peruspuusta tehokkaamman pienille merkkijonojoukoille (varsinkin jos itse merkkijonot ovat riittävän pitkiä) ja myös joukoille, joissa on pieni määrä pitkiä etuliitteitä.

Sovellus

Peruspuuta käytetään erityisesti luonnollisten kielten jäsentämiseen [2] .
Peruspuu on yksi Linux-ytimen tietorakenteista [3] .

Muistiinpanot

↑ Radix Tree -rakenne tietojen pakkaamiseen https://habrahabr.ru/post/141145/ Arkistoitu 20. joulukuuta 2016 Wayback Machinessa
↑ Pymorphy 2 https://m.habrahabr.ru/post/176575/ Arkistoitu 19. kesäkuuta 2017 Wayback Machinessa
↑ Robert Love. Linux-ytimen kehitys. kolmas painos. 2010 https://docs.google.com/file/d/0B1iyZaHiAMfFZE9aXzNBOXR0OGM/edit?pli=1 Arkistoitu 15. joulukuuta 2015 Wayback Machinessa

Linkit

Algoritmit ja tietorakenteet tutkimus- ja viitemateriaali: PATRICIA , kirjoittanut Lloyd Allison, Monashin yliopisto
Patricia Tree , NIST Dictionary of Algorithms and Data Structures
Crit-bit trees , kirjoittanut Daniel J. Bernstein
Radix Tree API Linux-ytimessä , Jonathan Corbet
Kart (key alteration radix tree) , kirjoittanut Paul Jarc

Puu (tietorakenne)
Binäärihakupuu Puu (graafiteoria) puun rakenne
Binääripuut	binääripuu T-puu
Itsetasapainottavat binaaripuut	AA puu AVL puu Puna-musta puu Splay-puu puu sakkoilla karteesinen puu Fibonacci puu B-puu T-puu
B-puut	2-3-puu B⁺-puu B*-puu B x -puu UB puu 2-3-4 puu (a,b)-puu tanssiva puu
etuliite puita	suffiksi puu Pakattu etuliitepuu Kolmiosainen hakupuu
Avaruuden binaarinen osiointi	k-ulotteinen puu VP-puu
Ei-binääripuut	Quadtree oktreen Harva Voxel Octree eksponentiaalinen puu PQ puu
Avaruuden hajottaminen	R-puu Hilbert R-puu R+-puu R*-puu X-puu M-puu Fenwick puu Segmenttipuu
Muut puut	pino hash puu sormipuu metrinen puu Päällystyspuu BK-puu Kaksiketjuinen puu iDistance Linkistä leikattu puu LSM puu
Algoritmit	Leveys ensimmäinen haku Ensimmäinen syvyyshaku DSW-algoritmi kattava puu protokolla