Drzewo Splay to samodostosowująca się struktura danych drzewa wyszukiwania binarnego, co oznacza, że ​​struktura drzewa jest dostosowywana dynamicznie w oparciu o dostępne lub wstawiane elementy. Innymi słowy, drzewo automatycznie reorganizuje się tak, że często używane lub wstawiane elementy znajdują się bliżej węzła głównego.

1. Drzewo splay zostało po raz pierwszy wprowadzone przez Daniela Dominica Sleatora i Roberta Endre Tarjana w 1985 roku. Ma prostą i wydajną implementację, która pozwala na wykonywanie operacji wyszukiwania, wstawiania i usuwania w złożoności czasu amortyzowanego O(log n), gdzie n jest liczba elementów w drzewie.
2. Podstawową ideą drzew splay jest przeniesienie ostatnio używanego lub wstawianego elementu do korzenia drzewa poprzez wykonanie sekwencji rotacji drzewa, zwanej splayingiem. Rozkładanie to proces restrukturyzacji drzewa poprzez uczynienie ostatnio używanego lub wstawianego elementu nowym korzeniem i stopniowe przesuwanie pozostałych węzłów bliżej korzenia.
3. Drzewa rozpryskowe są bardzo wydajne w praktyce ze względu na ich samodopasowujący się charakter, co skraca całkowity czas dostępu do często dostępnych elementów. To sprawia, że ​​są dobrym wyborem do zastosowań wymagających szybkich i dynamicznych struktur danych, takich jak systemy buforowania, kompresja danych i algorytmy routingu sieciowego.
4. Jednak główną wadą drzew rozłożystych jest to, że nie gwarantują one zrównoważonej struktury drzewa, co w najgorszych scenariuszach może prowadzić do pogorszenia wydajności. Ponadto drzewa rozsiane nie nadają się do zastosowań wymagających gwarantowanej wydajności w najgorszym przypadku, takich jak systemy czasu rzeczywistego lub systemy o krytycznym znaczeniu dla bezpieczeństwa.

Ogólnie rzecz biorąc, drzewa rozstawione to potężna i wszechstronna struktura danych, która zapewnia szybki i wydajny dostęp do często używanych lub wstawianych elementów. Są szeroko stosowane w różnych zastosowaniach i zapewniają doskonały kompromis między wydajnością a prostotą.

Drzewo splay to samobalansujące się drzewo wyszukiwania binarnego, zaprojektowane z myślą o wydajnym dostępie do elementów danych w oparciu o ich kluczowe wartości.

• Kluczową cechą drzewa rozłożonego jest to, że za każdym razem, gdy uzyskiwany jest dostęp do elementu, jest on przenoszony do korzenia drzewa, tworząc bardziej zrównoważoną strukturę dla kolejnych dostępów.
• Drzewa rozłożyste charakteryzują się wykorzystaniem rotacji, czyli lokalnych przekształceń drzewa, które zmieniają jego kształt, zachowując jednak porządek elementów.
• Obroty służą do doprowadzenia dostępnego elementu do korzenia drzewa, a także do przywrócenia równowagi drzewa, jeśli utraci ono równowagę po wielokrotnych dostępach.

Operacje na drzewie rozłożonym:

• Wprowadzenie: Aby wstawić nowy element do drzewa, zacznij od zwykłego wstawienia drzewa wyszukiwania binarnego. Następnie zastosuj rotacje, aby nowo wstawiony element znalazł się w korzeniu drzewa.
• Usunięcie : Aby usunąć element z drzewa, najpierw zlokalizuj go za pomocą wyszukiwania binarnego w drzewie. Następnie, jeśli element nie ma dzieci, po prostu go usuń. Jeśli ma jedno dziecko, wypromuj je na jego miejsce w drzewie. Jeśli ma dwójkę dzieci, znajdź następcę elementu (najmniejszy element w jego prawym poddrzewie), zamień jego klucz z elementem, który ma zostać usunięty, i zamiast tego usuń następcę.
• Szukaj : Aby wyszukać element w drzewie, rozpocznij od przeprowadzenia wyszukiwania binarnego w drzewie. Jeśli element zostanie znaleziony, zastosuj rotacje, aby doprowadzić go do korzenia drzewa. Jeśli nie zostanie znaleziony, zastosuj rotacje do ostatniego węzła odwiedzonego podczas wyszukiwania, który stanie się nowym korzeniem.
• Obrót : Obroty używane w drzewie rozłożonym to obrót Zig lub Zig-Zig. Rotacja Zig służy do doprowadzenia węzła do korzenia, natomiast rotacja Zig-Zig służy do zrównoważenia drzewa po wielokrotnych dostępach do elementów w tym samym poddrzewie.

