Дерево Splay — це саморегулююча структура даних бінарного дерева пошуку, що означає, що структура дерева динамічно налаштовується на основі доступних або вставлених елементів. Іншими словами, дерево автоматично реорганізовується так, що елементи, до яких часто звертаються або вставляють, стають ближчими до кореневого вузла.

1. Дерево розведення було вперше представлено Деніелом Домініком Сліатором і Робертом Ендре Тар’яном у 1985 році. Воно має просту та ефективну реалізацію, що дозволяє виконувати операції пошуку, вставки та видалення з амортизованою часовою складністю O(log n), де n — кількість елементів у дереві.
2. Основна ідея розкривних дерев полягає в тому, щоб перенести останній доступ або вставлений елемент до кореня дерева шляхом виконання послідовності поворотів дерева, що називається розведенням. Розгортання — це процес реструктуризації дерева шляхом перетворення елемента, до якого нещодавно було доступно або вставлено, новим коренем і поступового переміщення решти вузлів ближче до кореня.
3. Спільні дерева дуже ефективні на практиці завдяки своїй природі саморегулювання, що зменшує загальний час доступу для часто використовуваних елементів. Це робить їх хорошим вибором для програм, які вимагають швидких і динамічних структур даних, таких як системи кешування, стиснення даних і алгоритми мережевої маршрутизації.
4. Однак основним недоліком розкривних дерев є те, що вони не гарантують збалансовану структуру дерева, що може призвести до погіршення продуктивності в найгіршому випадку. Крім того, розсунуті дерева не підходять для додатків, які вимагають гарантованої продуктивності в найгіршому випадку, таких як системи реального часу або критичні для безпеки системи.

Загалом, розсунуті дерева є потужною та універсальною структурою даних, яка пропонує швидкий та ефективний доступ до часто використовуваних або вставлених елементів. Вони широко використовуються в різних програмах і забезпечують чудовий компроміс між продуктивністю та простотою.

Дерево розрізу — це самобалансуюче бінарне дерево пошуку, призначене для ефективного доступу до елементів даних на основі їхніх ключових значень.

• Ключовою особливістю дерева розсувів є те, що кожен раз, коли здійснюється доступ до елемента, він переміщується до кореня дерева, створюючи більш збалансовану структуру для наступних звернень.
• Дерева розкосів характеризуються використанням обертань, які є локальними перетвореннями дерева, які змінюють його форму, але зберігають порядок елементів.
• Обертання використовується для переведення елемента, до якого здійснюється доступ, до кореня дерева, а також для відновлення балансу дерева, якщо воно стає незбалансованим після кількох звернень.

Операції в дереві розгинання:

• Вставка: Щоб вставити новий елемент у дерево, почніть із виконання звичайної вставки двійкового дерева пошуку. Потім застосуйте обертання, щоб перенести щойно вставлений елемент до кореня дерева.
• Видалення : Щоб видалити елемент із дерева, спершу знайдіть його за допомогою пошуку у бінарному дереві пошуку. Тоді, якщо елемент не має дітей, просто видаліть його. Якщо у нього є один дочірній елемент, підвищте його до його місця в дереві. Якщо він має двох дочірніх елементів, знайдіть наступника елемента (найменший елемент у його правому піддереві), поміняйте його ключ з елементом, який потрібно видалити, і замість цього видаліть наступника.
• Пошук : щоб шукати елемент у дереві, почніть із виконання бінарного пошуку в дереві. Якщо елемент знайдено, застосуйте обертання, щоб привести його до кореня дерева. Якщо його не знайдено, застосовуйте обертання до останнього вузла, відвіданого під час пошуку, який стає новим коренем.
• Обертання : Обертання, що використовуються в дереві розкосу, є обертанням Зіг або Зіг-Зіг. Обертання Zig використовується, щоб привести вузол до кореня, тоді як обертання Zig-Zig використовується для збалансування дерева після кількох звернень до елементів у тому самому піддереві.

Ось покрокове пояснення операцій обертання:

• Зіг ротація : якщо вузол має правий дочірній елемент, виконайте поворот праворуч, щоб привести його до кореня. Якщо він має лівого дочірнього елемента, виконайте поворот ліворуч.
• Обертання Зіг-Зіг: Якщо вузол має онука, який також є правим або лівим дочірнім елементом його дочірнього елемента, виконайте подвійне обертання, щоб збалансувати дерево. Наприклад, якщо вузол має правий дочірній елемент, а правий дочірній елемент має лівого дочірнього вузла, виконайте обертання вправо-вліво. Якщо вузол має лівого дочірнього елемента, а лівий дочірній елемент має правого дочірнього вузла, виконайте обертання ліворуч-праворуч.
• Примітка: Конкретні деталі реалізації, включно з точними обертаннями, які використовуються, можуть відрізнятися залежно від точної форми розкривного дерева.

