스플레이 트리 데이터 구조 소개 - TECHCODEVIEW.COM

스플레이 트리는 자체 조정 이진 검색 트리 데이터 구조입니다. 즉, 트리 구조는 액세스되거나 삽입된 요소에 따라 동적으로 조정됩니다. 즉, 자주 액세스하거나 삽입되는 요소가 루트 노드에 가까워지도록 트리가 자동으로 재구성됩니다.

스플레이 트리는 1985년 Daniel Dominic Sleator와 Robert Endre Tarjan에 의해 처음 소개되었습니다. 이는 O(log n) 상각 시간 복잡도에서 검색, 삽입 및 삭제 작업을 수행할 수 있는 간단하고 효율적인 구현을 가지고 있습니다. 여기서 n은 트리의 요소 수입니다.
스플레이 트리의 기본 아이디어는 스플레잉(splaying)이라고 하는 일련의 트리 회전을 수행하여 가장 최근에 액세스했거나 삽입된 요소를 트리의 루트로 가져오는 것입니다. 스플레잉(Splaying)은 가장 최근에 액세스하거나 삽입한 요소를 새로운 루트로 만들고 나머지 노드를 점차 루트에 더 가깝게 이동하여 트리를 재구성하는 프로세스입니다.
스플레이 트리는 자주 액세스되는 요소에 대한 전체 액세스 시간을 줄이는 자체 조정 특성으로 인해 실제로 매우 효율적입니다. 따라서 캐싱 시스템, 데이터 압축 및 네트워크 라우팅 알고리즘과 같이 빠르고 동적 데이터 구조가 필요한 애플리케이션에 적합한 선택입니다.
그러나 스플레이 트리의 가장 큰 단점은 균형 잡힌 트리 구조를 보장하지 않아 최악의 경우 성능 저하가 발생할 수 있다는 것입니다. 또한, 스플레이 트리는 실시간 시스템이나 안전이 중요한 시스템과 같이 최악의 성능을 보장해야 하는 애플리케이션에는 적합하지 않습니다.

전반적으로 스플레이 트리는 자주 액세스하거나 삽입되는 요소에 빠르고 효율적으로 액세스할 수 있는 강력하고 다양한 데이터 구조입니다. 이는 다양한 애플리케이션에서 널리 사용되며 성능과 단순성 사이의 탁월한 절충안을 제공합니다.

스플레이 트리는 키 값을 기반으로 데이터 요소에 효율적으로 액세스하도록 설계된 자체 균형 이진 검색 트리입니다.

스플레이 트리의 주요 특징은 요소에 액세스할 때마다 요소가 트리의 루트로 이동하여 후속 액세스를 위해 보다 균형 잡힌 구조를 만든다는 것입니다.
스플레이 트리는 모양은 변경하지만 요소의 순서는 유지하는 트리의 로컬 변형인 회전을 사용하는 것이 특징입니다.
회전은 액세스된 요소를 트리의 루트로 가져오고, 여러 액세스 후 균형이 맞지 않는 경우 트리의 균형을 재조정하는 데 사용됩니다.

플레이 트리에서의 작업:

삽입: 트리에 새 요소를 삽입하려면 일반적인 이진 검색 트리 삽입을 수행하여 시작하세요. 그런 다음 회전을 적용하여 새로 삽입된 요소를 트리의 루트로 가져옵니다.
삭제 : 트리에서 요소를 삭제하려면 먼저 이진 검색 트리 검색을 사용하여 해당 요소를 찾습니다. 그런 다음 요소에 자식이 없으면 간단히 제거하면 됩니다. 자식이 하나 있으면 해당 자식을 트리의 해당 위치로 승격시킵니다. 두 개의 자식이 있는 경우 요소의 후속 요소(오른쪽 하위 트리에서 가장 작은 요소)를 찾고 해당 키를 삭제할 요소와 교환한 다음 대신 후속 요소를 삭제합니다.
찾다 : 트리에서 요소를 검색하려면 이진 검색 트리 검색을 수행하여 시작합니다. 요소가 발견되면 회전을 적용하여 트리의 루트로 가져옵니다. 찾지 못한 경우 검색에서 마지막으로 방문한 노드에 회전을 적용하여 새 루트가 됩니다.
회전 : 스플레이 트리에 사용되는 회전은 Zig 또는 Zig-Zig 회전입니다. Zig 회전은 노드를 루트로 가져오는 데 사용되는 반면, Zig-Zig 회전은 동일한 하위 트리의 요소에 여러 번 액세스한 후 트리 균형을 유지하는 데 사용됩니다.

