스니 스니 닷넷 : : kd - tree 
 스니 스니 닷넷 
 Total | 176 , 946 
 컴퓨터 과학 ! / Algorithms 2004 . 11 . 16 . 00 : 05 
 이건 지난 학기 FS 시간 에 배운 것 인데 , 
 이번 에 알고리즘 시간 에 나와서 
 한 번 복습 ! 
 ⊙ Introduction 
 여기 에서 다루 는 kd - tree 는 공간 DB 로 , 기존 의 문자 DB 와 는 다르 다 . key 값 매칭 문제 이 고 , 굉장히 큰 양 을 공간 기반 으로 검색 한다 . 공간 기반 검색 이란 , range 로 표현 된 질의 를 검색 한다는 것 이 다 . Spatial data 는 points , lines , polygons 등 을 포함 하 고 있 따 . 
 Spatial data 를 효율 적 으로 지원 하 기 위해서 는 , 다음 과 같 은 특징 적 어려움 을 알 아야 한다 . 
 ① First , spatial data are latge in quantity , complex in structures and relationships 
 ② Second , the retrieval process employs complex spatial operators like intersection , adjacency , and containment 
 ③ Third , it is difficult to define a spatial ordering , so conventional techniques cannot be employed for spatial operations 
 → spatial indices 필요 ! 
 ( 1 ) kd - tree : Binary - tree based indexing 
 kd - tree 는 multi - attribute data index 를 binary search 하 는 tree 로 , k 는 표현 될 데이터 공간 의 차원 을 가리킨다 . 각 depth 에서 , 어떤 branch 로 갈 것 인가 를 결정 하 는 데 에 다른 attribute 이 사용 된다 . 예 를 들 어 , 2 - d ( x , y ) tree 에서 는 짝수 depth 에서 x 좌표 가 branch 기준 이 라면 , 홀수 depth 에서 는 y 좌표 가 branch 방향 의 기준 이 된다 . 마지막 으로 , 이 tree 는 꼭 균형 을 이룰 필요 는 없 다 . 
 A 가 제일 먼저 들어간 것 을 알 수 있 다 . 즉 , 최초 의 분리 자 는 root 이 다 . 
 ① Principle 
 Node 는 각각 의 실제 data point 를 나타내 고 , 검색 방향 의 지표 가 된다 . ( left , right 두 개 의 child 가 있 다 . → 현재 노드 값 보다 작 은가 ? 큰가 ? ) 
 한 Node 는 5 개 의 field 로 구성 되 어 있 다 . LOSON ( 작 은 값 을 가진 left 자식 ) , HISON ( 큰 값 을 가진 right 자식 ) , 좌표 ( x , y , ...), NAME ( 해당 노드 에 대한 정보 . 포인터 가 들어갈 수 도 있 다 . ) , DISC ( 좌표 이름 을 가리킨다 . 즉 , 이 노드 는 x 를 기준 으로 했 느냐 y 를 기준 으로 했 느냐 . 등 . ). 
 ② Insertion 
 Binary search tree 에서 의 insertion 방법 과 유사 하 다 . 다른 점 이 있 다면 , 앞 에서 설명 했 듯이 , depth 마다 비교 하 는 attribute 가 다르 다는 것 이 다 . tree 의 bottom 에 도달 하 면 , 거기 에 새 node 를 넣 는다 . 
 ③ Search 
 Search 역시 매우 straightforward 하 다 . 흐흐 BST 처럼 찾 아 내려가 면 된다 . 여기 에서 역시 , 다른 점 은 depth 마다 비교 기준 의 attribute 이 다르 다는 점 뿐 . 참 그리고 , 질의 가 , 조건 질의 가 가능 하 다는 것 이 또 하나 틀린데 , 예 를 들 어 , ' Y > 20 인 점 들 을 찾 아라 ' 라든지 , '( 75 , 15 ) 에 가까운 점 들 을 찾 아라 ' 등 이 가능 하 다는 것 이 다 . 
 Region Search 는 Euclidean distance 를 이용 하 여 구할 수 있 다 . node ( a , b ) 근처 거리 d 안 에 있 는 점 들 을 다 구하 라는 질의 가 들어오 면 , 우선 ( a - d ) ≤ x ≤ ( a + d ) , ( b - d ) ≤ y ≤ ( b + d ) 안 의 점 들 을 다 구한다 . 그런데 이렇게 구한 점 은 , 반지름 d 인 원 안 에 있 는 점 이 아니 라 , 한 변이 2 d 인 정사각형 안 에 들어오 는 점 이 므로 , 점 들 을 구한 다음 에 range 안 에 들어오 는 게 맞 는지 확인 이 필요 하 다 . 
 Search 결과 Miami 를 찾 았 다 ! 
 ④ Deletion 
 앞 에 insert 나 search 는 BST 와 비슷 하 여 쉬웠 지만 , deletion 은 좀 더 복잡 하 다 . 각 depth 마다 , DISC 가 달라서 , 원래 tree 의 root 는 DISC 가 x 지만 , subtree 의 root 는 y 가 될 수 도 있 기 때문 에 , 모든 subtree 가 kd - tree 가 아니 다 . 그래서 그냥 마구 삭제 해 버리 면 문제 가 생긴다 . 
 kd - tree 로 부 터 ( a , b ) 노드 를 삭제 한다고 할 때 , ( a , b ) 의 두 subtree 가 empty tree 이 면 그냥 삭제 하 면 되 고 , 아니면 ( a , b ) 의 subtree 들 중 에서 가장 적절 한 대체 노드 ( c , d ) 를 찾 아서 , replace 시킨다 . 이 ( c , d ) 는 recursive 하 게 다시 삭제 되 는 것 이 다 . 그렇 다면 , 이 대체 노드 는 어떻게 찾 는 것 일까 ? 오른쪽 subtree 에서 가장 작 은 값 을 가진 노드 나 , 왼쪽 subtree 에서 가장 큰 값 을 고르 면 된다 . 그러면 다음 의 예 를 보 자 . 
 사실 이것 도 찬찬히 보 면 매우 쉽 다 . 그죠 ? 
 ⑤ 장단점 
 kd - tree 는 partial matching search 에 유용 하 지만 , empty space 가 없 고 , point search 와 region search 가 다 가능 하 다 . 하지만 , 균형 이 심 ~ 하 게 안 맞 으면 performance 가 안 좋 다 . kd - tree 는 메모리 기반 index 이 다 . File 기반 에서 는 . .. 안 좋 다 . 
 구독 하 기 스니 스니 닷넷 
 Posted by 스니 
 oakyoon 
 쳇 , 공부 쟁이 ! 
 2004 . 11 . 16 09 : 13 [ ADDR : EDIT / DEL : REPLY ] 
 치 앙수 
 2004 . 11 . 16 18 : 42 [ ADDR : EDIT / DEL : REPLY ] 
 스니 스니 
 지난 학기 FS 시간 에 했 다던 kd - tree 야 . 으흐흐흐 잘 읽 어 봉 . 쉬움 . 
 2004 . 11 . 16 19 : 09 [ ADDR : EDIT / DEL : REPLY ] 
 요거 찾 아 들어왔 슴다 . 꼭꼭 씹 어서 이해 되 었 구요 . .. ^^ 
 혹 제 가 모르 는 거 있 음 물어도 되 나요 ? 
 많이 도와 주 세요 ~~~ 
 2006 . 09 . 25 00 : 11 [ ADDR : EDIT / DEL : REPLY ] 
 아 . . 저 도 많이 부족 하 지만 . .. 
 제 가 아 는 것 이 라면 야 . . ^^ 
 2006 . 09 . 25 18 : 39 [ ADDR : EDIT / DEL : REPLY ] 
 비케이 러브 
 알고리즘 에 대한 기초 가 많이 부족 한 탓 인지 아무리 읽 어 봐도 잘 이해 가 가질 않 네요 . . 이 알고리즘 으로 image serach 프로그램 을 만들 어야 하 는데 어떻게 공부 를 해야 할까요 ? 쫌 가르쳐 주 세요 
 2006 . 11 . 14 15 : 36 [ ADDR : EDIT / DEL : REPLY ] 
 퍼가 염 . . 
 2007 . 04 . 10 11 : 11 [ ADDR : EDIT / DEL : REPLY ] 
 허 헛 ~! 구글 에서 k - d tree 치 니까 세 번 째 로 뜨 는 구 랴 ~~ 
 2007 . 10 . 11 23 : 13 [ ADDR : EDIT / DEL : REPLY ] 
 2007 . 10 . 20 17 : 17 [ ADDR : EDIT / DEL : REPLY ] 
 쪼 꼬 레 또 
 재밌 게 잘 써 놓 으셔서 퍼 갑니다 . 스크랩 이나 트랙백 으로 가져가 고 싶 었 는데 , 서비스 업체 가 달라서 안 되 네요 . . 암튼 잘 보 고 갑니다 ^^ 
 2007 . 11 . 09 19 : 14 [ ADDR : EDIT / DEL : REPLY ] 
 네 ㅡ 얼마 든지요 ! : ) 
 2007 . 11 . 16 13 : 29 [ ADDR : EDIT / DEL : REPLY ] 
 아 아아악 누나 ~~~!! 잘 지내 죠 ? 흐윽 ㅠ 
 알고리즘 분석 셤 이 낼 이 라 kd - tree 검색 하 다가 익숙 한 스니 스니 보 고 ㅋㅋ 
 역시 사발 의 천재 계 보군 요 흐음 흐음 . .. 이런 정리 를 ! 
 잘 참고 하 고 가요 ~~^^ 
 2009 . 10 . 22 20 : 16 [ ADDR : EDIT / DEL : REPLY ] 
 근데 deletion 할 때 그림 에서 는 오른쪽 subtree 이 던 왼쪽 subtree 이 던 minimum 값 만 찾 아서 교체 해 주 네요 . 누나 글 이랑 달라서 어느 쪽 이 맞 는 건가 해서 요 ㅠ _ ㅠ 
 2009 . 10 . 22 20 : 35 [ ADDR : EDIT / DEL : REPLY ] 
 그래 , 그러 고 보 니 설명 과 그림 에 약간 문제 가 있 구나 . 
 너무 오래 전 에 작성 한 글 이 라 다시 읽 어 보 고 다음 과 같 은 결론 을 내렸 다 . 
 1 . 자료 구조 라는 것 은 정해진 규칙 을 ' 유지 ' 하 고 있 도록 만드 는 것 이 주 목적 이 다 . 이 규칙 은 검색 을 용이 하 게 하 며 , 따라서 이 규칙 을 지키 도록 삽입 과 삭제 작업 을 해 주 어야 한다 . 
 2 . kd - tree 의 규칙 은 각 레벨 마다 기준 좌표 ( DISC ) 가 다른 BST 이 다 . 따라서 left subtree 의 x - DISC 에 해당 하 는 노드 의 x 값 은 parent 의 x 값 보다 모두 작 아야 하 며 , right subtree 의 x - DISC 에 해당 하 는 노드 의 x 값 은 parent 의 x 값 보다 모두 커야 한다 . y 도 마찬가지 이 다 . 
 3 . 따라서 , right subtree 의 min , left subtree 의 max 로 target 을 교체 하 여 삭제 하 는 것 이 기본 적 으로 생각 할 수 있 는 방법 이 다 . ( C 노드 를 E 노드 로 교체 ) 
 4 . 그러나 , 그림 에서 는 left subtree 의 min 으로 교체 하 고 그 subtree 를 target 의 right subtree 로 만들 어 주 었 다 . 이것 은 , 구현 의 특징 이 라고 할 수 있 는데 , 이 방법 에서 는 left subtree 의 max 냐 right subtree 의 min 이 냐 고민 하 기 전 에 , 무조건 right subtree 의 min 을 구해서 삭제 하 고 , right subtree 가 empty 일 때 에 만 left subtree 에서 교체 할 값 을 찾 는 방법 을 사용 하 기 때문 인 것 같 다 . ( C 노드 를 D 노드 로 교체 한 후 , D 의 left subtree 를 right subtree 로 바꾸 어 주 었 다 . ) 
 이렇게 한 이유 는 아마도 , 트리 가 균형 을 이룰 필요 는 없 으므로 , 교체 할 값 을 빠르 게 찾 고 검색 또한 빨라 지 게 하 기 위한 방법 이 아닐까 싶 다 . 
 2009 . 10 . 23 01 : 37 신고 [ ADDR : EDIT / DEL ] 
 잘 보 고 갑니다 ^^ 스크랩 해 갈게요 
 2010 . 02 . 02 18 : 41 [ ADDR : EDIT / DEL : REPLY ] 
 월하 은 검 
 회사 에서 일 하 다가 12 년 전 의 누나 블로그 를 보 고 가 네요 ^^ 12 년 전 의 누나 와 지금 의 누나 에게 감사 를 표 합니다 ~!! 잘 지내 시 죠 ? 
 2016 . 08 . 05 07 : 47 신고 [ ADDR : EDIT / DEL : REPLY ] 
 « 이전 1 · · · 220 221 222 223 224 225 226 227 228 · · · 275 다음 » 
 스니 의 블로그 
 스니 이야기 ( 223 ) 
 일기 ( 201 ) 
 Have Fun ! ( 15 ) 
 임신 일기 ( 0 ) 
 사진 백업 ( 0 ) 
 알 아 가 기 ( 0 ) 
 En ~ glish ~* ( 0 ) 
 컴퓨터 과학 ! ( 35 ) 
 Automata and Formal . . ( 0 ) 
 차간 거리 
 연구실 생활 
 음주 측정 
 2009 생일 . ( 6 ) 
 인생 의 정답 . ( 3 ) 
 My ♡. 
 기말고사 병 . ( 1 ) 
 직책 과 말씀 길이 는 . .. ( 2 ) 
 회사 에서 일 하 . .. 월하 은 검 2016 
 그 사람됨 을 알 . .. supra 2013 
 태양 이 바다 에 . .. chaussures louboutin pas cher 2013 
 Un trafiquant . .. timberland botas montaña 2012 
 약 한 달 여 전 에 . .. 스니 2010 
 インラインスケ . .. インラインスケ . . 2014 
 ヘルノ ダウン . .. ヘルノ ダウン . . 2014 
 イヤホン . イヤホン 2014 
 ヘルメット バ . .. ヘルメット バ . . 2014 
 デイトナヘッド . .. デイトナヘッド . . 2014 
 [ 사발 ] 한샘 슨 배 : ). 
 준상 슨 배 블로그 . 
 [ 사발 ] 스카이 룩 커 , 효 . .. 
 [ 사발 ] 파 덕이 의 꿈 그 . .. 
 [ 사발 ] 엄한 소리 . 
 제닉스 님 블로그 . 
 랩 애인 혜 연양 블로그 . 
 용용 이 블로그 . 
 : : Daydreami ' s Small . .. 
 정환 블로그 . 
 xino ' s blog . 
 Writing on Dirty Paper . 
 슨 미 슨 미 맛있 는 블로그 .