ps:이진_탐색_트리
목차
이진 탐색 트리 (Binary search tree)
- [작성중]
- 이진 탐색 트리에 대한 부분은 생략. 나중에 시간될때 채워넣기로 하자.
- 우리가 진짜 관심이 필요한 것은 Self-balancing binary search tree 이다. bbst라고 부르겠다.
- 이것을 구현하는 방식은 다양하고, 보통 교과서에서 배우는 것은 AVL tree와 red-black tree를 배운다.
- 그리고 cpp에는 bbst가 기본 라이브러리에 있고 (set, map), 대부분은 성능이 우수한 red-black tree로 구현되어있다.
- 하지만, python에는 기본 라이브러리에 bbst가 없기 때문에, 꼭 필요한 경우에는 구현해서 써야 하는데.. red-black tree는 구현이 너무 복잡해서 PS용도로 쓰기에는 적절하지 않다. 보통 PS에서 BBST를 구현해서 사용해야 할 경우에는 그나마 구현이 심플한 treap이나 splay tree를 사용한다. 스플레이 같은 경우는 구현이 심플해서라기 보다는.. 어차피 스플레이를 써야만 해결되는 연산이 있기 때문에 그런 문제를 풀기 위해 스플레이 구현체를 만들어놓고 그것을 그냥 여기저기에 사용하는 느낌이긴 하다.
- 하지만 가능하면, BBST를 안쓰고 문제를 풀수 있으면 가장 좋긴 하다. 그래서 우선 BBST를 써야 할것 같지만 안쓰고도 해결할수 있는 유형들을 정리해보겠다.
- 당장 떠오르는건 없고.. 접할때마다 여기 모아놓을 계획
BBST를 써야 할 것 같지만 안쓰고도 해결 가능한 유형
lower_bound를 찾아서 삭제하는 것을 반복
- 쿼리가 non-decreasing하는 경우에는 BBST를 안쓸수 있다.
- 이것은 18042를 풀면서 생각한 방법인데, 원래 웰노운인지는 잘 모르겠다.
- 먼저 삭제가 없다면, 당연히 bbst 대신 정렬된 배열에서 이분탐색으로 쿼리를 처리할수 있다. 하지만 이분탐색 q번 대신에, 그냥 가장 작은값부터 스위핑하면서 q개의 쿼리를 모두 순서대로 처리할수도 있다. O(qlogn) vs O(n+q) 인데, 쿼리 갯수가 원소 갯수와 비슷하다면 후자가 더 효율적이다
- 삭제가 있을때도 비슷하게 스위핑해서 풀수 있다. lower_bound(q1),lower_bound(q2),lower_bound(q3),.. 이 모두 다른 원소라면 실제로 삭제하지 않고 삭제한 척만 하면서 그냥 스위핑하면 된다. 문제는 lower_bound(q1) = lower_bound(q2)인 경우가 있을 때이다. 이러면 lower_bound(q1)을 찾아서 삭제하고 나면 lower_bound(q2)는 그 이전 원소가 해당되게 된다.
- 이것을 해결하기 위해 방법을 조금 개선해보자. arr에 원소를 정렬해놓고, qi가 들어오면 qi보다 작은 원소들을 arr에서 다 제거해서 스택에 넣는다 (큰수가 탑에 올라오도록). 그리고 스택에서 탑을 pop하면 그게 lower_bound값이 된다. 이렇게 원소들을 arr과 stack으로 분리해서 모아놓으면 쉽게 처리가 가능하다. 시간복잡도는 여전히 O(n+q)이다.
삭제와 lower_bound 만 주어짐
- DisjointSet을 사용해서 처리하는 웰노운 트릭이 있다.
- lower_bound가 같은 원소들을 같은 셋으로 묶어주는 방식이다. 인접한 원소들끼리만 같은 셋으로 묶이게 된다.
- 구체적인 방법은
- 원소들을 좌표압축하자. 원소 갯수만큼의 크기를 갖는 dsu를 만든다.
- 그리고 DSU의 셋들과 lower_bound 값을 매칭시키는 매핑이 필요하다. 처음에는 mapping[i]=i 로 초기화 된다
- n을 삭제하면, n과 n-1을 union한다. union된 셋의 lower_bound 값을 n-1을 포함하던 셋의 lower_bound으로 갱신한다.
- 코드를 나름 효율적으로 써보면 이런식 (여기서는 lower_bound 대신에 upper_bound 값을 찾아주는 코드)
class DeletableSet: __slots__ = ['_parent'] def __init__(self, size): self._parent = list(range(size)) def get_greater_or_equal(self, x): if (par := self._parent[x]) == x: return x while (gpar := self._parent[par]) != par: self._parent[x] = gpar x, par = par, gpar return par def delete(self, x): if (root_x := self.get_greater_or_equal(x)) == ( root_y := self.get_greater_or_equal(x + 1) ): raise ValueError self._parent[root_x] = root_y
ps/이진_탐색_트리.txt · 마지막으로 수정됨: 2023/08/07 14:29 저자 teferi
토론