다음은 회전 작업에 대한 단계별 설명입니다.

지그 회전 : 노드에 오른쪽 자식이 있는 경우 오른쪽 회전을 수행하여 루트로 가져옵니다. 왼쪽 자식이 있으면 왼쪽 회전을 수행합니다.
지그지그 회전: 노드에 자식의 오른쪽 또는 왼쪽 자식이기도 한 손자가 있는 경우 트리 균형을 맞추기 위해 이중 회전을 수행합니다. 예를 들어 노드에 오른쪽 자식이 있고 오른쪽 자식에 왼쪽 자식이 있는 경우 오른쪽-왼쪽 회전을 수행합니다. 노드에 왼쪽 자식이 있고 왼쪽 자식에 오른쪽 자식이 있는 경우 왼쪽-오른쪽 회전을 수행합니다.
메모: 사용된 정확한 회전을 포함한 구체적인 구현 세부 사항은 전개 트리의 정확한 형태에 따라 달라질 수 있습니다.

스플레이 트리의 회전

지그 회전
재그 회전
지그 – 지그 회전
재그 – 재그 회전
지그 – 재그 회전
재그 – 지그 회전

1) 지그 회전:

스플레이 트리의 Zig 회전은 AVL 트리 회전의 단일 오른쪽 회전과 유사한 방식으로 작동합니다. 이 회전으로 인해 노드가 현재 위치에서 오른쪽으로 한 위치 이동하게 됩니다. 예를 들어 다음 시나리오를 고려해보세요.

지그 회전(단일 회전)

2) 재그 회전:

스플레이 트리의 재그 회전은 AVL 트리 회전의 단일 왼쪽 회전과 유사한 방식으로 작동합니다. 이 회전 동안 노드는 현재 위치에서 왼쪽으로 한 위치 이동합니다. 예를 들어, 다음 그림을 고려하십시오.

이 xd는 무슨 뜻인가요?

Zag 회전(단일 왼쪽 회전)

3) 지그지그 회전:

스플레이 트리의 지그지그 회전은 이중 지그 회전입니다. 이 회전으로 인해 노드가 현재 위치에서 오른쪽으로 두 위치 이동하게 됩니다. 더 나은 이해를 위해 다음 예를 살펴보십시오.

vlc로 YouTube 비디오 다운로드

Zig-Zig 회전(이중 우회전)

4) 재그재그 회전:

스플레이 트리에서 재그-재그 회전은 이중 재그 회전입니다. 이 회전으로 인해 노드가 현재 위치에서 왼쪽으로 두 위치 이동하게 됩니다. 예를 들어:

Zag-Zag Rotation (좌측 이중 회전)

5) 지그재그 회전:

스플레이 트리의 지그재그 회전은 지그 회전과 재그 회전의 조합입니다. 이 회전의 결과로 노드는 현재 위치에서 오른쪽으로 한 위치 이동한 다음 왼쪽으로 한 위치 이동합니다. 다음 그림은 이 개념을 시각적으로 보여줍니다.

지그재그 회전

6) 재그-지그 회전:

스플레이 트리의 재그-지그 회전은 일련의 재그 회전과 그에 따른 지그 회전입니다. 결과적으로 노드는 왼쪽으로 한 위치 이동하고, 이어서 현재 위치에서 오른쪽으로 한 위치 이동합니다. 다음 그림은 이 개념을 시각적으로 보여줍니다.

재그지그 회전

다음은 Splay 트리에서 회전을 구현하는 C++ 코드입니다.