Oto szczegółowe wyjaśnienie operacji rotacji:

• Obrót Zig : Jeśli węzeł ma prawe dziecko, wykonaj obrót w prawo, aby doprowadzić go do korzenia. Jeśli ma lewe dziecko, wykonaj obrót w lewo.
• Rotacja Zig-Zig: Jeśli węzeł ma wnuka, który jest jednocześnie prawym lub lewym dzieckiem jego dziecka, wykonaj podwójny obrót, aby zrównoważyć drzewo. Na przykład, jeśli węzeł ma prawe dziecko, a prawe dziecko ma lewe dziecko, wykonaj obrót w prawo-lewo. Jeśli węzeł ma lewe dziecko, a lewe dziecko ma prawe dziecko, wykonaj obrót w lewo-prawo.
• Notatka: Konkretne szczegóły implementacji, w tym dokładne zastosowane rotacje, mogą się różnić w zależności od dokładnej formy drzewa rozkładu.

Obroty w drzewie rozłożenia

• Obrót Zig
• Obrót Zag
• Zig – obrót Zig
• Zag – obrót Zag
• Zig – obrót Zag
• Zag – obrót Zig

1) Rotacja Zig:

Obrót Zig w drzewach rozłożonych działa w sposób podobny do obrotu w pojedynczą prawą stronę w obrotach drzewa AVL. Ten obrót powoduje, że węzły przesuwają się o jedną pozycję w prawo od ich bieżącej lokalizacji. Rozważmy na przykład następujący scenariusz:

Rotacja Zig (pojedynczy obrót)

2) Obrót Zag:

Rotacja Zag w drzewach rozłożonych działa w podobny sposób jak obrót w lewo w obrotach drzewa AVL. Podczas tego obrotu węzły przesuwają się o jedną pozycję w lewo od swojej bieżącej lokalizacji. Rozważmy na przykład poniższą ilustrację:

klasa abstrakcyjna a interfejs

Obrót Zag (obrót w lewo)

3) Rotacja Zig-Zig:

Rotacja Zig-Zig w drzewach rozłożystych jest podwójną rotacją zig. Obrót ten powoduje przesunięcie węzłów o dwie pozycje w prawo od ich aktualnej lokalizacji. Aby lepiej zrozumieć, spójrz na następujący przykład:

Obrót Zig-Zig (podwójny obrót w prawo)

4) Rotacja Zag-Zag:

W drzewach rozłożystych rotacja Zag-Zag jest podwójną rotacją zag. Ten obrót powoduje, że węzły przesuwają się o dwie pozycje w lewo od ich aktualnej pozycji. Na przykład:

Obrót Zag-Zag (podwójny obrót w lewo)

posortuj listę tablic w Javie

5) Rotacja zygzakowata:

Rotacja zygzakowata w drzewach rozłożystych jest kombinacją rotacji zygzakowatej, po której następuje rotacja zag. W wyniku tego obrotu węzły przesuwają się o jedną pozycję w prawo, a następnie o jedną pozycję w lewo od ich aktualnej lokalizacji. Poniższa ilustracja przedstawia wizualną reprezentację tej koncepcji:

Rotacja Zig-Zag

6) Rotacja Zag-Zig:

Rotacja Zag-Zig w drzewach rozłożystych to seria obrotów zag, po których następuje rotacja zygzakowata. Powoduje to przesunięcie węzłów o jedną pozycję w lewo, a następnie o jedną pozycję w prawo w stosunku do ich bieżącej lokalizacji. Poniższa ilustracja przedstawia wizualną reprezentację tej koncepcji:

Rotacja Zag-Zig

Poniżej znajduje się kod C++ implementujący rotacje w drzewie Splay:

