Splay дърветата са самобалансиращи се или самонастройващи се двоични дървета за търсене. С други думи, можем да кажем, че разпръснатите дървета са вариантите на двоичните дървета за търсене. Предпоставката за разпръснатите дървета, която трябва да знаем за двоичните дървета за търсене.

Както вече знаем, времевата сложност на дървото за двоично търсене във всеки случай. Времевата сложност на дървото за двоично търсене в средния случай е O(вход) и времевата сложност в най-лошия случай е O(n). В дърво за двоично търсене стойността на лявото поддърво е по-малка от коренния възел, а стойността на дясното поддърво е по-голяма от коренния възел; в такъв случай времевата сложност би била O(вход) . Ако двоичното дърво е изкривено наляво или надясно, тогава времевата сложност ще бъде O(n). За да се ограничи изкривяването, на AVL и червено-черно дърво влезе в картината, като O(вход ) времева сложност за всички операции във всички случаи. Можем също така да подобрим тази времева сложност, като правим повече практически реализации, така че новото дърво Какво е Splay Tree?

Разклоненото дърво е самобалансиращо се дърво, но Тогава AVL и червено-черните дървета също са самобалансиращи се дървета. Това, което прави дървото на разклоненията уникално, две дървета. Той има едно допълнително свойство, което го прави уникален, а именно разпръскването.

Разкривеното дърво съдържа същите операции като a Двоично дърво за търсене , т.е. вмъкване, изтриване и търсене, но също така съдържа още една операция, т.е. разпръскване. Така. всички операции в splay дървото са последвани от splaying.

Наклонените дървета не са строго балансирани дървета, но са приблизително балансирани дървета. Нека разберем операцията за търсене в splay-дървото.

Да предположим, че искаме да търсим 7 елемент в дървото, което е показано по-долу:

За да търсим който и да е елемент в splay дървото, първо ще извършим стандартната двоична операция за търсене в дървото. Тъй като 7 е по-малко от 10, ще стигнем отляво на основния възел. След като извършим операцията по търсене, трябва да извършим разпръскване. Тук разпръскването означава, че операцията, която извършваме върху който и да е елемент, трябва да се превърне в основен възел след извършване на някои пренареждания. Пренареждането на дървото ще става чрез ротациите.

Забележка: Разкривеното дърво може да се дефинира като самонастройващо се дърво, в което всяка операция, извършена върху елемента, би пренаредила дървото, така че елементът, върху който е извършена операцията, да стане основният възел на дървото.

Ротации

Има шест вида завъртания, използвани за разгъване:

1. Zig въртене (надясно въртене)
2. Zag въртене (ляво въртене)
3. Зиг заг (зиг, последван от заг)
4. Заг зиг (заг последван от зиг)
5. Зиг зиг (две завъртания надясно)
6. Zag zag (две леви завъртания)

Необходими фактори за избор на тип ротация

Следните са факторите, използвани за избор на тип ротация:

• Възелът, който се опитваме да завъртим, има ли баба и дядо?
• Ляв или десен дъщерен възел на родителя ли е?
• Възелът ляво или дясно дете на баба и дядо ли е?

Калъфи за Ротациите

Случай 1: Ако възелът няма дядо-родител и ако е дясно дете на родителя, тогава извършваме ляво завъртане; в противен случай се извършва правилното завъртане.

Случай 2: Ако възелът има баба и дядо, тогава въз основа на следните сценарии; ротацията ще се извърши:

Сценарий 1: Ако възелът е отдясно на родителя и родителят също е отдясно на своя родител, тогава зиг зиг надясно надясно въртене се извършва.

Сценарий 2: Ако възелът е отляво на родител, но родителят е отдясно на своя родител, тогава зиг заг дясно ляво въртене се извършва.

Сценарий 3: Ако възелът е вдясно от родителя и родителят е вдясно от своя родител, тогава зиг зиг ляво ляво въртене се извършва.

Сценарий 4: Ако възелът е отдясно на родител, но родителят е отляво на своя родител, тогава зиг заг дясно-ляво въртене се извършва.

Сега нека разберем горните ротации с примери.

За да пренаредим дървото, трябва да извършим някои завъртания. По-долу са типовете завъртания в дървото на изкривяване:

Зиг завъртания

Цик ротациите се използват, когато елементът, който трябва да се търси, е или основен възел, или дете на коренен възел (т.е. ляво или дясно дете).

Следните са случаите, които могат да съществуват в дървото на splay по време на търсене:

Случай 1: Ако търсеният елемент е основен възел на дървото.

Случай 2: Ако елементът за търсене е дете на основния възел, тогава двата сценария ще бъдат там:

1. Ако детето е ляво дете, ще се извърши дясно завъртане, известно като зиг дясно завъртане.
2. Ако детето е дясно дете, ще се извърши ляво завъртане, известно като зиг ляво завъртане.

