Splay Tree - 1

작성일 | In

Splay Tree란?

이번 글은 균형 이진 탐색 트리(Balanced Binary Search Tree, BBST) 중 splay tree라는 자료 구조에 대한 설명입니다.
가장 자주 쓰이는 BBST는 레드 블랙 트리(Red-Black tree, RB Tree)이지만, 구현이 너무 복잡합니다.
그러나 이번에 소개할 splay tree는 구현이 쉽고 레드 블랙 트리에 버금가는 속도를 갖고 있기 때문에 STL을 못 쓰는 환경에서 유용하게 쓸 수 있습니다.

레드 블랙 트리는 삽입/검색/삭제 모두 O(log n)이고, 스플레이 트리는 amortized O(log n)입니다.

Node구조체

먼저 트리의 노드를 의미하는 구조체를 만듭시다.

1
2
3
4
5
6
struct node{
  node* l; //왼쪽 자식 노드
  node* r; //오른쪽 자식 노드
  node* p; //부모 노드
  int key; //key값
};

rotate

splay tree는 두 가지의 연산을 이용해 작동합니다.
먼저, rotate라는 함수는 특정 노드를 자신의 부모 위치로 옮기는 기능을 수행합니다.


그림 1


그림 2

rotate 함수를 만들어봅시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void rotate(node* x){ //x : 위로 올릴 노드
  node* p = x->p; //p : x의 부모 노드
  node* b = NULL; //그림 1, 2의 b 노드
  if(!p) return; //x가 루트 노드라면 종료
  if(x == p->l){ //x가 왼쪽 자식이라면
    p->l = b = x->r; //x의 오른쪽 자식이 p의 새로운 왼쪽 자식
    x->r = p; //p를 x의 자식으로 이동
  }else{ //x가 오른쪽 자식이라면
    p->r = b = x->l; //x의 왼쪽 자식이 p의 새로운 오른쪽 자식
    x->l = p; //p를 x의 자식으로 이동
  }
  //부모 재설정
  x->p = p->p;
  p->p = x;
  if(b) b->p = p;
  (x->p ? p==x->p->l ? x->p->l : x->p->r : tree) = x;
}

splay

다음으로, splay라는 함수는 특정 노드를 루트 노드 위치로 옮기는 기능을 수행합니다. 작동 과정은 다음과 같습니다.

  1. x가 루트라면, 종료한다.
  2. x의 부모 p가 루트라면 rotate(x)를 수행하고 종료한다. (Zig Step)
  3. x의 조부모를 g라고 하면, 다음 두 가지 중 하나를 수행한다.
  4. g-p방향과 p-x방향이 같다면 rotate(p)와 rotate(x)를 차례대로 수행한다. (Zig-Zig Step)
  5. 방향이 다른 경우 rotate(x)를 두 번 수행한다. (Zig-Zag Step)
  6. 1로 돌아가서 x가 루트가 될 때까지 반복한다.
1
2
3
4
5
6
7
8
9
10
11
void splay(node* x){ //x : 루트로 올릴 노드
  while(x->p){ //x가 루트가 될 때까지
    node* p = x->p;
    node* g = p->p;
    if(g){
      if((x==p->l) == (p==g->l)) rotate(p); //Zig-Zig Step
      else rotate(x); //Zig-Zag Step
    }
    rotate(x); //Zig Step
  }
}

다음 글에서는 insert, find, delete와 같은 이진 탐색 트리(Binary Search Tree, BST)의 기본 연산을 splay tree에서 구현해보도록 하겠습니다.