Сплаи стабла су самобалансирајућа или самоприлагођена бинарна стабла претраге. Другим речима, можемо рећи да су стабла ширења варијанте бинарних стабала претраге. Предуслов за сплаи стабла које треба да знамо о бинарним стаблима претраге.
Као што већ знамо, временска сложеност бинарног стабла претраге у сваком случају. Временска сложеност бинарног стабла претраге у просечном случају је О(пријава) а временска сложеност у најгорем случају је О(н). У бинарном стаблу претраге, вредност левог подстабла је мања од коренског чвора, а вредност десног подстабла је већа од коренског чвора; у том случају би временска сложеност била О(пријава) . Ако је бинарно стабло закривљено лево или десно, онда би временска сложеност била О(н). Да би се ограничила искривљеност, АВЛ и црвено-црно дрво дошао у слику, имајући О(логн ) временска сложеност за све операције у свим случајевима. Такође можемо побољшати ову временску сложеност тако што ћемо радити практичније имплементације, тако да ново дрво Шта је Сплаи Трее?
Сплаи дрво је самобалансирајуће дрво, али АВЛ и црвено-црна стабла су тада такође самобалансирајућа стабла. Оно што чини сплаи дрво јединственим два дрвета. Има једно додатно својство које га чини јединственим је распршивање.
Сплаи стабло садржи исте операције као а Бинарно стабло претраге , односно уметање, брисање и претраживање, али садржи и још једну операцију, тј. Тако. све операције у стаблу развлачења су праћене сплаиингом.
Сплаи стабла нису стриктно избалансирана стабла, али су грубо избалансирана стабла. Хајде да разумемо операцију претраживања у стаблу приказа.
Претпоставимо да желимо да претражимо 7 елемента у стаблу, које је приказано испод:
Да бисмо претражили било који елемент у стаблу приказа, прво ћемо извршити стандардну операцију бинарног стабла претраге. Како је 7 мање од 10, тако ћемо доћи лево од коренског чвора. Након извршења операције претраживања, потребно је да извршимо распршивање. Овде излагање значи да операција коју изводимо на било ком елементу треба да постане основни чвор након извођења неких преуређивања. Преуређење дрвета ће се вршити кроз ротације.
Напомена: Сплаи стабло се може дефинисати као самоприлагођено стабло у коме би било која операција извршена на елементу преуредила стабло тако да елемент на коме је операција извршена постане коренски чвор стабла.
Ротатионс
Постоји шест типова ротација које се користе за развлачење:
- Зиг ротација (десна ротација)
- Закривљена ротација (ротација улево)
- цик цак (цик за којим следи цак)
- Заг цик (цак праћен цик)
- цик цик (две десне ротације)
- Заг заг (две леве ротације)
Фактори потребни за избор врсте ротације
Следећи фактори се користе за избор типа ротације:
- Да ли чвор који покушавамо да ротирамо има баку и деду?
- Да ли је чвор лево или десно дете родитеља?
- Да ли је чвор лево или десно дете баке и деде?
Случајеви за ротације
Случај 1: Ако чвор нема бабу-родитеља, и ако је десно дете родитеља, онда вршимо леву ротацију; иначе се врши права ротација.
Случај 2: Ако чвор има бабу и деду, онда на основу следећих сценарија; ротација би се извршила:
Сценарио 1: Ако је чвор десно од родитеља, а родитељ је такође десно од свог родитеља, онда цик цик десно десно ротирање је извођен.
Сценарио 2: Ако је чвор лево од родитеља, али је родитељ десно од свог родитеља, онда цик-цак десна лева ротација је извођен.
Сценарио 3: Ако је чвор десно од родитеља, а родитељ десно од свог родитеља, онда зиг зиг лево ротација је извођен.
Сценарио 4: Ако је чвор десно од родитеља, али је родитељ лево од свог родитеља, онда цик-цак ротација десно-лево је извођен.
Сада, хајде да разумемо горње ротације са примерима.
Да бисмо преуредили дрво, потребно је да извршимо неке ротације. Следећи су типови ротација у стаблу развода:
Цик ротације се користе када је ставка која се тражи или основни чвор или дете основног чвора (тј. лево или десно дете).
Следећи случајеви могу постојати у стаблу приказа током претраге:
Случај 1: Ако је ставка за претрагу коренски чвор стабла.
Случај 2: Ако је ставка за претрагу подређена основном чвору, тада ће бити ту два сценарија:
- Ако је дете лево дете, извршиће се десна ротација, позната као цик ротација удесно.
- Ако је дете десно дете, извршиће се лева ротација, позната као зиг лево.
Погледајмо горња два сценарија кроз пример.
Размотрите следећи пример:
У горњем примеру, морамо да претражимо 7 елемента у стаблу. Пратићемо следеће кораке:
Корак 1: Прво, упоредимо 7 са коренским чвором. Како је 7 мање од 10, то је лево дете коренског чвора.
Корак 2: Када се елемент пронађе, извршићемо распршивање. Десна ротација се изводи тако да 7 постане коренски чвор стабла, као што је приказано у наставку:
Хајде да размотримо још један пример.
У горњем примеру, морамо да претражимо 20 елемената у стаблу. Пратићемо следеће кораке:
Корак 1: Прво, упоредимо 20 са коренским чвором. Како је 20 веће од коренског чвора, то је право дете коренског чвора.
Корак 2: Када се елемент пронађе, извршићемо распршивање. Лева ротација се врши тако да 20 елемент постане коренски чвор стабла.
Понекад се јавља ситуација када предмет који се тражи има родитеља као и баку и деду. У овом случају морамо да извршимо четири ротације за распршивање.
Хајде да разумемо овај случај кроз пример.
Претпоставимо да морамо да претражимо 1 елемент у стаблу, што је приказано испод:
Корак 1: Прво, морамо да извршимо стандардну операцију претраживања БСТ-а да бисмо претражили 1 елемент. Како је 1 мање од 10 и 7, тако ће бити лево од чвора 7. Дакле, елемент 1 има родитеља, тј. 7, као и бабу и деду, тј. 10.
Корак 2: У овом кораку морамо да изведемо распршивање. Морамо да направимо чвор 1 као коренски чвор уз помоћ неких ротација. У овом случају, не можемо једноставно извршити цик или цак ротацију; морамо да применимо цик цик ротацију.
Да бисмо направили чвор 1 као коренски чвор, потребно је да извршимо две десне ротације познате као цик цик ротације. Када извршимо десну ротацију, тада ће се 10 померити надоле, а чвор 7 ће доћи нагоре као што је приказано на доњој слици:
Опет ћемо извршити цик-десну ротацију, чвор 7 ће се померити надоле, а чвор 1 ће доћи нагоре као што је приказано испод:
Као што видимо на горњој слици да је чвор 1 постао коренски чвор стабла; дакле, претрага је завршена.
Претпоставимо да желимо да претражимо 20 у доњем стаблу.
Да бисмо претражили 20, потребно је да извршимо две леве ротације. Следе кораци потребни за претрагу 20 чвора:
Корак 1: Прво, изводимо стандардну операцију претраживања БСТ-а. Како је 20 веће од 10 и 15, тако ће бити десно од чвора 15.
Корак 2: Други корак је извођење прскања. У овом случају би се извршиле две леве ротације. У првој ротацији, чвор 10 ће се померити надоле, а чвор 15 ће се померити нагоре као што је приказано испод:
У другој левој ротацији, чвор 15 ће се померити надоле, а чвор 20 постаје коренски чвор стабла, као што је приказано у наставку:
Као што смо приметили да се изводе две леве ротације; па је позната као цик цик лево ротација.
До сада смо читали да су и родитељ и бака и деда или у РР или ЛЛ вези. Сада ћемо видети РЛ или ЛР однос између родитеља и баке и деде.
Хајде да разумемо овај случај кроз пример.
Претпоставимо да желимо да претражимо 13 елемента у стаблу које је приказано испод:
Корак 1: Прво, вршимо стандардну операцију претраживања БСТ-а. Како је 13 веће од 10, али мање од 15, тако ће чвор 13 бити лево дете чвора 15.
Корак 2: Пошто је чвор 13 лево од 15, а чвор 15 десно од чвора 10, тако да постоји РЛ веза. Прво, извршимо десну ротацију на чвору 15, и 15 ће се померити надоле, а чвор 13 ће доћи нагоре, као што је приказано испод:
Ипак, чвор 13 није коријенски чвор, а 13 је десно од коријенског чвора, тако да ћемо извршити ротацију улијево познато као заг ротација. Чвор 10 ће се померити надоле, а 13 ће постати основни чвор као што је приказано у наставку:
Као што можемо приметити у горњем стаблу да је чвор 13 постао коренски чвор; стога је претрага завршена. У овом случају, прво смо извршили цик ротацију, а затим цик ротацију; па је позната као цик-цак ротација.
Хајде да разумемо овај случај кроз пример.
Претпоставимо да желимо да претражимо 9 елемента у стаблу, које је приказано испод:
Корак 1: Прво, изводимо стандардну операцију претраживања БСТ-а. Како је 9 мање од 10, али веће од 7, то ће бити право дете чвора 7.
Корак 2: Пошто је чвор 9 десно од чвора 7, а чвор 7 лево од чвора 10, тако да постоји ЛР веза. Прво, вршимо леву ротацију на чвору 7. Чвор 7 ће се померити надоле, а чвор 9 се помера нагоре као што је приказано испод:
Ипак, чвор 9 није коренски чвор, а 9 је лево од коренског чвора, тако да ћемо извршити десну ротацију познату као зиг ротација. Након извршења десне ротације, чвор 9 постаје основни чвор, као што је приказано у наставку:
Као што можемо приметити у горњем стаблу да је чвор 13 коренски чвор; стога је претрага завршена. У овом случају прво смо извршили цик ротацију (лева ротација), а затим се изводи цик ротација (десна ротација), па је позната као цик ротација.
Предности Сплаи дрвета
- У стаблу приказа, не морамо да чувамо додатне информације. Насупрот томе, у АВЛ стаблима, морамо да ускладиштимо фактор равнотеже сваког чвора који захтева додатни простор, а црвено-црна стабла такође захтевају складиштење једног додатног бита информација који означава боју чвора, било црвену или црну.
- То је најбржи тип стабла бинарне претраге за различите практичне примене. Користи се у Виндовс НТ и ГЦЦ компајлери .
- Обезбеђује боље перформансе јер ће се чворови којима се често приступа померати ближе коренском чвору, због чега се елементима може брзо приступити у стаблима развода. Користи се у имплементацији кеша пошто се недавно приступљени подаци чувају у кешу тако да не морамо да идемо у меморију за приступ подацима, а потребно је и мање времена.
Недостатак Сплаи дрвета
Главни недостатак стабла сплеја би био да стабла нису стриктно избалансирана, то јест, грубо су избалансирана. Понекад су стабла сплаи линеарна, тако да ће бити потребно О(н) временске сложености.
Операција уметања у Сплаи стабло
У уметање операцију, прво убацујемо елемент у стабло, а затим вршимо операцију распростирања на уметнутом елементу.
15, 10, 17, 7
Корак 1: Прво убацујемо чвор 15 у дрво. Након уметања, потребно је да извршимо прскање. Како је 15 основни чвор, тако да не морамо да вршимо распростирање.
Корак 2: Следећи елемент је 10. Како је 10 мање од 15, тако ће чвор 10 бити лево дете чвора 15, као што је приказано у наставку:
Сада наступамо прскање . Да бисмо направили 10 као основни чвор, извршићемо десну ротацију, као што је приказано у наставку:
Корак 3: Следећи елемент је 17. Како је 17 веће од 10 и 15, тако ће постати право дете чвора 15.
Сада ћемо изводити прскање. Како 17 има родитеља као и баку и деду, ми ћемо изводити цик цик ротације.
На горњој слици, можемо приметити да 17 постаје коренски чвор дрвета; дакле, уметање је завршено.
4. корак: Следећи елемент је 7. Како је 7 мање од 17, 15 и 10, тако ће чвор 7 остати потомак 10.
Сада, морамо да распршимо дрво. Како 7 има родитеља као и баку и деду, извршићемо две десне ротације као што је приказано испод:
Ипак, чвор 7 није основни чвор, он је лево дете коренског чвора, тј. 17. Дакле, морамо да извршимо још једну десну ротацију да бисмо направили чвор 7 као коренски чвор као што је приказано испод:
Алгоритам за операцију уметања
Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n)
У горњем алгоритму, Т је стабло, а н је чвор који желимо да убацимо. Направили смо привремену променљиву која садржи адресу основног чвора. Покрећемо док петљу док вредност темп не постане НУЛЛ.
Када се убацивање заврши, извршиће се распршивање
Алгоритам за Сплаиинг операцију
Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y
У горњој имплементацији, к је чвор на коме се врши ротација, док је и лево дете чвора к.
Имплементација лефт.ротатион(Т, к)
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
У горњој имплементацији, к је чвор на коме се врши ротација, а и је десно дете чвора к.
Брисање у Сплаи стаблу
Као што знамо да су стабла приказивања варијанте стабла бинарног претраживања, тако да би операција брисања у стаблу приказа била слична БСТ-у, али једина разлика је у томе што се операција брисања у стаблима постављања прати операцијом ширења.
Врсте брисања:
Постоје две врсте брисања у стаблима приказа:
- Одоздо према горе
- Одозго према доле
Одоздо према горе
У излагању одоздо према горе, прво избришемо елемент из стабла, а затим вршимо извлачење на избрисаном чвору.
Хајде да разумемо брисање у Сплаи стаблу.
Претпоставимо да желимо да избришемо 12, 14 из стабла приказаног испод:
јава цаст цхар у стринг
- Прво, једноставно изводимо стандардну операцију брисања БСТ-а за брисање 12 елемента. Како је 12 листни чвор, једноставно избришемо чвор из стабла.
Брисање још увек није завршено. Морамо да прикажемо родитељ избрисаног чвора, тј. 10. Морамо да извршимо Сплаи(10) на дрвету. Као што можемо приметити у горњем стаблу да је 10 десно од чвора 7, а чвор 7 лево од чвора 13. Дакле, прво вршимо леву ротацију на чвору 7, а затим вршимо десну ротацију на чвору 13, као што је приказано у наставку:
Ипак, чвор 10 није основни чвор; чвор 10 је лево дете основног чвора. Дакле, треба да извршимо праву ротацију на коренском чвору, тј. 14 да би чвор 10 постао основни чвор као што је приказано у наставку:
- Сада морамо да избришемо елемент 14 из стабла, што је приказано испод:
Као што знамо да не можемо једноставно избрисати унутрашњи чвор. Заменићемо вредност чвора било помоћу инордер претходник или по реду наследник . Претпоставимо да користимо наследник нереда у коме вредност замењујемо најнижом вредношћу која постоји у десном подстаблу. Најнижа вредност у десном подстаблу чвора 14 је 15, па вредност 14 замењујемо са 15. Пошто чвор 14 постаје лисни чвор, можемо га једноставно избрисати као што је приказано испод:
Ипак, брисање није завршено. Морамо да извршимо још једну операцију, то јест, сплаиинг у којој морамо да направимо родитељ избрисаног чвора као основни чвор. Пре брисања, родитељ чвора 14 је био основни чвор, тј. 10, тако да морамо да извршимо било какво ширење у овом случају.
Одозго према доле
У одозго према доле, прво изводимо распршивање на коме треба да се изврши брисање, а затим бришемо чвор из стабла. Када се елемент избрише, извршићемо операцију спајања.
Хајде да разумемо спуштање одозго надоле кроз пример.
Претпоставимо да желимо да избришемо 16 из стабла које је приказано испод:
Корак 1: У одозго према доле, прво изводимо распршивање на чвору 16. Чвор 16 има и родитељ и деда. Чвор 16 је са десне стране свог родитеља и родитељски чвор је такође са десне стране свог родитеља, тако да је ово ситуација заг-заг. У овом случају, прво ћемо извршити леву ротацију на чвору 13, а затим на 14 као што је приказано у наставку:
Чвор 16 још увек није коренски чвор, и он је десно дете коренског чвора, тако да морамо да извршимо леву ротацију на чвору 12 да бисмо направили чвор 16 као коренски чвор.
Када чвор 16 постане основни чвор, избрисаћемо чвор 16 и добићемо два различита стабла, тј. лево подстабло и десно подстабло као што је приказано испод:
Као што знамо да су вредности левог подстабла увек мање од вредности десног подстабла. Корен левог подстабла је 12, а корен десног подстабла је 17. Први корак је проналажење максималног елемента у левом подстаблу. У левом подстаблу, максимални елемент је 15, а затим треба да извршимо операцију развлачења на 15.
Као што можемо приметити у горњем стаблу да елемент 15 има родитеља као и баку и деду. Чвор је десно од свог родитеља, а родитељски чвор је такође десно од свог родитеља, тако да морамо да извршимо две леве ротације да би чвор 15 постао основни чвор као што је приказано испод:
Након извршења две ротације на стаблу, чвор 15 постаје коренски чвор. Као што видимо, десно дете од 15 је НУЛЛ, тако да прилажемо чвор 17 на десни део 15 као што је приказано испод, а ова операција је позната као придружити операција.
Напомена: Ако елемент није присутан у стаблу приказивања, које треба обрисати, тада би се извршило сплаиинг. Пребацивање би се извршило на последњем приступном елементу пре достизања НУЛЛ.
Алгоритам операције брисања
If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root
У горњем алгоритму прво проверавамо да ли је корен Нулл или не; ако је корен НУЛЛ значи да је дрво празно. Ако стабло није празно, извршићемо операцију распростирања на елементу који треба да се обрише. Када се заврши операција приказивања, упоредићемо корен податке са елементом који треба да се обрише; ако оба нису једнака значи да елемент није присутан у стаблу. Ако су једнаки, онда се могу десити следећи случајеви:
Случај 1 : Лево од корена је НУЛЛ, десно од корена постаје коренски чвор.
Случај 2 : Ако постоје и лева и десна, онда приказујемо максимални елемент у левом подстаблу. Када је распршивање завршено, максимални елемент постаје корен левог подстабла. Десно подстабло би постало десно дете корена левог подстабла.