Нека разгледаме горните два сценария чрез пример.

Разгледайте примера по-долу:

В горния пример трябва да търсим 7 елемента в дървото. Ще следваме стъпките по-долу:

Етап 1: Първо сравняваме 7 с коренен възел. Тъй като 7 е по-малко от 10, това е ляво дете на коренния възел.

Стъпка 2: След като елементът бъде намерен, ще извършим разпръскване. Правилното завъртане се извършва така, че 7 да се превърне в коренния възел на дървото, както е показано по-долу:

Нека разгледаме друг пример.

В горния пример трябва да търсим 20 елемента в дървото. Ще следваме стъпките по-долу:

Етап 1: Първо сравняваме 20 с коренен възел. Тъй като 20 е по-голямо от коренния възел, то е дясно дете на коренния възел.

Стъпка 2: След като елементът бъде намерен, ще извършим разпръскване. Лявото завъртане се извършва така, че 20 елемент да стане основният възел на дървото.

Зиг зиг ротации

Понякога възниква ситуация, когато обектът, който трябва да се търси, има родител, както и баба и дядо. В този случай трябва да извършим четири завъртания за разгъване.

Нека разберем този случай чрез пример.

Да предположим, че трябва да търсим 1 елемент в дървото, което е показано по-долу:

Етап 1: Първо, трябва да извършим стандартна BST операция за търсене, за да търсим 1 елемент. Тъй като 1 е по-малко от 10 и 7, то ще бъде вляво от възела 7. Следователно елемент 1 има родител, т.е. 7, както и баба и дядо, т.е. 10.

Стъпка 2: В тази стъпка трябва да извършим разгъване. Трябва да направим възел 1 като основен възел с помощта на някои ротации. В този случай не можем просто да извършим зиг или заг ротация; трябва да приложим зиг зиг ротация.

За да направим възел 1 като основен възел, трябва да извършим две десни завъртания, известни като зиг зиг завъртания. Когато извършим правилното завъртане, тогава 10 ще се премести надолу, а възел 7 ще дойде нагоре, както е показано на фигурата по-долу:

Отново ще извършим зигообразно завъртане надясно, възел 7 ще се движи надолу, а възел 1 ще се издигне нагоре, както е показано по-долу:

Както виждаме на фигурата по-горе, възел 1 е станал основният възел на дървото; следователно търсенето е завършено.

Да предположим, че искаме да търсим 20 в дървото по-долу.

За да търсим 20, трябва да извършим две завъртания наляво. Следват стъпките, необходими за търсене на 20 възела:

Етап 1: Първо, извършваме стандартната операция за търсене на BST. Тъй като 20 е по-голямо от 10 и 15, то ще бъде отдясно на възел 15.

Стъпка 2: Втората стъпка е да се извърши разпръскване. В този случай ще бъдат извършени две леви завъртания. При първото завъртане възел 10 ще се премести надолу, а възел 15 ще се премести нагоре, както е показано по-долу:

При второто ляво завъртане, възел 15 ще се премести надолу, а възел 20 става основният възел на дървото, както е показано по-долу:

Както забелязахме, че се извършват две леви завъртания; така че е известно като зиг зиг ляво въртене.

Зиг заг ротации

Досега сме чели, че и родителят, и бабата и дядото са в RR или LL връзка. Сега ще видим връзката RL или LR между родителя и бабата и дядото.

Нека разберем този случай чрез пример.

Да предположим, че искаме да търсим 13 елемента в дървото, което е показано по-долу:

Етап 1: Първо извършваме стандартна операция за търсене на BST. Тъй като 13 е по-голямо от 10, но по-малко от 15, така че възел 13 ще бъде ляво дете на възел 15.

Стъпка 2: Тъй като възел 13 е отляво на 15, а възел 15 е отдясно на възел 10, така че съществува RL връзка. Първо извършваме правилното завъртане на възел 15 и 15 ще се премести надолу, а възел 13 ще се издигне нагоре, както е показано по-долу:

Все пак възел 13 не е основният възел, а 13 е отдясно на основния възел, така че ще извършим ляво завъртане, известно като zag завъртане. Възелът 10 ще се премести надолу, а 13 става основният възел, както е показано по-долу:

Както можем да наблюдаваме в горното дърво, че възел 13 е станал основен възел; следователно търсенето е завършено. В този случай първо сме изпълнили зигзавъртане и след това завъртане; така че е известно като зиг заг ротация.

Зиг завъртане

Нека разберем този случай чрез пример.

Да предположим, че искаме да търсим 9 елемент в дървото, което е показано по-долу:

Етап 1: Първо, извършваме стандартната операция за търсене на BST. Тъй като 9 е по-малко от 10, но по-голямо от 7, така че ще бъде правилното дете на възел 7.

