[자료구조] Treap (Heap+Tree)

자료구조 트립입니다.

저에겐 처음들어보는 자료구조였습니다. 하지만 개념자체는 이해하기 어려운 자료구조는 아니였으며

그 구현의 이해를 이해하는데 조금 시간이 걸렸을 뿐입니다.

제목처럼 트립은 힙과 트리의 결합형입니다.

다시말해 우선순위 힙과 이진트리 탐색의 장점을 합쳐놓은 것으로

주요목적은 트리가 한쪽으로 치우지지 않고 되도록 고르게 노드가 잡혀서

탐색, 삽입, 삭제등의 작업을 O(logN)에 마칠 수 있도록 하는것입니다.

이진트리의 탐색은 구현도 복잡하지만 자칫 잘못하면 운이 나빠 트리가 선형구조로 되어서

O(N)이 될 수도 있기 때문입니다.

또 힙의 장점으로써 하위노드들은 부모노드 보다 우선순위가 낮음을 이용합니다.

우선 트립을 구현한 헤더파일입니다.

보다시피 이진트리나 힙처럼 일반적인 구조를 갖고 있으나 특이하게

priority를 갖고 있습니다. 이 값이 

트리를 치우치지 않고 균일하게 노드가 들어가도록 하는 장치입니다.

생성자가 호출되면 rand()함수를 이용해 우선순위를 결정하고 있습니다.

rand()가 못 믿음직 스러우면 직접 우선순위를 반환할 함수를 만들어도 되겠습니다

트립클래스의 함수들을 구현한 hpp파일입니다.

using을 이용하여 타입을 정의한 부분은 C11에서 지원하는 기능입니다.

insert만 간단히 설명해보겠습니다.

새로운 노드가 들어오면 루트의 우선순위와 비교합니다.

새로운 노드가 루트보다 우선순위가 높다면 새로운 노드를 루트로 지정하고

기존의 루트는 왼쪽의 루트가 될지, 오른쪽의 루트가 될지를 키의 대소로 비교하여 재귀적으로 판단합니다.

kth함수는 찾으려는 key가 있는 노드가 노드의 몇번째 위치에 있는지를 알려주는 함수로

size를 이용하여 탐색하게 됩니다.