Splay Tree (1) - rotate, splay

안녕하세요.

오늘은 Splay Tree에 대해 알아보겠습니다.

 

이번 글에서는 기본 연산인 rotate와 splay에 대해 알아보겠습니다.

---

AVL Tree

스플레이 트리는 자가 균형 이진 트리에 속합니다.

https://ko.wikipedia.org/wiki/AVL_%ED%8A%B8%EB%A6%AC

AVL 트리 - 위키백과, 우리 모두의 백과사전

 

일반 이진 탐색 트리의 경우 한쪽으로 노드가 쏠리는 skewed tree가 나타날 수 있습니다.

https://www.geeksforgeeks.org/convert-a-binary-search-tree-into-a-skewed-tree-in-increasing-or-decreasing-order/

이렇게 되면 insert, delete 또는 find 연산이 O(N) 만큼 걸린다는 단점이 있습니다.

 

하지만 splay tree는 이런 case를 없애 위의 연산을 빠르게 수행합니다.

 

이진 트리의 특성을 가짐

이진 트리의 특성을 가지기에 아래 2가지를 만족합니다.

• 자식이 2개 (leftChild, rightChild)
• 어떤 노드를 기준으로 아래 조건을 만족함
  • 왼쪽 서브트리는 자신보다 작은 노드들
  • 오른쪽 서브트리는 자신보다 큰 노드들

struct Node {
	Node* left;
	Node* right;
	Node* parent;
	ll key;

	Node(ll k) {
		key = k;
		left = right = parent = NULL;
	}

	bool isLeft() { return parent->left == this; }
	bool isRoot() { return !parent; }

	void rotate() {
		...
	}
};

---

Splay Tree 만의 특징

최근에 접근한 노드가 루트로 올라오는 특징이 있습니다.

가장 최근에 접근했던 노드일수록 빠르게 탐색이 가능합니다.

 

그래서 cache나 텍스트 자동 완성 등에 사용된다고 합니다.

 

시간 복잡도

amortized O(log N)

 

이전에 유니온 파인드 포스팅을 하면서 amortized에 대해 간단히 다룬 적이 있습니다.

 

스플레이 트리는 어떤 순간에는 skewed tree가 될 수도 있습니다.

 

하지만 루트로 올라오는 특징으로, N번 연산을 했을 때 시간적 비용을 더하면 N * logN에 가까워집니다.

이를 N으로 나눈 평균 연산은 logN이 되므로 위의 시간 복잡도가 나옵니다.

---

Rotate

특정 node를 부모 위치로 올리는 연산입니다.

node가 오른쪽, 왼쪽 자식일 때 각각 rotate한 모습입니다.

struct Node {
	...

	void rotate() {
		if (isRoot()) return;
		Node* p = parent;

		if (isLeft()) {
			p->left = right;
			if (right) right->parent = p;

			right = p;
		}
		else {
			p->right = left;
			if (left) left->parent = p;

			left = p;
		}

		if(!p->isRoot()) 
			(p->isLeft() ? p->parent->left : p->parent->right) = this;

		parent = p->parent;
		p->parent = this;
	}
};

---

Splay

node x를 root로 만들어주는 연산 입니다.

 

스플레이 연산은 아래 case에 따라 다르게 연산을 수행합니다.

아래 연산을 node x가 root가 될 때까지 반복해주면 됩니다.

 

Case 1. Zig

노드 x의 부모가 루트일 때 입니다.

(p(x) is the root)

 

=> rotate(x) 수행합니다.

 

Case 2. Zig-Zig

노드 x의 부모가 루트가 아니고

노드 x와 부모 노드가 전부 같은 방향의 children 일 때 입니다.

( p(x) is not root &

x and p(x) are both left or both right children )

 

=> rotate(p) 이 후, rotate(x)를 수행합니다.

 

Case 3. Zig-Zag

노드 x의 부모가 루트가 아니고

노드 x와 부모 노드가 다른 방향의 children 일 때 입니다.

( p(x) is not root &

x is a left child and p(x) is a right child, or vice-versa )

 

=> rotate(x) 이 후, rotate(x)를 수행합니다.

struct SplayTree {
	Node* root;

	void splay(Node* x) {
		while (!x->isRoot()) {
			Node* p = x->parent;
			if (!p->isRoot()) {
				if (p->isLeft() == x->isLeft()) p->rotate();
				else x->rotate();
			}

			x->rotate();
		}

		root = x;
	}
};

---

참고 자료

https://www.youtube.com/watch?v=Sf0-5pjSgyQ 

https://brilliant.org/wiki/splay-tree/

Splay Tree | Brilliant Math & Science Wiki

https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf

 

https://cubelover.tistory.com/10

Splay Tree