#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->klucz = klucz;  węzeł->lewy = węzeł->prawy = nullptr;  węzeł zwrotny; } Węzeł*rightRotate(Węzeł* x) { Węzeł* y = x->lewo;  x->lewo = y->prawo;  y->prawo = x;  zwróć y; } Węzeł* leftRotate(Węzeł* x) { Węzeł* y = x->prawy;  x->prawo = y->lewo;  y->lewo = x;  zwróć y; } Węzeł* splay(Węzeł* root, int klucz) { if (root == nullptr || root->key == klucz) return root;  if (root->key> key) { if (root->left == nullptr) return root;  if (root->lewy->klawisz> klawisz) { root->lewy->lewy = splay(root->lewy->lewy, klawisz);  root = RightRotate(root);  } else if (root->lewy->klawisz< key) {  root->lewy->prawy = splay(root->lewy->prawy, klawisz);  if (root->left->right != nullptr) root->left = leftRotate(root->left);  } return (root->left == nullptr) ? root:rightRotate(root);  } else { if (root->right == nullptr) return root;  if (root->prawy->klawisz> klucz) { root->prawy->lewy = splay(root->prawy->lewy, klawisz);  if (root->right->left != nullptr) root->right = RightRotate(root->right);  } else if (root->prawy->key< key) {  root->prawo->prawo = spplay(root->prawo->prawo, klawisz);  root = leftRotate(root);  } return (root->right == nullptr) ? root: leftRotate(root);  } } Węzeł* wstaw(Węzeł* root, int klucz) { if (root == nullptr) return newNode(key);  root = spplay(root, klucz);  if (root->key == klucz) zwróć root;  Węzeł* węzeł = nowyWęzeł(klucz);  if (root->key> key) { węzeł->right = root;  węzeł->lewy = korzeń->lewy;  root->lewy = nullptr;  } else { węzeł->lewy = korzeń;  węzeł->prawo = korzeń->prawo;  root->right = nullptr;  } węzeł zwrotny; } void preOrder(Węzeł* węzeł) { if (węzeł != nullptr) { cout<< node->klucz<< ' ';  preOrder(node->lewy);  preOrder(węzeł->prawo);  } } int main() { Węzeł* root = nullptr;  root = wstaw(korzeń, 100);  root = wstaw(korzeń, 50);  root = wstaw(korzeń, 200);  root = wstaw(korzeń, 40);  root = wstaw(korzeń, 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>klucz) { if (root.left == null) return root;  if (root.left.key> klucz) { 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>klawisz) { root.right.left = spplay(root.right.left, klawisz);  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>klucz) { węzeł.right = root;  węzeł.lewy = root.lewy;  root.left = null;  } else { węzeł.left = korzeń;  węzeł.prawo = root.prawo;  root.right = null;  } węzeł zwrotny;  } static void preOrder(Węzeł węzła) { if (węzeł != null) { System.out.println();  System.out.print(node.key + ' ');  zamówienie wstępne (węzeł. lewy);  zamówienie wstępne(węzeł.prawy);  } } public static void main(String[] args) { Korzeń węzła = null;  root = wstaw(korzeń, 100);  root = wstaw(korzeń, 50);  root = wstaw(korzeń, 200);  root = wstaw(korzeń, 40);  root = wstaw(korzeń, 60);  System.out.println('Przechodzenie przez zmodyfikowane drzewo Splay w przedsprzedaży:');  zamówienie w przedsprzedaży(root);  } } // Ten kod został napisany przez 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>klucz: jeśli root.left to None: zwróć root, jeśli root.left.key> klucz: root.left.left = splay(root.left.left, klucz) 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>klucz: root.right.left = splay(root.right.left, klucz) if 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>klucz: node.right = root node.left = root.left root.left = Brak innych: node.left = root node.right = root.right root.right = Brak return node def pre_order(node): if węzeł: print (node.key, end=' ') pre_order(node.left) pre_order(node.right) if __name__ == '__main__': root = Brak root = wstaw(root, 100) root = wstaw(root , 50) root = wstawka(root, 200) root = wstawka(root, 40) root = wstawka(root, 60) print('Przechodzenie zmodyfikowanego drzewa Splay w przedsprzedaży:') 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>klucz) { if (root.left == null) return root;  if (root.left.key> klucz) { 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>klawisz) { root.right.left = spplay(root.right.left, klawisz);  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>klucz) { węzeł.right = root;  węzeł.lewy = root.lewy;  root.left = null;  } else { węzeł.left = korzeń;  węzeł.prawo = root.prawo;  root.right = null;  } węzeł zwrotny;  } static void preOrder(węzeł węzła) { if (węzeł != null) { Console.Write(node.key + ' ');  zamówienie wstępne (węzeł. lewy);  zamówienie wstępne(węzeł.prawy);  } } public static void Main(string[] args) { Korzeń węzła = null;  root = wstaw(korzeń, 100);  root = wstaw(korzeń, 50);  root = wstaw(korzeń, 200);  root = wstaw(korzeń, 40);  root = wstaw(korzeń, 60);  Console.WriteLine( 'Przechodzenie przez zmodyfikowane drzewo Splay w przedsprzedaży:');  zamówienie w przedsprzedaży(root);  } } // Ten kod został napisany przez księcia Kumara>

