Стабло жртвеног јарца

У рачунарству скапегоат трее (или жртвени јарац стабло) је бинарно стабло претраге откривено од стране Арнеа Андерсона^[1] и поново од стране Игала Галперина и Роналда L. Ривеста.^[2]. Сложеностје у најгорем слуцају О(лог н) за претраживање и амортизовано време уметања и брисања од само О(лог н).

За разлику од већине самобалансирајућих бинарних стабала који обезбедити најгоре време од О(лог н) за проналажење, овај тип нема додатну меморију за пре-цворове, као код других стабла за претразивање. У чвоу се цува само клуч и два показивача, на синове. Чиме се остварује уштеда меморијског простора до чак 1/3. Ова структура чини стабло жртвеног јарца лакшим за имплеменетацију.

Теорија

Бинарно стабло претраге се каже да је тежински уравнотежен ако половина чворова су на левој страни корена , а половина на десној. α-тежина-избалансиран се стога дефинише као испуњавање следећих услова:

сизе(лефт) <= α*сизе(ноде) сизе(ригхт) <= α*сизе(ноде) -- велицина (лево) <= α*велицина (цвора) велицина (десно) <= α*велицина (цвора)

Где се величина мосе дефенисати рекурзивно као:

фунцтион сизе(ноде)

if node = nil
 return 0
else
 return size(node->left) + size(node->right) + 1

енд

Где би α једнако опсивало да је повезани лист балансиран, где би 0,5 одговорало скоро попуњеним бинарним стаблима. За балансирано стабло претраге које је α-тежински-балансирано мора да буде и α-висински балансирано.

хеигхт(трее) <= лог1/α(НодеЦоунт)

Жртвени јарац нису гаранти да одржавају α-тежински-балансирање али су увек отприлике α-висински балансирана.

хеигхт(сцапегоат трее) <= лог1/α(НодеЦоунт) + 1

Ово чине жртвени јарац стабло сличним црвено-црним стаблима у томе да су обоје ограничени с висином. Они се у највишој мери разликују у имплементацији одлућивања где це изврсити ротациа (или ребаласирање у слуцају жрвеног јарца). Где црвено-црна стабла додају екстра информацију у облику 'боје' да дефенисе локација, жрвени јарац налази жрвеног јарца где није α-тежински-балансиран да изврси ребалансирајуце операције. Ово је блиско са АВЛ стаблима, у томе да актуелна ротација зависи од 'баланса' чворова, али детерминација баланса се драстично разликује.Пошто АВЛ стабла провера стање вредности на сваком убацивању / брисању, типично је податак чуван у сваком чвору; жртвени-јарац-стабла су у стању да га израчунају само по потреби , што је само када треба жртвени јарац да се пронађе . За разлику од вечиње само балансирајуцих стабла,жртвени јарац стабла су у потпуности флексибилни код њиховог балансирања.Они подржавају било какву α тај што су 0,5 < α < 1. α високе вредности има као резултат мање балансирања,чинећи убацивање брже него претрразивање и брисања који буду спорији, и обрното за α које узима малу вредност. У практичној примени α мозе да се изабере према томе какве су фреквенције одговарајућих операција.

Операције

Убацивање

Убацивање се реализује са истим основним идејама као неуравнотежене бинарном стаблу претраге , међутим уз неколико значајних промена. Када пронадје жељењу тачку уметања ,дубина новог чвора мора бити забележен. Ово се реализује путем једноставног бројача који се увећава током сваке итерације док се не пронадје,ефикасно броји гране између корена и чвора који се убације. Ако овај чвор крши α-висина-билансну својство (дефинисан горе), потребна је ребаланс. За ребаланс цело под стабло испод цвора жртвеног јарца улази у балансирање. Жртвени јарац је дефинисана као предак од убаченог чвора који није α-тежина-уравнотежен. Увек це бити бар један такав предак. Ребаланс било којих од њих ће обновити α-висина-уравнотежено својство.

Један начин проналажање жртвеног јарца, је да се пењемо од убаченог чвора натраг до корена стабла, и обележети први чвор који није α-тежина-уравнотежен.

Пењане натраг до корена захтева О(лог н) меморијски простор, обисно алоциран на стеку или родитељске показиваче. Ово се заправо може избећи указујући сваком детету на свом родитељу како идете доле, а поправити у повратку назад.

Да би утврдили да ли је чвор повољан као жртвени јарац може да се вратимо на дефеницију:

size(left) <= α*size(node)
size(right) <= α*size(node)

Велика оптимизација се може извршити кад се утврди да ми већ у суштини имамо две од 3 тражене величине и морамо да рачунамо само последњу. Размотрањем следећег примера ћемо да демонстрирамо ово. Под претпоставком да се пењемо назад до корена.

size(parent) = size(node) + size(sibling) + 1

али како:

size(inserted node) = 1.

Сличај постаје тривиалан:

size[x+1] = size[x] + size(sibling) + 1

Где је x = чвор, а x+1 родитељ и једини позив који нам је потребан је позив сизе(брата).

