Perfect balanced KDTree - Code
2009.11.03 03:01 Edit
알고리즘 숙제로 KDTree Construct를 효율적으로 하는 숙제가 나왔다.
KDTree는 x,y 좌표 같은 것이 들어오는데 바이너리 트리에 구겨 넣고 싶을 때 사용하는 자료형이다.
바이너리 트리인데 한번은 x에 대해서 바이너리 다음 depth에서는 y에 대해서 그다음은 z가 있으면 z에 대해서 나누고 만약 z가 없다면 다시 x에 대해서... 그런식으로 진행하는 자료형이다.
그래서 이걸 어떻게 효과적으로 만드는지에 대해서 고민을 많이 했다.
그냥 바이너리 트리를 구축하는 것이라면 가운데 값을 가운데 넣고 그 왼쪽에는 가운데 값 보다 작은 값들 중 가운데 값을 넣고 오른쪽에는 가운데 값 보다 큰 값중에 가운데값을 넣고 하는 식으로 만들면 된다.
하지만 KDTree는 가운데 값을 찾고 다음에 넣을 때는 y좌표의 가운데를 찾아야한다.
뭐 이러한 연유로 좀 찾기가 어려워서 어떻게 할까 고민을 하다가 방법을 스스로 알아냈다고 기뻐하면서
만들었는데, 사실은 검색해보니 이미 다 있는 방법이더라..아놔~ 방법 고안해낸 줄 알고 좋아했더니 ㅋㅋ
construct(s:시작,e:끝,k:이번에정렬할인덱스)
if(s>=e) return
sort(s,e,by k);
swap(s,(s+e)/2);
construct(s+1, (s+e)/2,(k+1)%n);
construct((s+e)/2+1, e,(k+1)%n);
이런식으로 nlogn만큼 sort를 호출하게 되면 해결 ㅋㅋ
O((nlogn)log(nlogn)) 이런 시간 복잡도가 나오지 않을까
