Tree Data Structure

Quadtree

Quadtree는 사각형을 더 작은 사각형으로 나누는 것에서 인한다. 이처럼 사각형과 정제를 연관시키면서, 이것이 활용적인지 확인할 수 있다. 예를 들면 2D 탐색 또는 최적화 알고리즘에서 사용할 수 있다. 우선, 1개의 단위 사각형에서 루트 트리를 시작하여, 4개의 더 작은 사각형으로 분할한다. 각각의 새로운 사각형은 루트의 자식노드가 된다. 이 다음부터는 이러한 과정을 반복하면서 4개의 더 작은 사각형들을 계속 생산하며 자식 노드를 생성한다.

"As you move down the quadtree each square is divided into four smaller squares."

"The most abstract view emphasises the tree, but remember where the squares come from."

Octree

3D 에서 사각형은 큐브로 대체되어 더 작은 8개의 큐브로 공감을 분할한다. 이를 Octree라고 하며, oct는 8(여덟)을 의미한다.

"하나의 Octree를 분할하면, 8개의 하위 큐브가 생긴다." Octree는 QuadTree의 3차원 표현일 뿐이다! 각 노드는 딘일 큐브에 상응하며, 8개의 하위노드를 갑는다. 주의할 점은 모든 서브노드 큐브는 부모 큐브를 갖오 있다. Quadtree와 마찬가지로, Ocree는 데이터 포인터를 찾을 수 있지만, 3D에서는 매우 빠르게 찾을 수 있다. 이전과 마찬가지로 Octree를 평평하게 펴서 아래와 같이 그릴 수도 있다. 

---

Reference

[1] https://www.youtube.com/watch?v=OKiBmQ6ZNyU
[2] https://www.i-programmer.info/programming/theory/1679-quadtrees-and-octrees.html#google_vignette