Komprimerat prefixträd

basträd
Sorts	trä
Uppfinningens år	1968
Författare	Donald R. Morrison
Komplexitet i O-symboler
Som värst Sök Föra in Borttagning
Mediafiler på Wikimedia Commons

Ett  grundträd ( radixträd , även kompakt prefixträd , huvudträd, restträd [1] ) är en datastruktur som är en minnesoptimerad implementering av ett prefixträd. I basträdet slås noden som är det enda underordnade till noden samman med noden .

Tidskomplexiteten för operationerna för att söka, lägga till och ta bort ett element från basträdet uppskattas som , där  är längden på elementet som bearbetas. Körtiden beror inte på antalet element i trädet.

Till skillnad från konventionella prefixträd kan en basträdnod märkas med antingen ett enskilt element (tecken, bit, etc.) eller en sekvens av element. Detta gör basträdet mer effektivt för små uppsättningar av strängar (särskilt om själva strängarna är tillräckligt långa), och även för uppsättningar som har ett litet antal långa prefix.

Applikation

• Basträdet används i synnerhet för att analysera naturliga språk [2] .
• Basträdet är en av Linux-kärnans datastrukturer [3] .

Anteckningar

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

Länkar

• Algoritmer och datastrukturer Forskning och referensmaterial: PATRICIA , av Lloyd Allison, Monash University
• Patricia Tree , NIST Dictionary of Algorithms and Data Structures
• Crit-bit trees , av Daniel J. Bernstein
• Radix Tree API i Linux-kärnan , av Jonathan Corbet
• Kart (nyckeländring radixträd) , av Paul Jarc