Обертання в Splay Tree

• Зіг ротація
• Загоподібне обертання
• Zig – обертання Zig
• Zag – обертання Zag
• Обертання зиг-заг
• Zag – обертання Zig

1) Обертання Zig:

Обертання Zig у деревах зі зсувом працює подібно до одиночного обертання вправо в обертаннях дерева AVL. Це обертання призводить до того, що вузли переміщуються на одну позицію вправо від свого поточного розташування. Наприклад, розглянемо такий сценарій:

Обертання Zig (один оберт)

2) Обертання Zag:

Обертання Zag у деревах розкосу працює подібно до одиничного обертання вліво в обертаннях дерева AVL. Під час цього обертання вузли зміщуються на одну позицію вліво від свого поточного розташування. Наприклад, розглянемо таку ілюстрацію:

абстрактний клас проти інтерфейсу

Zag Rotation (один поворот ліворуч)

3) Обертання Зіг-Зіг:

Обертання «зиг-зиг» у розкосих деревах — це подвійне обертання «зиг». Це обертання призводить до того, що вузли зміщуються на дві позиції вправо від свого поточного розташування. Подивіться на наступний приклад для кращого розуміння:

Обертання зиг-зиг (подвійне обертання вправо)

4) Заг-заг обертання:

У розкосих деревах обертання Zag-Zag є подвійним zag обертанням. Це обертання змушує вузли переміщатися на дві позиції вліво від їх поточної позиції. Наприклад:

arraylist у сортуванні java

Заг-заг обертання (подвійне обертання ліворуч)

5) Зигзагоподібне обертання:

Зигзагоподібне обертання у розкосих деревах — це комбінація зиґзаґоподібного обертання з наступним заґаподібним обертанням. У результаті цього обертання вузли зміщуються на одну позицію вправо, а потім на одну позицію вліво від свого поточного розташування. На наступній ілюстрації наочно показано цю концепцію:

Зигзагоподібне обертання

6) Заг-зиг обертання:

Обертання Zag-Zig у розкосих деревах — це серія обертань Zag, за якою слід обертання Zig. Це призводить до переміщення вузлів на одну позицію вліво, а потім на одну позицію вправо від їх поточного розташування. Наступна ілюстрація пропонує візуальне представлення цієї концепції:

Заг-зиг обертання

Нижче наведено код C++ для реалізації поворотів у дереві Splay:

метод tostring у java

#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->ключ = ключ;  node->left = node->right = nullptr;  зворотний вузол; } Node* rightRotate(Node* x) { Node* y = x->left;  x->ліворуч = y->праворуч;  y->праворуч = x;  повернення y; } Node* leftRotate(Node* x) { Node* y = x->right;  x->праворуч = y->ліворуч;  y->ліворуч = x;  повернення y; } Node* splay(Node* root, int key) { if (root == nullptr || root->key == key) return root;  if (root->key> key) { if (root->left == nullptr) повертає root;  if (root->left->key> key) { root->left->left = splay(root->left->left, key);  root = rightRotate(root);  } else if (root->left->key< key) {  root->ліворуч->праворуч = splay(корінь->ліворуч->праворуч, клавіша);  if (root->left->right != nullptr) root->left = leftRotate(root->left);  } return (root->left == nullptr) ? корінь : rightRotate(корінь);  } else { if (root->right == nullptr) повертає корінь;  if (root->right->key> key) { root->right->left = splay(root->right->left, key);  if (root->right->left != nullptr) root->right = rightRotate(root->right);  } else if (root->right->key< key) {  root->right->right = splay(root->right->right, key);  root = leftRotate(root);  } return (root->right == nullptr) ? корінь : leftRotate(корінь);  } } Node* insert(Node* root, int key) { if (root == nullptr) return newNode(key);  root = splay(корінь, ключ);  if (root->key == key) повернути корінь;  Node* node = newNode(ключ);  if (root->key> key) { node->right = root;  node->left = корінь->left;  root->left = nullptr;  } else { node->left = корінь;  node->right = root->right;  root->right = nullptr;  } повернення вузла; } void preOrder(Node* node) { if (node ​​!= nullptr) { cout<< node->ключ<< ' ';  preOrder(node->ліворуч);  preOrder(node->right);  } } int main() { Node* root = nullptr;  корінь = вставка (корінь, 100);  корінь = вставка (корінь, 50);  корінь = вставити (корінь, 200);  корінь = вставка (корінь, 40);  корінь = вставити (корінь, 60);  cout<< 'Preorder traversal of the modified Splay tree:' << endl;  preOrder(root);  return 0; }>

