bst1 이진 탐색 트리, 트립 보통 c++의 set이나 map을 이진탐색트리로 구현한다. (avl트리나 레드블랙 트리) 하지만 set이나 map은 k번째로 큰 원소가 무엇인지 알 수없다. 이런 기능을 가능하게 하는 구조로 '트립'이 있다. stl에서 사용하는 구조보단 느리지만 확률적으로 최악의 경우 로그시간에 동작한다. 노드에 값 외에 우선순위를 추가로 갖는다. 우선순위는 생성시 랜덤하게 부여된다. 트립은 다음 두가지 속성 (bs tree + heap)을 만족해서 treap이라고 부른다. 1. 모든 노드에 대해 왼쪽 서브트리에 있는 노드들의 원소는 해당 노드의 원소보다 작고, 오른쪽 서브트리에 있는 노드들의 원소는 해당 노드의 원소보다 크다. 2. 모든 노드의 우선순위는 각자의 자식 노드보다 크거나 같다. typedef long lo.. 2020. 2. 10. 이전 1 다음