C++

 #include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->열쇠 = 열쇠;  노드->왼쪽 = 노드->오른쪽 = nullptr;  반환 노드; } 노드* rightRotate(노드* x) { 노드* y = x->왼쪽;  x->왼쪽 = y->오른쪽;  y->오른쪽 = x;  y를 반환; } 노드* leftRotate(노드* x) { 노드* 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) return root;  if (루트->왼쪽->키> 키) { 루트->왼쪽->왼쪽 = splay(루트->왼쪽->왼쪽, 키);  루트 = rightRotate(루트);  } else if (루트->왼쪽->키< key) {  root->왼쪽->오른쪽 = splay(루트->왼쪽->오른쪽, 키);  if (루트->왼쪽->오른쪽 != nullptr) 루트->왼쪽 = leftRotate(루트->왼쪽);  } return (root->left == nullptr) ? 루트 : rightRotate(루트);  } else { if (root->right == nullptr) return root;  if (루트->오른쪽->키> 키) { 루트->오른쪽->왼쪽 = splay(루트->오른쪽->왼쪽, 키);  if (root->right->left != nullptr) root->right = rightRotate(root->right);  } else if (루트->오른쪽->키< key) {  root->오른쪽->오른쪽 = splay(루트->오른쪽->오른쪽, 키);  루트 = leftRotate(루트);  } return (root->right == nullptr) ? 루트 : leftRotate(루트);  } } Node* insert(Node* root, int key) { if (root == nullptr) return newNode(key);  루트 = splay(루트, 키);  if (루트->키 == 키) return root;  노드* node = newNode(key);  if (루트->키> 키) { 노드->right = 루트;  노드->왼쪽 = 루트->왼쪽;  루트->왼쪽 = nullptr;  } else { 노드->왼쪽 = 루트;  노드->오른쪽 = 루트->오른쪽;  루트->오른쪽 = nullptr;  } 반환 노드; } void preOrder(Node* node) { if (node != nullptr) { cout<< node->열쇠<< ' ';  preOrder(node->왼쪽);  preOrder(노드->오른쪽);  } } int main() { 노드* 루트 = nullptr;  루트 = 삽입(루트, 100);  루트 = 삽입(루트, 50);  루트 = 삽입(루트, 200);  루트 = 삽입(루트, 40);  루트 = 삽입(루트, 60);  시합<< '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) return root;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  루트 = rightRotate(루트);  } 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 = 루트.왼쪽;  루트.왼쪽 = null;  } else { node.left = 루트;  node.right = 루트.right;  root.right = null;  } 반환 노드;  } static void preOrder(노드 노드) { if (노드 != null) { System.out.println();  System.out.print(node.key + ' ');  preOrder(node.left);  preOrder(node.right);  } } public static void main(String[] args) { 노드 루트 = null;  루트 = 삽입(루트, 100);  루트 = 삽입(루트, 50);  루트 = 삽입(루트, 200);  루트 = 삽입(루트, 40);  루트 = 삽입(루트, 60);  System.out.println('수정된 Splay 트리의 선주문 순회:');  사전주문(루트);  } } // 이 코드는 Princekumaras가 제공한 것입니다.>

파이썬3

 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>key: root.left가 None인 경우: root.left.key인 경우 루트를 반환> key: root.left.left = splay(root.left.left, key) 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, key) 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>key: node.right = 루트 node.left = root.left root.left = 없음 else: 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 = 없음 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) return root;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  루트 = rightRotate(루트);  } 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 = 루트.왼쪽;  루트.왼쪽 = null;  } else { node.left = 루트;  node.right = 루트.right;  root.right = null;  } 반환 노드;  } static void preOrder(노드 노드) { if (node != null) { Console.Write(node.key + ' ');  preOrder(node.left);  preOrder(node.right);  } } public static void Main(string[] args) { 노드 루트 = null;  루트 = 삽입(루트, 100);  루트 = 삽입(루트, 50);  루트 = 삽입(루트, 200);  루트 = 삽입(루트, 40);  루트 = 삽입(루트, 60);  Console.WriteLine( '수정된 Splay 트리의 선주문 순회:');  사전주문(루트);  } } // 이 코드는 Prince Kumar가 제공한 것입니다.>

자바스크립트

 // 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>키) { if (root.left == null) { 루트 루트 반환;  } if (root.left.key> key) { root.left.left = SplayTree.splay(root.left.left, key);  루트 = SplayTree.rightRotate(루트);  } 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>key) { root.right.left = SplayTree.splay(root.right.left, key);  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>키) { node.right = 루트;  node.left = 루트.왼쪽;  루트.왼쪽 = null;  } else { node.left = 루트;  node.right = 루트.right;  root.right = null;  } 반환 노드;  } static preOrder(node) { if (node != null) { console.log(node.key + ' ');  SplayTree.preOrder(node.left);  SplayTree.preOrder(node.right);  } } } 루트 = null을 보자; 루트 = SplayTree.insert(루트, 100); 루트 = SplayTree.insert(root, 50); 루트 = SplayTree.insert(루트, 200); 루트 = SplayTree.insert(root, 40); 루트 = SplayTree.insert(root, 60); console.log('수정된 Splay 트리의 선주문 순회:'); SplayTree.preOrder(루트); // 코드는 Nidhi goel이 제공했습니다.>

산출

Preorder traversal of the modified Splay tree:>

전개 트리 데이터 구조의 단점:

불균형한 나무: 나무가 같은 방향으로 반복적으로 회전하면 확산 나무가 불균형하고 비효율적이 될 수 있습니다.
메모리 사용량: 스플레이 트리는 각 노드에 추가 정보가 포함되어 있기 때문에 다른 데이터 구조에 비해 많은 메모리를 사용할 수 있습니다.
복잡성: 스플레이 트리는 매 작업 후에 트리를 재구성해야 하기 때문에 삽입 및 삭제와 같은 기본 작업에 대해 시간 복잡도가 높을 수 있습니다.
재구성 오버헤드: 모든 작업에 필요한 확장 작업은 시간이 많이 걸리고 오버헤드가 높아질 수 있습니다.
제한된 사용 사례 : 스플레이 트리는 모든 데이터 구조에 적합하지 않으며 중복 키를 효율적으로 처리하지 못하기 때문에 사용 사례가 제한됩니다.

전개 나무의 응용:

캐싱 : 스플레이 트리는 캐시 메모리 관리를 구현하는 데 사용할 수 있습니다. 여기서 가장 자주 액세스되는 항목은 더 빠른 액세스를 위해 트리의 맨 위로 이동됩니다.
데이터베이스 인덱싱 : 스플레이 트리를 사용하면 데이터를 더 빠르게 검색하고 검색할 수 있도록 데이터베이스를 색인화할 수 있습니다.
파일 시스템 : 스플레이 트리는 할당 테이블, 디렉터리 구조, 파일 속성과 같은 파일 시스템 메타데이터를 저장하는 데 사용할 수 있습니다.
데이터 압축: 반복되는 패턴을 식별하고 인코딩하여 데이터를 압축하는 데 스플레이 트리를 사용할 수 있습니다.
텍스트 처리 : 스플레이 트리는 빠른 검색을 위해 단어가 스플레이 트리에 저장되는 맞춤법 검사기와 같은 텍스트 처리 응용 프로그램에서 사용할 수 있습니다.
그래프 알고리즘: 스플레이 트리는 가중치 그래프에서 최단 경로를 찾는 등의 그래프 알고리즘을 구현하는 데 사용할 수 있습니다.
온라인 게임: 스플레이 트리는 온라인 게임에서 최고 점수, 순위표, 플레이어 통계를 저장하고 관리하는 데 사용할 수 있습니다.

물론, 다음은 스플레이 트리의 장점과 단점, 그리고 해당 주제에 대해 더 자세히 알아볼 수 있는 권장 도서입니다.

리틱 로샨 나이

스플레이 트리의 장점:

스플레이 트리는 많은 작업에 대해 O(log n)의 상각 시간 복잡도를 가지므로 어떤 경우에는 다른 균형 트리 데이터 구조보다 더 빠릅니다.
스플레이 트리는 자체 조정됩니다. 즉, 항목을 삽입하고 제거할 때 자동으로 균형을 유지합니다. 이는 트리의 균형이 맞지 않을 때 발생할 수 있는 성능 저하를 방지하는 데 도움이 될 수 있습니다.

스플레이 트리의 단점:

스플레이 트리는 일부 작업에 대해 O(n)의 최악의 시간 복잡도를 가질 수 있으므로 AVL 트리 또는 레드-블랙 트리와 같은 다른 균형 트리 데이터 구조보다 예측하기 어렵습니다.
스플레이 트리는 예측 가능한 성능이 필요한 특정 애플리케이션에는 적합하지 않을 수 있습니다.

Splay Trees에 관한 추천 도서:

Mark Allen Weiss의 Java 데이터 구조 및 알고리즘 분석
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest 및 Clifford Stein의 알고리즘 소개
C++의 데이터 구조 및 알고리즘 - Michael T. Goodrich 및 Roberto Tamassia

결론:

결론적으로 스플레이 트리는 요소를 검색, 삽입 및 삭제하는 효율적인 방법을 제공하는 동적 자체 균형 이진 검색 트리 데이터 구조입니다. AVL 및 Red-Black 트리와 같은 전통적인 균형 이진 검색 트리와는 다릅니다. 각 작업 후에 트리를 재구성하여 최근에 액세스한 노드를 루트로 가져옵니다. 이는 트리의 높이를 줄이는 데 도움이 되며 작업 속도가 빨라집니다. Splay Tree는 매우 유연하며 다양한 사용 사례에 맞게 조정할 수 있습니다. 회전 측면에서 오버헤드가 높을 수 있지만 단순성과 다양성으로 인해 광범위한 문제를 해결하는 데 유용한 도구가 됩니다.