// Java Program for the above approach class Node {  public int key;  public Node left, right; } class SplayTree {  static Node newNode(int key) {  Node node = new Node();  node.key = key;  node.left = node.right = null;  return node;  }  static Node rightRotate(Node x) {  Node y = x.left;  x.left = y.right;  y.right = x;  return y;  }  static Node leftRotate(Node x) {  Node y = x.right;  x.right = y.left;  y.left = x;  return y;  }  static Node splay(Node root, int key) {  if (root == null || root.key == key)  return root;  if (root.key>ключ) { if (root.left == null) повертає корінь;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  root = rightRotate(root);  } else if (root.left.key< key) {  root.left.right = splay(root.left.right, key);  if (root.left.right != null)  root.left = leftRotate(root.left);  }  return (root.left == null) ? root : rightRotate(root);  }  else {  if (root.right == null)  return root;  if (root.right.key>ключ) { root.right.left = splay(root.right.left, ключ);  if (root.right.left != null) root.right = rightRotate(root.right);  } else if (root.right.key< key) {  root.right.right = splay(root.right.right, key);  root = leftRotate(root);  }  return (root.right == null) ? root : leftRotate(root);  }  }  static Node insert(Node root, int key) {  if (root == null)  return newNode(key);  root = splay(root, key);  if (root.key == key)  return root;  Node node = newNode(key);  if (root.key>ключ) { node.right = корінь;  node.left = root.left;  root.left = null;  } else { node.left = корінь;  node.right = root.right;  root.right = null;  } повернення вузла;  } static void preOrder(Node node) { if (node ​​!= null) { System.out.println();  System.out.print(node.key + ' ');  preOrder(node.left);  preOrder(node.right);  } } public static void main(String[] args) { Node root = null;  корінь = вставка (корінь, 100);  корінь = вставка (корінь, 50);  корінь = вставити (корінь, 200);  корінь = вставка (корінь, 40);  корінь = вставка (корінь, 60);  System.out.println('Попередній обхід модифікованого дерева Splay:');  preOrder(корінь);  } } // Цей код надано princekumaras>

class Node: def __init__(self, key): self.key = key self.left = None self.right = None def new_node(key): return Node(key) def right_rotate(x): y = x.left x.left = y.right y.right = x return y def left_rotate(x): y = x.right x.right = y.left y.left = x return y def splay(root, key): if root is None : return new_node(key) if root.key == key: return root if root.key>ключ: якщо root.left має значення None: повертає root, якщо root.left.key> ключ: root.left.left = splay(root.left.left, ключ) root = right_rotate(root) elif root.left.key< key: root.left.right = splay(root.left.right, key) if root.left.right: root.left = left_rotate(root.left) return root.left if root.left is None else right_rotate(root) else: if root.right is None: return root if root.right.key>ключ: root.right.left = splay(root.right.left, ключ) якщо root.right.left: root.right = right_rotate(root.right) elif root.right.key< key: root.right.right = splay(root.right.right, key) root = left_rotate(root) return root.right if root.right is None else left_rotate(root) def insert(root, key): if root is None: return new_node(key) root = splay(root, key) if root.key == key: return root node = new_node(key) if root.key>ключ: node.right = корінь node.left = root.left root.left = Ніщо інше: node.left = корінь node.right = root.right root.right = Немає return node def pre_order(node): if node: print (node.key, end=' ') pre_order(node.left) pre_order(node.right) if __name__ == '__main__': root = None root = insert(root, 100) root = insert(root , 50) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('Попередній порядок проходження модифікованого дерева Splay:') pre_order(root)>

// C# program for the above approach using System; class Node {  public int key;  public Node left, right; } class SplayTree {  static Node newNode(int key)  {  Node node = new Node();  node.key = key;  node.left = node.right = null;  return node;  }  static Node rightRotate(Node x)  {  Node y = x.left;  x.left = y.right;  y.right = x;  return y;  }  static Node leftRotate(Node x)  {  Node y = x.right;  x.right = y.left;  y.left = x;  return y;  }  static Node splay(Node root, int key)  {  if (root == null || root.key == key)  return root;  if (root.key>ключ) { if (root.left == null) повертає корінь;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  root = rightRotate(root);  } else if (root.left.key< key) {  root.left.right  = splay(root.left.right, key);  if (root.left.right != null)  root.left = leftRotate(root.left);  }  return (root.left == null) ? root  : rightRotate(root);  }  else {  if (root.right == null)  return root;  if (root.right.key>ключ) { root.right.left = splay(root.right.left, ключ);  if (root.right.left != null) root.right = rightRotate(root.right);  } else if (root.right.key< key) {  root.right.right  = splay(root.right.right, key);  root = leftRotate(root);  }  return (root.right == null) ? root  : leftRotate(root);  }  }  static Node insert(Node root, int key)  {  if (root == null)  return newNode(key);  root = splay(root, key);  if (root.key == key)  return root;  Node node = newNode(key);  if (root.key>ключ) { node.right = корінь;  node.left = root.left;  root.left = null;  } else { node.left = корінь;  node.right = root.right;  root.right = null;  } повернення вузла;  } static void preOrder(Node node) { if (node ​​!= null) { Console.Write(node.key + ' ');  preOrder(node.left);  preOrder(node.right);  } } public static void Main(string[] args) { Node root = null;  корінь = вставка (корінь, 100);  корінь = вставка (корінь, 50);  корінь = вставити (корінь, 200);  корінь = вставка (корінь, 40);  корінь = вставка (корінь, 60);  Console.WriteLine( 'Попередній обхід модифікованого дерева Splay:');  preOrder(корінь);  } } // Цей код надав принц Кумар>>>Javascript

