Splay Tree - 2

작성일 | In

지난 글에서는 splay tree의 기본이 되는 두 가지 연산(rotate, splay)을 알아보았습니다.
이번 글에서는 splay tree에서 삽입/삭제/검색 연산이 어떻게 이루어 지는지 알아보도록 하겠습니다.

insert

삽입 함수를 만들어봅시다.
작동 방식은 일반적인 이진 탐색 트리의 삽입 방식과 같습니다만, 마지막에 삽입한 노드를 splay해줍니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void insert(int key){
  node* p = tree;
  node** pp; //넣을 위치
  if(!p){ //빈 트리인 경우
    node* x = new node;
    tree = x;
    x->l = x->r = x->p = NULL;
    x->key = key; return;
  }
  while(1){ //삽입할 위치 탐색
    if(key == p->key) return; //중복
    if(key < p->key){ //현재 노드보다 작으면 왼쪽에 삽입
      if(!p->l){ //왼쪽이 비어있으면 삽입
        pp = &p->l; break;
      }
      p = p->l; //비어있지 않다면 왼쪽 서브 트리에서 다시 탐색
    }
    else{ //현재 노드보다 크다면 오른쪽에 삽입
      if(!p->r){
        pp = &p->r; break;
      }
      p = p->r;
    }
  }
  //삽입할 노드 정보 설정
  node* x = new node;
  * pp = x;
  x->l = x->r = NULL;
  x->p = p, x->key = key;
  //splay
  splay(x);
}

find

find함수를 구현해봅시다.
find함수도 일반적인 이진 탐색 트리와 방식은 같고, 마지막에 검색한 노드를 splay해주어서 다른 부가적인 연산을 쉽게 할 수 있게 해줍니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool find(int key){
  node* p = tree;
  if(!p) return false; //빈 트리
  while(p){ //탐색
    if(key == p->key) break; //탐색 성공
    if(key < p->key){ //현재 노드보다 더 작으면 왼쪽 서브 트리에서 다시 탐색
      if(!p->l) break; //탐색 실패
      p = p->l;
    }
    else{ //현재 노드보다 더 크면 오른쪽 서브 트리에서 다시 탐색
      if(!p->r) break; //탐색 실패
      p = p->r;
    }
  }
  splay(p); //탐색한 정점을 루트로 이동
  return key == p->key; //찾았으면 true
}

delete

마지막으로 delete함수를 구현해봅시다.
delete함수는 먼저 삭제를 할 노드를 splay 한 뒤, 삭제를 합니다.
만약 자식이 0개 혹은 1개라면 그냥 삭제를 하지만, 자식이 2개라면 두 서브 트리를 붙여줍니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void delete(int key){
  if(!find(key)) return; //없으면 종료 and 삭제할 노드를 루트로 이동
  node* p = tree;
  if(p->l && p->r){ //자식 노드 2개
    tree = p->l; tree->p = NULL; //왼쪽 자식이 새로운 루트

    //오른쪽 서브 트리를 왼쪽 서브 트리 아래에 삽입
    node* x = tree;
    while(x->r) x = x->r;
    x->r = p->r; p->r->p = x;
    delete p; return; //노드 삭제
  }
  if(p->l){ //자식이 왼쪽만 있는 경우
    tree = p->l; tree->p = NULL; //왼쪽 자식이 새로운 루트
    delete p; return; //노드 삭제
  }
  if(p->r){ //자식이 오른쪽만 있는 경우
    tree = p->r; tree->p = NULL; //오른쪽 자식이 새로운 루트
    delete p; return; //노드 삭제
  }

  //자신밖에 없을 경우
  delete p; tree = NULL;
}

지난 글에서는 splay tree의 기본 연산, 이번 글에서는 splay tree에서의 삽입/삭제/검색 방법에 대해 알아보았습니다.
다음 글에서는 k-th element를 찾는 방법에 대해 알아보겠습니다.