X-брзо дрво

X-fast tree
Тип Trie
Смишљено 1982
Смисллио Dan Willard
Asymptotic complexity

in big O notation

Простор O(n log M)
Претраживање O(log log M)
Убацивање O(log M) amortized
Брисање O(log M) amortized

У рачунарској науци, x-брзо дрво је структура података за чување целих бројева из повезаног домена. Подржава упите и предака и наследника у времену O(log log M), коришћењем O(n log M) простора, где је n број сачуваних вредности и M максимална вредност у домену. Структуру је предложио Dan Willard у 1982,[1] уз компликованије y-брзо дрво, као начин да побољша коришћење van Emde Boas дрвећа, задржавајући O(log log M) време упита.

Структура

[уреди | уреди извор]
A binary tree with 4 levels. The nodes on each level are: 3: (), 2: (0) and (1), 1: (00) and (10), 0: (001), (100) and (101). The unlabeled node is the root. There are directed edges between the folllowing nodes: ()->(0), ()->(1), (0)->(00), (0)->(001) in blue, (1)->(10), (1)->(101) in blue, (00)->(001) twice, once in blue, (10)->(100), (10)->(101), (001)<->(100), (100)<->(101). The nodes on each level are contained in a box, labeled with LSS(<level>).
An x-fast trie containing the integers 1 (0012), 4 (1002) and 5 (1012). Blue edges indicate descendant pointers.

x-брзо дрво је bitwise trie:  бинарно дрво где свако подрво чува вредности чије бинарне репрезентације почињу с истим префиксом. Сваки унутрашњи чвор је означен са честим префиксом вредности у његовом поддрвету и типично, лево дете додаје нулу на крај префикса, док десно дете додаје јединицу. Бинарна репрезентација целих бројева између 0 и M − 1 користи ⌈log2 M⌉ битова, тако да је висина дрвета O(log M).

Све вредности у x-брзом дрвету се чувају на листовима. Унутрашњи чворови се чувају само ако имају листове у њиховом поддрвету. Ако унутрашњи чвор нема лево дете, он чува показивач на најмањи лист у сво поддрвету, који се зове наследнички показивач. Слично, ако нема десно дете, чува показивач на највећи лист у свом левом поддрвету. Сваки лист чува показивач на претка и наследника, и тако формира двоструко повезану листу. Коначно, постоји хеш табела за сваки ниво која садржи све чворове на том нивоу. Заједно, ове хеш табеле из level-search структуре (LSS). Да гарантује времена упита у најгорем случају, ове хеш табеле би користиле динамички савршено хеширање или cuckoo hashing.

Тотално заузимање простора је O(n log M), јер сваки елемент има пут од корена до листа дужине O(log M).

Операције

[уреди | уреди извор]

Као van Emde Boas дрвећа, x-брза дрвећа подржавају операције уређеног associative array. Ово укључује уобичајене операције асоцијативног низа, заједно са још две операције сређивања, Successor и Predecessor:

  • Find(k): тражи вредност повезан са датим кључем
  • Successor(k): тражи кључ/вредност пар са најмањим кључем већим или једнаким датом кључу
  • Predecessor(k): тражи кључ/вредност пар са највећим кључем мањим или једнаким датом кључу
  • Insert(k, v): убаци дати кључ/вредност пар
  • Delete(k): уклони кључ/вредност пар са датим кључем

Тражење

[уреди | уреди извор]

Пронађи вредност повезану са кључем k који је у структури података може да се изврши у константном времену тражећи k у LSS[0], што је хеш табела на свим листовима.[2]

Наследник и предак

[уреди | уреди извор]

Д би пронашли претка или наследника кључа k, прво тражимо Ak, најнижег наследника k. Ово је чвор чвор у дрвету који има најдужи слични префикс са k. Да би пронашли Ak, изводимо бинарну претрагу на нивоима. Почињемо на нивоу h/2, где је h висина дрвета. На сваком нивоу, користимо одговарајућу хеш табелу у структури са префиксом k одговарајуће дужине. Ако чвор с тим префиксом не постоји, знамо да Ak мора да буде на вишем нивоу и ограничавамо нашу претрагу на њих. Ако чвор с тим префиксом постоји, Ak не може бити на вишем нивоу, премда ограничавамо претрагу на тренутним и нижим нивоима.

Када пронађемо најнижег наследника k, знамо да има листове у неким од својих поддрвећа (у супротном не би били у дрвету) и k би требало да буде у дргом поддрвету. Премда наследнички показивач показује на наследника или претка од k. У зависности од тога који тражим, можда би требало да предузмемо један корак у повезаној листи до претходног или следећег листа.

С обзиром да дрво има висину O(log M), бинарна претрага за најнижег наследника узима време од O(log log M). Посе тога, наследник или предак могу да се пронађу у константном времену, тако да укупно време упиа износи O(log log M).[1]

Убацивање

[уреди | уреди извор]

Да бисмо убацили кључ/вредност пар (k, v), прво тражимо претка и наследника од k. Онда стварамо нови лист за k, убацујемо га у повезану листу на листове између наследника и претка, и дајемо му показивач на v. Даље, идемо од корена до новог листа, стварајући неопходне чворове на путу наниже, убацујући их у респективне хеш табеле и ажурирамо наследничке показиваче ако је неопходно.

Јер морамо да прођемо кроз читаву висину дрвета, процес одузима време од O(log M) .[3]

Брисање

[уреди | уреди извор]

Да бисмо обрисали кључ k, тражимо лист користећи хеш табел на листовима. Уклањамо је из повезане листе, али памтимо ко су били наследник и предак. Онда се крећемо од листа до корена дрвета, уклањајући све чворове чија су поддрва садржавала k и ажурирамо наследничке показиваче где је потребно. Наследнички показивачи који су  коришћени за показивање на k ће сада показивати или на наследника или на претка од k, у зависности од поддрвета које недостаје.

Као убацивање, ово узима O(log M) времена, јер морамо да прођемо кроз сваки ниво дрвета.[3]

Дискусија

[уреди | уреди извор]

Willard је представио x-брзо дрвеће углавном као увод у y-брзо дрвеће, које омогућује исто време упита, користећи само O(n) простора и дозвољавајући убацивања и брисања у времену од O(log log M) .[1]

Техника компресије је слична patricia tries може да се користи да знатно смањи коришћење простора x-брзих дрвећа у пракси.[4]

Коришћењем експоненцијалног претраживања пре бинарног по нивоима и слањем упита не само тренутном префиксу x, него такође његовом наследнику x + 1, x-брзо дрвеће може да одговори на упите предака и наследника у времену од O(log log Δ), где је Δ разлика између вредности упита и његовок претка и наследника.[2]

Референце

[уреди | уреди извор]
  1. ^ а б в Willard, Dan E. (1983).
  2. ^ а б Bose, Prosenjit; Douïeb, Karim; Dujmović, Vida; Howat, John; Morin, Pat (2010), Fast Local Searches and Updates in Bounded Universes (PDF), Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010). стр. 261–264
  3. ^ а б Schulz, André; Christiano, Paul (2010-03-04).
  4. ^ Kementsietsidis, Anastasios; Wang, Min (2009), Provenance Query Evaluation: What’s so special about it?, Proceedings of the 18th ACM conference on Information and knowledge management. стр. 681–690

Спољашње везе

[уреди | уреди извор]