// Javascript code addition  class Node {  constructor(key) {  this.key = key;  this.left = null;  this.right = null;  } } class SplayTree {  static newNode(key) {  const node = new Node(key);  return node;  }  static rightRotate(x) {  const y = x.left;  x.left = y.right;  y.right = x;  return y;  }  static leftRotate(x) {  const y = x.right;  x.right = y.left;  y.left = x;  return y;  }  static splay(root, key) {  if (root == null || root.key == key) {  return root;  }  if (root.key>klucz) { if (root.left == null) { return root;  } if (root.left.key> klucz) { root.left.left = SplayTree.splay(root.left.left, key);  root = SplayTree.rightRotate(root);  } else if (root.left.key< key) {  root.left.right = SplayTree.splay(root.left.right, key);  if (root.left.right != null) {  root.left = SplayTree.leftRotate(root.left);  }  }  return root.left == null ? root : SplayTree.rightRotate(root);  } else {  if (root.right == null) {  return root;  }  if (root.right.key>klucz) { root.right.left = SplayTree.splay(root.right.left, klucz);  if (root.right.left != null) { root.right = SplayTree.rightRotate(root.right);  } } else if (root.right.key< key) {  root.right.right = SplayTree.splay(root.right.right, key);  root = SplayTree.leftRotate(root);  }  return root.right == null ? root : SplayTree.leftRotate(root);  }  }  static insert(root, key) {  if (root == null) {  return SplayTree.newNode(key);  }  root = SplayTree.splay(root, key);  if (root.key == key) {  return root;  }  const node = SplayTree.newNode(key);  if (root.key>klucz) { węzeł.right = root;  węzeł.lewy = root.lewy;  root.left = null;  } else { węzeł.left = korzeń;  węzeł.prawo = root.prawo;  root.right = null;  } węzeł zwrotny;  } static preOrder(węzeł) { if (węzeł != null) { console.log(node.key + ' ');  SplayTree.preOrder(węzeł.lewy);  SplayTree.preOrder(węzeł.prawy);  } } } niech root = null; root = SplayTree.insert(root, 100); root = SplayTree.insert(root, 50); root = SplayTree.insert(root, 200); root = SplayTree.insert(root, 40); root = SplayTree.insert(root, 60); console.log('Przechodzenie przez zmodyfikowane drzewo Splay w przedsprzedaży:'); SplayTree.preOrder(root); // Kod został napisany przez Nidhi goela.>

Preorder traversal of the modified Splay tree:>

Wady struktury danych drzewa rozgałęzionego:

• Niezrównoważone drzewa: Rozłożyste drzewa mogą stać się niezrównoważone i nieefektywne, jeśli będą wielokrotnie obracane w tym samym kierunku.
• Zużycie pamięci: Drzewa rozpostarte mogą zużywać dużo pamięci w porównaniu z innymi strukturami danych, ponieważ każdy węzeł zawiera dodatkowe informacje.
• Złożoność: Drzewa rozłożone mogą wymagać dużej złożoności czasowej w przypadku podstawowych operacji, takich jak wstawianie i usuwanie, ponieważ drzewa wymagają reorganizacji po każdej operacji.
• Koszty reorganizacji: Operacja rozkładania wymagana w każdej operacji może być czasochłonna i powodować duże koszty ogólne.
• Ograniczone przypadki użycia : Drzewa rozproszone nie są odpowiednie dla wszystkich struktur danych i mają ograniczone zastosowania, ponieważ nie obsługują efektywnie duplikatów kluczy.

