쿼드 트리 : 컴퓨터 과학자 라파엘 핑클, 존 벤틀리가 제안한 원래 쿼드 트리를 기반으로 만들어진 2차원 자료 구조 유형.

• 각 레벨에서 2차원 노드를 4개의 하위 사분면으로 분할.

여서는 데이빗 앤더슨이 제안한 균일 쿼드 트리에 초점.

1. 쿼드 트리

큔일 쿼드 트리는 트리의 분기 구조를 격자에 도입한다.

• 트리의 각 노드는 공간의 각 영역을 나타낸다.
• 루트 노드는 트리가 다룰 전체 공간과 그 공간에 포함되는 모든 점을 나타낸다.
• 각 노드는 4개의 동일한 크기 사분면으로 분할되며, 비어 있지 않은 사분면마다 노드가 할당된다.
• ‘균일’이라는 말은 노드가 공간을 똑같은 크기의 하위 공간으로 분할한다는 사실을 나타낸다.

# QuadTreeNode 구조체는 2D 공간을 분할하여 포인트를 저장하는 쿼드 트리(Quad Tree) 노드를 정의합니다.

QuadTreeNode {
    # 노드가 리프(leaf)인지 여부를 나타냅니다.
    Boolean: is_leaf

    # 노드 내의 포인트 개수를 저장합니다.
    Integer: num_points

    # 노드의 공간 경계를 정의하는 좌표 (x 및 y의 최소 및 최대 범위)
    Float: x_min
    Float: x_max
    Float: y_min
    Float: y_max

    # 자식 노드(4개의 QuardTreeNodes 배열)
    Matrix of QuardTreeNodes: children

    # 노드에 포함된 포인트 배열 (리프 노드일 경우만 유효)
    Array of Points: points
}

각 점에 대해 간단한 복합 자료 구조를 사용

Point {
	Float: x
	Float: y
}

기술적으로 노드의 공간 경계를 명시적으로 저장할 필요는 없다.

• 대신 루트 노드의 경계와 분할 순서로부터 각 노드의 경계를 도출할 수 있다.