Tömörített előtag fa

alapfa
Típusú	faipari
Feltalálás éve	1968
Szerző	Donald R. Morrison
Bonyolultság az O-szimbólumokban
Legrosszabb esetben Keresés Beszúrás Eltávolítás
Médiafájlok a Wikimedia Commons oldalon

Az  alapfa ( radix fa , még kompakt előtag fa , főfa , maradékfa [1] ) olyan adatstruktúra, amely egy előtag fa memóriára optimalizált megvalósítása. Az alapfában az a csomópont , amely a csomópont egyetlen gyermeke, összevonódik a csomóponttal .

Az elem keresésének, hozzáadásának és az alapfából való eltávolításának műveleteinek időbeli összetettségét a következőképpen becsüljük meg : ahol  a feldolgozás alatt álló elem hossza. A futási idő nem függ a fában lévő elemek számától.

A hagyományos előtagfákkal ellentétben az alapfa csomópontja egyetlen elemmel (karakterrel, bittel stb.) vagy elemek sorozatával is felcímkézhető. Ez hatékonyabbá teszi az alapfát kis karakterlánc-készletek esetén (különösen, ha maguk a karakterláncok elég hosszúak), és olyan halmazok esetében is, amelyeknek kevés hosszú előtagja van.

Alkalmazás

• Az alapfát különösen a természetes nyelvek elemzésére használják [2] .
• Az alapfa a Linux kernel egyik adatstruktúrája [3] .

Jegyzetek

1. ↑ Radix Tree szerkezet adattömörítéshez https://habrahabr.ru/post/141145/ Archivált : 2016. december 20. a Wayback Machine -nél
2. ↑ Pymorphy 2 https://m.habrahabr.ru/post/176575/ Archivált : 2017. június 19. a Wayback Machine -nél
3. ↑ Robert Love. Linux kernel fejlesztés. harmadik kiadás. 2010 https://docs.google.com/file/d/0B1iyZaHiAMfFZE9aXzNBOXR0OGM/edit?pli=1 Archiválva : 2015. december 15. a Wayback Machine -nél

Linkek

• Algoritmusok és adatstruktúrák kutatási és referenciaanyag: PATRICIA , Lloyd Allison, Monash Egyetem
• Patricia Tree , NIST Dictionary of Algorithms and Data Structures
• Crit-bit trees , Daniel J. Bernstein
• Radix Tree API a Linux kernelben , Jonathan Corbet
• Kart (key alteration radix tree) , szerző: Paul Jarc