Preorder traversal of the modified Splay tree:>

Недоліки структури даних дерева розкосу:

• Незбалансовані дерева: Скошені дерева можуть стати незбалансованими та неефективними, якщо дерево неодноразово повертати в одному напрямку.
• Використання пам'яті: Дерева Splay можуть використовувати багато пам’яті порівняно з іншими структурами даних, оскільки кожен вузол містить додаткову інформацію.
• Складність: Дерева розведення можуть мати високу складність у часі для основних операцій, таких як вставка та видалення, оскільки дерева потрібно реорганізовувати після кожної операції.
• Накладні витрати на реорганізацію: Операція розведення, необхідна для кожної операції, може зайняти багато часу та призвести до великих накладних витрат.
• Випадки обмеженого використання : Дерева Splay не підходять для всіх структур даних і мають обмежені випадки використання, оскільки вони неефективно обробляють дублікати ключів.

Застосування розкосного дерева:

• Кешування : Дерева Splay можна використовувати для реалізації керування кеш-пам’яттю, де елементи, до яких найчастіше звертаються, переміщуються у верхню частину дерева для швидшого доступу.
• Індексація бази даних : Дерева Splay можна використовувати для індексування баз даних для швидшого пошуку та отримання даних.
• Файлові системи : Дерева Splay можна використовувати для зберігання метаданих файлової системи, таких як таблиця розподілу, структура каталогів і атрибути файлів.
• Стиснення даних: Дерева Splay можна використовувати для стиснення даних шляхом ідентифікації та кодування повторюваних шаблонів.
• Обробка тексту : Дерева розведення можна використовувати в програмах для обробки тексту, таких як перевірка орфографії, де слова зберігаються в дереві розведення для швидкого пошуку та отримання.
• Алгоритми графів: Дерева Splay можна використовувати для реалізації алгоритмів графів, таких як пошук найкоротшого шляху у зваженому графі.
• Ігри онлайн: Дерева Splay можна використовувати в онлайн-іграх для зберігання та керування рекордами, таблицями лідерів і статистикою гравців.

Звичайно, ось деякі переваги та недоліки розкосих дерев, а також деякі рекомендовані книги, щоб дізнатися більше про цю тему:

Переваги сплеєвих дерев:

Дерева Splay мають амортизовану часову складність O(log n) для багатьох операцій, що робить їх у деяких випадках швидшими, ніж багато інших збалансованих структур даних дерева.
Розкидні дерева саморегулюються, тобто вони автоматично балансують, коли елементи вставляються та видаляються. Це може допомогти уникнути зниження продуктивності, яке може статися, коли дерево стає незбалансованим.

Недоліки сплавних дерев:

Дерева Splay можуть мати найгіршу часову складність O(n) для деяких операцій, що робить їх менш передбачуваними, ніж інші збалансовані структури даних дерева, такі як дерева AVL або червоно-чорні дерева.
Дерева Splay можуть не підходити для певних програм, де потрібна передбачувана продуктивність.

Рекомендовані книги про Splay Trees:

Структури даних і аналіз алгоритмів у Java, Марк Аллен Вайс
Вступ до алгоритмів Томаса Х. Кормена, Чарльза Е. Лейзерсона, Рональда Л. Ріввеста та Кліффорда Стайна
Структури даних і алгоритми в C++ Майкл Т. Гудріч і Роберто Тамасія

Висновок:

Підсумовуючи, Splay Trees — це динамічна структура даних бінарного дерева пошуку, яка забезпечує ефективний спосіб пошуку, вставки та видалення елементів. Вони відрізняються від традиційних збалансованих бінарних дерев пошуку, таких як дерева AVL і Red-Black, оскільки вони реорганізовують дерево після кожної операції, щоб перевести нещодавно доступний вузол до кореня. Це допомагає зменшити висоту дерева та прискорює роботу. Splay Trees є дуже гнучкими і можуть бути адаптовані до різних випадків використання. Хоча вони можуть мати вищі накладні витрати з точки зору ротацій, їх простота та універсальність роблять їх корисними інструментами для вирішення широкого кола проблем.