Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
알고스팟 INSERTION - 삽입 정렬 뒤집기를 해결하기 위해 등장하는 자료구조.
트립(Treap)
대부분의 표준 라이브러리에서 제공하는 이진트리 자료구조들은 균형 잡힌 이진트리(레드- 블랙 트리 등..)으로 구현이 되어있다. 그대로 사용한다면 문제가 없지만 이진 트리에 추가적인 기능을 넣어주고 싶어도 레드 블랙 트리는 너무 구현이 복잡하다 보니 문제를 풀면서 처음부터 끝까지 구현해내긴 무리가 있다.
이럴 때는 비교적 간단히 균형 잡힌 트리를 만들어 주는 트립을 구현해보자.
트립(Treap)은 Tree와 Heap의 합성어로 말 그대로 heap의 특성과 tree의 특성을 합쳤다.
heap에서는 부모 노드가 자식 노드보다 크다는 규칙만을 가진다.
트립에서는 이와 같이 부모 노드의 우선순위가 자식 노드의 우선순위보다 크도록 트리가 구성된다.
예를 들어 일반적인 이진 트리에 오름차순으로 이미 정렬된 수(1, 2, 3, 4, 5)들이 순서대로 삽입될 경우
skewed tree(사향 트리)가 생성되어 이진 트리의 장점인 원소의 검색시간이 O( N, 노드 수)가 되어 버린다.
트립은 노드를 삽입시 랜덤으로 부여한 우선순위 수를 기준으로 heap과 같이 부모 노드가 우선수위가 더 크도록 트리를 재구성한다.
물론 노드의 원소를 탐색하기 위한 이진 트리의 특징도 잃지 않는다.
루트 노드의 왼쪽은 루트보다 낮은 수를, 오른쪽 수는 더 큰 수를 저장한다.
수열 1, 2, 3, 4, 5의 우선순위가 랜덤으로 아래와 같이 정해질 경우 트리는 아래와 같이 재구성되며 수를 저장한다.
(12, 56, 36, 76, 11)
트립(Treap) 구현
*구현 코드는 알고리즘 문제 해결 전략 서적을 참고하였습니다.
'알고리즘 공부 > 알고리즘 기법' 카테고리의 다른 글
| [절단선과 절단점] Articulation point, Bridge (Cut vertex, cut edge) (0) | 2021.03.14 |
|---|---|
| [임계 경로 알고리즘] Critical Path Method (백준-1948 해설) (0) | 2021.03.09 |
| [Union-Find] 유니온-파인드, 분리 집합 (백준 1717 - 집합의 표현 해설) (1) | 2021.02.28 |
| [Fenwick Tree Lazy propagation] - 펜윅 트리에 Lazy propagation 적용하기 (1) | 2021.02.27 |
| [정수론] 에라토스테네스의 체와 소인수 분해 (0) | 2021.01.12 |