트리의 종류와 쓰이는 이유(난이도 하~중)

우선 자세한 내용을 쓰기전에, 이 포스팅은 어떻게 구현하는가 보다는, 이 알고리즘을 어떨때 쓰는지에 대한 설명에 초점을 맞췄다.

따라서 구현방법보다는, 다음 내용들이 어디에 쓰이는지 모르겠는 사람들이 보는것을 추천한다. 

 

1. 이진탐색트리(binary search tree)

이진 탐색트리의 핵심은 왼쪽 자식은 나보다 작고, 오른쪽 자식은 나보다 크다는 것이다. 일종의 정렬되어있는 배열이나 리스트와 비슷한 역할을 하는데 필요로 하는 시간이 다르다. 자세한건 아래 표 참조.

	만드는데 드는 시간 (정렬 안된 배열에서)	삽입/삭제 시간	탐색 시간
이진 탐색 트리	O(nlogn)	O(logn)	O(logn)
배열(정렬)	O(nlogn)	O(n)	O(logn)
리스트	O(n)	O(1)	O(n)

보통 이진탐색트리는 삽입/삭제/탐색 3개가 전부 빈번히 발생할때 사용된다.

구현할때는 대체로 그냥 배열을 사용하기 때문에 메모리가 배열보다 더 들지도 않는다. (부모 자식rule을 2*i, 2*i+1로 하면 됨)

2. 힙(heap)

힙의 핵심은 이진 트리중에서, 두 자식 모두 부모보다 작다(크다)는 것이다. 따라서, 최소(최대)값을 구할때 매우 유용하게 쓰인다. priority queue(우선순위 큐)를 만들때도 heap을 사용한다. 

	만드는데 드는 시간 (정렬 안된 배열에서)	삽입/삭제 시간	최대(최소)값탐색시간
힙	O(nlogn)	O(logn)	O(1)
배열(정렬)	O(nlogn)	O(n) //최대값 삭제는 O(1)	O(1)
정렬된 리스트	O(nlogn)	O(n)/O(n) //최대값 삭제는 O(1)	O(1)

주요 용도는 heap정렬과 우선순위 큐가 쓰이는 모든 문제들이 있다.(다익스트라 알고리즘이 대표적)

heap정렬의 경우, 힙을만들고 최대값만 계속 빼내면 O(nlogn)이다 라는 것인데, 문제는 사실 heap정렬대신 이해하기 쉬운 quick정렬을 써도 별 상관이 없기때문에, 몰라도 별 지장이 없다.

문제는 이제 우선순위 queue가 쓰이는 문제들인데, 계속 값들이 추가되는 와중에 최대값을 찾아내야하는 문제, 또는 알고리즘의 경우 heap 또는 heap을 사용하는 우선순위 queue를 사용하지 않으면 풀기 어려울 것이다. 

이것 역시 구현은 배열로 하면된다. (완전 이진 트리 구조일경우 무조건 배열로 해도 별 상관이 없다.)

3. 세그먼트 트리(segment tree)

세그먼트 트리는, 이진 트리를 사용하는데 각 이진트리의 node가 배열의 부분합을 가지고 있고, 자식2개의 합이 부모의 값이 되는 트리이다. 부분합을 빠르게 구하기 위해서 만들어졌으며, 특히 부분합을 구하는 배열의 원소의 값이 지속적으로 바뀔때 사용한다.

	만드는데 드는 시간	부분합 구하기	값 변경
세그먼트 트리	O(n)	O(logn)	O(logn)
부분합 배열	O(n)	O(1)	O(n)
그냥 배열로 구하기	O(1)	O(n)	O(1)

값이 변경되지 않는 부분합 문제의 경우 부분합 배열이 훨씬 효과적이나, 값이 계속해서 변경되는 부분합 문제의 경우, 세그먼트 트리를 활용하면 문제가 풀릴것이다. 

거의 순수 부분합 문제에서만 필요하다.