Једном кад је жртвено јаре надјено, под стабло закачено на жртвеног јарца је изнова креирано да буде балансирано.^[2]. Ово се може урадити за О(н) времена, тако сто ћемо да предјемо преко свих чворова подстабла, да би установили њихове вредностиу сортираном поретку, и рекрузивно бирамо медијану као корен подстабла.

Пошто ребаланси узимају временску сложеност од О(н) за најгору ситуацију то је уједно и временска сложеност, али пошто су најгори слуцајеви ретки амортизована временска слозеност ће бити О(лог н).

Скица доказа за трошкове уметања

Небалансираност чвора в је апсолутна вредност разлика у величини између његовог левог и десног чвора минус 1 или 0, које год је веће. Другим речима:

$I(v)=max(|left(v)-right(v)|-1,0)\$

Одмах после изградње под стабла в, л(в)=0.

Лема: Пре изградње под стабла цвора в:

$I(v)=\Omega (|v|)\$
( $\Omega \$ ис Биг О Нотатион.)

Доказ леме:

Нека је $v_{0}$ корен одмах после креирања $h(v_{0})=log(|v_{0}|+1)\$ Ако је $\Omega (|v_{0}|)$ дегенерисано уметање (то јест, где је сваки убаченог повећава висину 1), затим

$I(v)=\Omega (|v_{0}|)\$ ,
$h(v)=h(v_{0})+\Omega (|v_{0}|)\$ и
$log(|v|)\leq log(|v_{0}|+1)+1\$ .

Посто је $I(v)=\Omega (|v|)$ пре поновног прављења $\Omega (|v|)$ инсерције у подстаблу са кореном у $v$ која није довела у обнови. Сваки од ових уметања се могу извести у О (лог н). Коначна уметање која изазива трошкове $O(|v|)$ Коришћење укупну анализе постаје јасно да амортизују трошкови уметак је $O(logn)$

${\Omega (|v|)O(\log {n})+O(|v|) \over \Omega (|v|)}=O(\log {n})\$

Брисање

Жртвени јарац стабла су необична по томе што је брисање лакше него убацивање. Да бисте омогућили брисање, жртвени јарац стабла је потребно да се сачува додатна вредност са структуром података стабла. Ово својство, коју ћемо звати МаxНодеЦоунт једноставно представља највишу постигнуту НодеЦоунт. Постављен је за НодеЦоунт кад год се ребалансира цело стабло, а након убацивања постављен је на маx(МаxНодеЦоунт, НодеЦоунт).Да би се извршило брисање, ми једноставно уклонимо чвор као што би у једноставном бинарном стаблу претраге, али ако

NodeCount <= α*MaxNodeCount

онда ћемо ребаланс цело стабло око корена, сећајући да поставимо МаxНодеЦоунт на НодеЦоунт. Ово даје брисање за свој најгори могући учинак О (н) , али се амортизује за О (лог н) просечно време.

Скица доказа за трошкове брисања

Претпоставимо а зртвени јарац стабло има $n$ елемената и управо је било поново креирано, (другим рецима комплетно бинарно стабло је). Највисе $n/2-1$ брисања се мозе обавити пре него што се стабло мора наново креирати. Свако ово брисање кошта $O(\log {n})$ времена,(време да се надје елемант и обележи) после $n/2$ пута це изазвати да се стабло поново изгради. $O(\log {n})+O(n)$ Коришћење укупну анализе постаје јасно да трошкове отплате брисање је $O(\log {n})$ :

${\sum _{1}^{n \over 2}O(\log {n})+O(n) \over {n \over 2}}={{n \over 2}O(\log {n})+O(n) \over {n \over 2}}=O(\log {n})\$

Претрага

Претрага није модификован од стране стандардног стабле претраге, и има најгоре време од О(лог н). Ово је супротно Угаоном стабло која имају најгору слоyеност од О(н).Смањена меморије за чворове у односу на друге само-балансирајуће бинарних стабала претраге може додатно побољшати локалне референце и кеша.

Референце

^ Андерссон, Арне (1989). „Импровинг партиал ребуилдинг бy усинг симпле баланце цритериа”. Проц. Wорксхоп он Алгоритхмс анд Дата Струцтурес. Јоурнал оф Алгоритхмс. Спрингер-Верлаг. стр. 393—402. дои:10.1007/3-540-51542-9_33.
^ ^а ^б Галперин, Игал; Ривест, Роналд L. „Сцапегоат треес”. Процеедингс оф тхе фоуртх аннуал АЦМ-СИАМ Сyмпосиум он Дисцрете алгоритхмс: 165—174 yеар=1993

Види још

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

[anderson1-1] Андерссон, Арне (1989). „Импровинг партиал ребуилдинг бy усинг симпле баланце цритериа”. Проц. Wорксхоп он Алгоритхмс анд Дата Струцтурес. Јоурнал оф Алгоритхмс. Спрингер-Верлаг. стр. 393—402. дои:10.1007/3-540-51542-9_33.

[galperin_rivest-2] а ^б Галперин, Игал; Ривест, Роналд L. „Сцапегоат треес”. Процеедингс оф тхе фоуртх аннуал АЦМ-СИАМ Сyмпосиум он Дисцрете алгоритхмс: 165—174 yеар=1993

[1]

[2]