Splay-дерева — це самобалансуючі або самонастроювані бінарні дерева пошуку. Іншими словами, ми можемо сказати, що розкладені дерева є варіантами бінарних дерев пошуку. Необхідна умова для дерев розведення, яку ми повинні знати про дерева бінарного пошуку.
Як ми вже знаємо, часова складність бінарного дерева пошуку в кожному випадку. Часова складність бінарного дерева пошуку в середньому становить O (вхід) а часова складність у гіршому випадку становить O(n). У бінарному дереві пошуку значення лівого піддерева менше кореневого вузла, а значення правого піддерева більше кореневого вузла; у такому випадку часова складність буде O (вхід) . Якщо бінарне дерево має перекіс вліво або вправо, то часова складність буде O(n). Щоб обмежити перекос, AVL і червоно-чорне дерево увійшов у картину, маючи O(log ) часова складність для всіх операцій у всіх випадках. Ми також можемо покращити цю часову складність, зробивши більше практичних реалізацій, тому нове Дерево Що таке Splay Tree?
Розкошене дерево є самобалансуючим деревом, але Тоді дерева AVL і Red-Black також є самобалансуючими деревами. Що робить розкосне дерево унікальним? Два дерева. Він має одну додаткову властивість, яка робить його унікальним, це розкидання.
Дерево розширення містить ті самі операції, що й a Двійкове дерево пошуку , тобто вставлення, видалення та пошук, але він також містить ще одну операцію, тобто розгортання. Так. усі операції в дереві розведення супроводжуються розведенням.
Дерева розкосів не є строго збалансованими, але приблизно збалансованими. Давайте розберемося з операцією пошуку в splay-дереві.
Припустімо, ми хочемо знайти 7 елемент у дереві, яке показано нижче:
Для пошуку будь-якого елемента в дереві розширення, спочатку ми виконаємо стандартну операцію бінарного пошуку дерева. Оскільки 7 менше за 10, ми підійдемо зліва від кореневого вузла. Після виконання операції пошуку нам потрібно виконати розведення. Тут розгортання означає, що операція, яку ми виконуємо над будь-яким елементом, повинна стати кореневим вузлом після виконання деяких перегрупувань. Перестановку дерева здійснюватимуть за допомогою чергування.
Примітка. Дерево розриву можна визначити як саморегульоване дерево, у якому будь-яка операція, виконана над елементом, переставляє дерево таким чином, що елемент, над яким була виконана операція, стає кореневим вузлом дерева.
Ротації
Існує шість типів поворотів, які використовуються для розведення:
- Обертання Zig (обертання вправо)
- Загоподібне обертання (обертання вліво)
- Зиг заг (за зигом йде заг)
- Zag zig (Заг, за яким йде зіг)
- Zig zig (два повороти вправо)
- Zag zag (два повороти вліво)
Фактори, необхідні для вибору типу ротації
Для вибору типу ротації використовуються такі фактори:
- Чи має вузол, який ми намагаємось повернути, дідуся чи бабусю?
- Вузол є лівим чи правим дочірнім вузлом батьківського?
- Вузол лівий чи правий дочірній елемент бабусі та дідуся?
Кейси для ротацій
Випадок 1: Якщо вузол не має діда-батька, і якщо це правий дочірній елемент батька, то виконуємо лівий поворот; інакше виконується правильний поворот.
Випадок 2: Якщо вузол має бабусю та дідуся, то на основі наступних сценаріїв; обертання буде виконано:
Сценарій 1: Якщо вузол є правим за батьківським, а батьківський також є правим за своїм батьківським, тоді зіг зіг вправо вправо обертання виконується.
Сценарій 2: Якщо вузол розташований ліворуч від батьківського елемента, але батьківський вузол знаходиться праворуч від свого батьківського елемента, тоді зигзагоподібне обертання вправо вліво виконується.
Сценарій 3: Якщо вузол знаходиться праворуч від батьківського, а батьківський — праворуч від свого батьківського, тоді zig zig ліворуч ліворуч обертання виконується.
Сценарій 4: Якщо вузол знаходиться праворуч від батьківського елемента, але батьківський вузол знаходиться ліворуч від свого батьківського елемента, тоді зигзагоподібне обертання вправо-вліво виконується.
Тепер давайте розберемо наведені вище обертання на прикладах.
Щоб переставити дерево, нам потрібно виконати кілька обертів. Нижче наведено типи поворотів у дереві розкосів:
Зіг-обертання використовується, коли шуканий елемент є або кореневим вузлом, або дочірнім вузлом кореневого вузла (тобто лівим чи правим дочірнім).
Нижче наведено випадки, які можуть існувати в дереві розведення під час пошуку:
Випадок 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 кореневим вузлом за допомогою деяких поворотів. У цьому випадку ми не можемо просто виконати зіг або заг; ми маємо реалізувати обертання zig zig.
Для того, щоб зробити вузол 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 знаходиться праворуч від кореневого вузла, тому ми будемо виконувати обертання вліво, відоме як обертання загону. Вузол 10 переміститься вниз, а 13 стане кореневим вузлом, як показано нижче:
Як ми можемо помітити у наведеному вище дереві, вузол 13 став кореневим вузлом; отже, пошук завершено. У цьому випадку ми спочатку виконали обертання зіг, а потім поворот; тому це відоме як зигзагоподібне обертання.
Розберемося в цьому випадку на прикладі.
Припустімо, ми хочемо знайти 9 елемент у дереві, яке показано нижче:
Крок 1: Спочатку ми виконуємо стандартну операцію пошуку BST. Оскільки 9 менше за 10, але більше за 7, це буде правильний дочірній елемент вузла 7.
Крок 2: Оскільки вузол 9 знаходиться праворуч від вузла 7, а вузол 7 – ліворуч від вузла 10, тож зв’язок LR існує. Спочатку ми виконуємо обертання вліво на вузлі 7. Вузол 7 рухатиметься вниз, а вузол 9 рухається вгору, як показано нижче:
Все ж вузол 9 не є кореневим вузлом, а 9 знаходиться ліворуч від кореневого вузла, тому ми будемо виконувати обертання вправо, відоме як зіг-обертання. Після виконання правильного обертання вузол 9 стає кореневим вузлом, як показано нижче:
Як ми можемо помітити у наведеному вище дереві, вузол 13 є кореневим вузлом; отже, пошук завершено. У цьому випадку ми спочатку виконали загоподібне обертання (обертання вліво), а потім виконується зигоподібне обертання (обертання вправо), тому воно називається загоподібним обертанням.
Переваги дерева 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
Як ми знаємо, що розведені дерева є варіантами бінарного дерева пошуку, тому операція видалення в розведеному дереві буде подібна до BST, але єдина відмінність полягає в тому, що за операцією видалення в розведених деревах слідує операція розведення.
Типи видалень:
Існує два типи видалень у деревах розведення:
- Розкидання знизу вгору
- Розкидання зверху вниз
Розкидання знизу вгору
У розширенні знизу вгору спочатку ми видаляємо елемент із дерева, а потім виконуємо розведення на видаленому вузлі.
Давайте розберемося з видаленням у дереві Splay.
Припустимо, ми хочемо видалити 12, 14 з дерева, показаного нижче:
обрізка рядка javascript
- Спочатку ми просто виконуємо стандартну операцію видалення 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 : якщо існують і ліворуч, і праворуч, ми розводимо максимальний елемент у лівому піддереві. Коли розкладання завершено, максимальний елемент стає коренем лівого піддерева. Праве піддерево стане правим дочірнім елементом кореня лівого піддерева.