최상 답변
그래프와 트리 데이터 구조의 차이점 :
그래프
- 그래프에는 두 개 이상의 경로가있을 수 있습니다. 즉 그래프에는 노드간에 단방향 또는 양방향 경로가있을 수 있습니다.
- 그래프에는 루트 노드.
- 그래프는 루프, 회로를 가질 수있을뿐만 아니라 자체 루프도 가질 수 있습니다.
- 그래프에는 그런 것이 없습니다. 부모 자식 관계.
- 그래프는 순환, 루프 등을 가질 수 있으므로 트리에 비해 더 복잡합니다.
- 그래프는 DFS : Depth First Search 및 BFS : Breadth First Search 알고리즘
- 그래프는 순환 또는 비순환 일 수 있습니다.
- 그래프에는 주로 방향 그래프와 무 방향 그래프의 두 가지 유형이 있습니다.
- 그래프 앱 lications :지도의 채색, 알고리즘, 그래프 채색, 작업 일정 등
- 그래프에서, no. 가장자리 수는 그래프에 따라 다릅니다.
- 그래프는 네트워크 모델입니다.
나무
- 나무는 그래프의 특별한 형태입니다. 즉, 최소로 연결된 그래프이고 두 정점 사이에 경로가 하나뿐입니다.
- 트리는 루프, 회로 및 자체 루프가없는 그래프의 특별한 경우입니다.
- 트리에는 정확히 하나의 루트가 있습니다. / span> 노드와 모든 하위 에는 부모가 하나만 있습니다.
- 트리에는 부모 자식 관계가 있으므로 흐름이 방향과 함께있을 수 있습니다. 위에서 아래로 또는 그 반대로합니다.
- 나무는 주기도, 자체 루프도없고 여전히 연결되어 있으므로 그래프보다 덜 복잡합니다.
- 트리 순회는 일종의 순회의 특별한 경우입니다. 그래프 트리는 Pre-Order , In-Order 및 주문 후 ( DFS 또는 BFS 세 가지 모두 알고리즘)
- 트리는 DAG 범주에 속합니다. 방향성 비순환 그래프는 순환이없는 일종의 방향성 그래프입니다.
- 다른 유형의 트리는 다음과 같습니다. 이진 트리 , 이진 검색 트리, AVL 트리, 힙
- 트리 애플리케이션 : Tree Traversal & Binary Search와 같은 정렬 및 검색.
- 트리에는 항상 n-1 가장자리가 있습니다.
- 트리 은 계층 적 모델입니다.
답변
따라서 kd 트리는 처음 보면 실제적인 것보다 더 이론적 인 것처럼 보일 수 있습니다. 하지만 실제로는 그렇지 않습니다.
kd 트리에는 다음과 같은 다양한 중요한 애플리케이션이 있습니다.
1 . 인접 이웃 검색
Social Cop 을 사용하세요. Social Cop은 사람들이 실시간으로 가장 가까운 경찰서에 범죄를 신고 할 수 있도록 도와줍니다.
여기서 문제가되는 것 같습니까?
예, 맞습니다. 신고를하기 전에 범죄 장소에서 가장 가까운 경찰서를 찾아야합니다.
어떻게 할 수 있습니까? 빠르게 ?
K-d 나무는 도시의 2 차원지도에서 가장 가까운 이웃을 찾는 데 도움이됩니다. 도시의 모든 경찰서 위치에서 2 차원 kd 트리를 구성한 다음 kd 트리를 쿼리하여 도시의 특정 위치에서 가장 가까운 경찰서를 찾는 것입니다.
알겠습니다. 그들이 할 수있는 일을 알았습니다. 하지만 어떻게하나요?
바이너리 검색 트리 의 작동 방식을 이미 알고 있다면 kd 트리의 작동 방식을 이해하면 새로운 것이 아닙니다. 이진 검색 트리가 실제 라인 을 분할하는 데 도움이되는 것처럼 k-d 트리는 공간 분할에 도움이됩니다. k-d 트리는 공간 영역을 재귀 적으로 분할하여 트리의 각 수준에서 이진 공간 분할을 만듭니다.
3 차원 kd 트리로 분할 된 공간의 3 차원 영역은 다음과 같습니다. [1] :
3 차원 kd 트리. 첫 번째 분할 (빨간색)은 루트 셀 (흰색)을 두 개의 하위 셀로 자른 다음 각각이 두 개의 하위 셀로 분할 (녹색)됩니다. 마지막으로이 네 개는 각각 두 개의 하위 셀로 분할 (파란색)됩니다. 더 이상 분할이 없기 때문에 마지막 8 개를 리프 셀이라고합니다.
그리고 트리는 어떻게 구성됩니까?
시작하려면 k 차원 공간에 일련의 점이 있습니다.2 차원 kd 트리의 예를 들어 보겠습니다.
입력 : (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
출력 : 2 차원 kd 트리 [2] :
이진 검색 트리의 경우 각 내부 노드에서 실제 행의 이진 파티션은 점 . 마찬가지로 2 차원 kd 트리의 경우 각 내부 노드에서 2 차원 데카르트 평면의 이진 분할은 선 .
이진 검색 트리의 경우 내부 노드가 나타내는 점이 실제 선을 분할하는 데 사용되는 점 역할을합니다. 2 차원 kd 트리의 경우 분할 선을 어떻게 선택합니까?
본질적으로 , 내부 노드가 나타내는 점을 통과하는 선을 선택할 수 있습니다. 2 차원 데카르트 평면을 분할합니다.
위의 kd 트리 출력은 트리의 각 내부 노드에서 파티션 라인을 선택하는 간단한 방법을 사용하여 구성되었습니다.-
레벨 0 :- 첫 번째 차원 ( X 이 경우) 해당 노드가 나타내는 지점을 통과합니다.
Level 1 :-분할 선 선택 두 번째 측정 기준 (이 경우 Y )에 수직이고 다음으로 표시되는 점을 통과합니다. 문제의 노드입니다.
: : :
레벨 k-1 :- k 번째 측정 기준 및 표시된 점 통과 문제의 노드에 의해. 레벨 k :- 첫 번째 차원 에 수직 인 분할 선을 선택합니다 ( X (이 경우)) 문제의 노드가 나타내는 점을 통과합니다.
따라서 기본적으로 각 수준에서 X 및 Y 차원을 번갈아 가며 kd 트리의 각 내부 노드에서 분할 라인을 선택하기 위해.
kd 트리 [2]의 각 노드 옆에 표시되는 레이블은 해당 수준의 노드에서 분할 선에 대한 차원 선택을 나타냅니다.
Let ” 이제 2 차원 kd 트리가 2 차원 평면을 분할하는 방법을 확인합니다 [3] :
좋아요. 검색은 어떻게 수행합니까?
“나는 당신에게 맡기지 만 당신에게 맡기겠다”라고 말하지 않겠습니다. 완전히 이해하려면 다른 리소스의 도움을 받아야합니다. 하지만 kd 트리에 의한 공간 분할은 공간의 특정 지점에 가장 가까운 이웃을 찾는 데 도움이 될 수 있습니다. 모든 파티션을 탐색 할 필요없이 Social Cop에 대한 실시간 보고를 수행합니다.
kd 트리에서 가장 가까운 이웃 알고리즘을 이해하기위한 좋은 리소스는 다음과 같습니다. http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
kd 트리의 배경 대부분은 이미 첫 번째 애플리케이션에 대한 논의에서 다루었으므로 kd 트리의 다른 애플리케이션에 대해 간략하게 살펴 보겠습니다.
2. 다차원 검색 키를 포함하는 데이터베이스 쿼리
(40, 50) 연령 그룹의 모든 직원을 요청하고 월급 (15000, 20000) 범위의 급여를받는 쿼리는 연령이 x 축을 따라 그려지는 기하학적 문제로 변환 될 수 있습니다. 급여는 y 축을 따라 표시됩니다. [4]
[4] x 축은 연령을 나타냅니다. 직원은 년 이고 y 축은 월급을 천 루피 로 나타냅니다.
(age, salary) 의 복합 색인에 대한 2 차원 kd 트리 은 위에서 설명한 쿼리로 정의 된 사각형 공간 영역에 속하는 모든 직원을 효율적으로 검색하는 데 도움이 될 수 있습니다.
3. n-body 문제 [5]
상호 중력 적 인력 하에서 움직이는 물체 모음의 움직임을 어떻게 효율적으로 시뮬레이션 할 수 있습니까?순진한 방법은 중력 인력 하에서 움직임을 시뮬레이션하기 위해 다른 모든 물체로 인한 물체 사이의 중력을 계산하는 것을 포함합니다. 더욱이, 우리는 O (n ^ 2) 시간이 걸리는 모든 객체에 대해 그것을해야 할 것입니다.
그러나 k-d 트리를 사용하여 공간을 분할하고 각 공간 분할에 대해 나머지 공간에 미치는 전체 효과를 파악할 수 있습니다. 아래는 알고리즘의 의사 코드 [6]입니다.
객체를 트리에 넣습니다. 트리의 맨 아래 수준에서 시작합니다. 트리의 깊이 d 에있는 모든 영역에 대해 : 자식이 나뭇잎이면 상호 작용을 직접 계산합니다. ” 다극 확장 “이를 상위 노드의 로컬 확장으로 변환하고 전달합니다. 레벨 d-1로 이동합니다. 트리의 맨 위에 도달하면 트리 아래로 다시 돌아가 로컬 확장을 합산합니다.
4. 색상 감소 [7]
풀 컬러 이미지를 표현하기 위해 256 색을 선택하는 지능적인 방법?
순진한 방법은 가장 자주 사용되는 색상을 선택하는 것일 수 있습니다.
그러나보다 효율적인 방법은 RGB 값을 지정하고 이미지의 모든 색상을 포함하는 공간을 나누기 위해 3 차원 kd 트리를 구성합니다. k-d 트리의 구성은 리프 노드의 수가 256이되면 중지됩니다. 그러면 256 개 파티션 각각의 RGB 값의 평균을 사용하여 풀 컬러 이미지에 대한 256 색 팔레트를 얻을 수 있습니다.
참조 : [1], [2], [3] : http://en.wikipedia.org/wiki/Kd-tree [4] : 가장 가까운 이웃을 사용한 분류 [5], [6], [7] : kD 나무