Zastosowania drzewa rozpryskowego:

• Buforowanie : Rozwinięte drzewa mogą służyć do zarządzania pamięcią podręczną, gdzie najczęściej używane elementy są przenoszone na górę drzewa, aby zapewnić szybszy dostęp.
• Indeksowanie baz danych : Drzewa splay mogą być używane do indeksowania baz danych w celu szybszego wyszukiwania i odzyskiwania danych.
• Systemy plików : Drzewa rozłożone mogą służyć do przechowywania metadanych systemu plików, takich jak tabela alokacji, struktura katalogów i atrybuty plików.
• Kompresja danych: Drzewa rozłożone mogą służyć do kompresji danych poprzez identyfikację i kodowanie powtarzających się wzorców.
• Przetwarzanie tekstu : Drzewa powiększone mogą być używane w aplikacjach do przetwarzania tekstu, takich jak moduły sprawdzania pisowni, gdzie słowa są przechowywane w drzewie powiększonym w celu szybkiego wyszukiwania i odzyskiwania.
• Algorytmy wykresów: Drzewa rozłożone mogą służyć do implementowania algorytmów grafowych, takich jak znajdowanie najkrótszej ścieżki na wykresie ważonym.
• Gry internetowe: Drzewa splay mogą być używane w grach online do przechowywania i zarządzania najlepszymi wynikami, rankingami i statystykami graczy.

Oczywiście, oto kilka zalet i wad drzewek rozłożystych, a także kilka polecanych książek, aby dowiedzieć się więcej na ten temat:

Zalety drzewek splatających:

Drzewa Splay mają amortyzowaną złożoność czasową O (log n) dla wielu operacji, co czyni je szybszymi niż wiele innych zrównoważonych struktur danych drzewiastych w niektórych przypadkach.
Drzewa uchylne są samoregulujące, co oznacza, że ​​automatycznie równoważą się podczas wkładania i wyjmowania przedmiotów. Może to pomóc uniknąć pogorszenia wydajności, które może wystąpić, gdy drzewo staje się niezrównoważone.

Wady drzew rozłożystych:

Drzewa rozłożone mogą mieć złożoność czasową O(n) w najgorszym przypadku dla niektórych operacji, co czyni je mniej przewidywalnymi niż inne zrównoważone struktury danych drzew, takie jak drzewa AVL lub drzewa czerwono-czarne.
Drzewa rozłożyste mogą nie nadawać się do niektórych zastosowań, w których wymagana jest przewidywalna wydajność.

jak zdobyć emoji z iPhone'a na Androida

Polecane książki na temat Splay Trees:

Struktury danych i analiza algorytmów w Javie autorstwa Marka Allena Weissa
Wprowadzenie do algorytmów autorstwa Thomasa H. Cormena, Charlesa E. Leisersona, Ronalda L. Rivesta i Clifforda Steina
Struktury danych i algorytmy w C++ autorstwa Michaela T. Goodricha i Roberto Tamassii

Wniosek:

Podsumowując, drzewa Splay to dynamiczna, samobalansująca struktura danych drzewa wyszukiwania binarnego, która zapewnia efektywny sposób wyszukiwania, wstawiania i usuwania elementów. Różnią się od tradycyjnych zrównoważonych drzew wyszukiwania binarnego, takich jak drzewa AVL i czerwono-czarne, ponieważ reorganizują drzewo po każdej operacji, aby przenieść ostatnio używany węzeł do katalogu głównego. Pomaga to zmniejszyć wysokość drzewa i skutkuje szybszymi operacjami. Drzewa Splay są bardzo elastyczne i można je dostosować do różnych zastosowań. Chociaż mogą mieć większy narzut w zakresie rotacji, ich prostota i wszechstronność czynią je użytecznymi narzędziami do rozwiązywania szerokiego zakresu problemów.