블로그 이사 중입니다 >> gumgood.github.io

Treap 본문

Problem Solving/분류없음

Treap

gumgood 2017. 5. 27. 02:38

- STL에서 지원하지 않는 BST의 연산이 필요한 경우 Balanced BST를 직접 구현해야 한다.

- AVL tree나 red-black tree와 같은 Balanced binary tree보다는 구현이 간단하다.

- Treap은 tree와 heap의 특성을 모두 갖춘다.


1. Treap의 특징

  - BST와 성질은 같으나 tree형태가 '원소 추가 순서'가 아닌 '난수'에 의해 임의로 결정된다.

    따라서 어떤 순서로 원소가 추가/삭제 되더라도 tree 높이의 기대치*는 항상 일정하다

    (깊이가 n-1인 최악일 확률은 매우 낮다. n=100일 경우, 1/(4*10^157) )

  - treap은 새 node가 추가될 때마다 해당 node에 우선순위(prioriy)를 부여한다.

    우선순위는 원소와 관계없는 '난수'를 통해 생성한다. 이에 따라 부모의 우선순위가 자식의 우선순위보다 높은 BST를 만든다.


2. Treap의 조건

  ① BST 조건 : 모든 node들에 대해

        '왼쪽 subtree의 node들의 원소'는 '해당 node의 원소'보다 작아야 한다. 

        '오른쪽 subtree의 node들의 원소'는 '해당 node의 원소'보다 커야 한다.

  ② heap 조건 : 모든 node의 우선순위는 각각의 자식 node들보다 크거나 같다.

      (prioriy가 높은 순으로 추가된 BST라 생각하면 될 듯)


3. Treap의 높이

  node를 random하게 섞었을 때, tree 높이의 기대치가 보다 작아야 한다.

  즉, N개의 원소를 갖는 treap에서 x를 찾을 때, 거치는 node의 수는 개 이하여야 한다.

  (증명은 종만북 참고, 요약하자면 한 level을 내려갈 때마다 후보의 수가 평균 2/3으로 줄어든다.)

  따라서 treap 높이의 기대치는 


4. Treap의 연산

  STL에서 지원하지 않는 연산들은 다음과 같은 것들이 있다.

  ① k번째 element 찾기

      일반적인 BST에서도 사용할 수 있다.. 수행시간이 트리의 높이에 비례함에 주의해야한다.

  ② x보다 작은 원소 세기

      특정 범위 [a,b)가 주어질 때, 이 범위 안에 있는 원소 수를 구하는 연산이다.

      간단하게 countLessThan(b) - countLessThan(a)으로 구할 수 있다.

      (countLessThan(x) := 주어진 원소 x보다 작은 원소의 수를 반환)

      역시 일반 BST에서 사용할 수 있고, 수행시간은 트리의 높이에 비례한다.


5. Treap의 구현

  C++11(종만북 코드)


6.기타

  아직까지 활용하는 문제를 찾지는 못했다. K번째 수를 구하는 문제는 sort하는게 더 빠르다...

'Problem Solving > 분류없음' 카테고리의 다른 글

Segment Tree (구간 트리)  (0) 2017.05.27
Disjoint-set  (0) 2017.05.27
Diameter of tree  (0) 2017.05.27
Tree Traversal  (0) 2017.05.27
Treap  (0) 2017.05.27
Priority Queue & Heap  (0) 2017.05.27
0 Comments
댓글쓰기 폼