Стъпка 2: Тъй като възел 9 е отдясно на възел 7, а възел 7 е отляво на възел 10, така че съществува връзка LR. Първо извършваме ляво завъртане на възел 7. Възел 7 ще се движи надолу, а възел 9 се движи нагоре, както е показано по-долу:

Все пак възел 9 не е основен възел, а 9 е отляво на основния възел, така че ще извършим дясното завъртане, известно като зиг ротация. След извършване на правилното завъртане, възел 9 става основен възел, както е показано по-долу:

Както можем да видим в горното дърво, че възел 13 е основен възел; следователно търсенето е завършено. В този случай първо сме извършили завъртане на заг (завъртане наляво), а след това се извършва завъртане на зиг (въртене надясно), така че е известно като завъртане на зиг.

Предимства на дървото Splay

• В splay дървото не е необходимо да съхраняваме допълнителна информация. Обратно, в дърветата AVL трябва да съхраним коефициента на баланс на всеки възел, който изисква допълнително пространство, а червено-черните дървета също изискват да съхраним един допълнителен бит информация, който обозначава цвета на възела, червен или черен.
• Това е най-бързият тип дърво за двоично търсене за различни практически приложения. Използва се в Windows NT и GCC компилатори .
• Той осигурява по-добра производителност, тъй като често достъпните възли ще се приближат до основния възел, поради което елементите могат да бъдат достъпни бързо в разпръснати дървета. Използва се при реализацията на кеша, тъй като наскоро достъпните данни се съхраняват в кеша, така че не е необходимо да отиваме в паметта за достъп до данните и отнема по-малко време.

Недостатък на дървото Splay

Основният недостатък на разклоненото дърво би бил, че дърветата не са строго балансирани, т.е. те са приблизително балансирани. Понякога разклонените дървета са линейни, така че ще отнеме O(n) времева сложност.

Операция за вмъкване в Splay дърво

В вмъкване първо вмъкваме елемента в дървото и след това изпълняваме операцията за разпръскване върху вмъкнатия елемент.

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) 

В горния алгоритъм T е дървото, а n е възелът, който искаме да вмъкнем. Създадохме временна променлива, която съдържа адреса на основния възел. Ще изпълняваме цикъла while, докато стойността на temp стане NULL.

След като вмъкването приключи, ще се извърши разгъване

Алгоритъм за операция Разпръскване

 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 

В горната реализация x е възелът, върху който се извършва ротацията, докато y е лявото дете на възела x.

Внедряване на left.rotation(T, x)

 left.rotation(T, x) y=x->right x->right = y->left y->left = x return y 

В горната реализация x е възелът, върху който се извършва ротацията, а y е дясното дете на възела x.

Изтриване в Splay дърво

Както знаем, че splay дърветата са вариантите на двоичното дърво за търсене, така че операцията по изтриване в splay дървото би била подобна на BST, но единствената разлика е, че операцията за изтриване е последвана в splay дърветата от операцията за разпръскване.

Видове изтривания:

Има два вида заличавания в разпръснатите дървета:

1. Разпръскване отдолу нагоре
2. Разпръскване отгоре надолу

Разпръскване отдолу нагоре

При разпръскване отдолу нагоре първо изтриваме елемента от дървото и след това извършваме разпръскването върху изтрития възел.

Нека разберем изтриването в дървото на Splay.

Да предположим, че искаме да изтрием 12, 14 от дървото, показано по-долу:

прочетете excel файл в java

• Първо, ние просто изпълняваме стандартната операция за изтриване на BST, за да изтрием 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 е NULL, така че прикачваме възел 17 в дясната част на 15, както е показано по-долу, и тази операция е известна като присъединяване операция.

Забележка: Ако елементът не присъства в дървото на разпръскване, което трябва да бъде изтрито, тогава ще се извърши разпръскване. Разпръскването ще се извърши върху последния осъществен достъп преди достигане на NULL.

Алгоритъм на операция Изтриване

 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 

В горния алгоритъм първо проверяваме дали коренът е Null или не; ако коренът е NULL означава, че дървото е празно. Ако дървото не е празно, ще извършим операцията за разпръскване върху елемента, който трябва да бъде изтрит. След като операцията по разпръскване приключи, ще сравним основните данни с елемента, който трябва да бъде изтрит; ако и двете не са равни означава, че елементът не присъства в дървото. Ако те са равни, тогава могат да възникнат следните случаи:

Случай 1 : Лявото на корена е NULL, дясното на корена става основен възел.

Случай 2 : Ако съществуват и ляво, и дясно, тогава разпръскваме максималния елемент в лявото поддърво. Когато разпръскването приключи, максималният елемент става корен на лявото поддърво. Дясното поддърво ще стане дясно дете на корена на лявото поддърво.