쿼드 트리 란 무엇입니까?

쿼드 트리는 4의 거듭 제곱을 기반으로하는 트리와 유사한 구조이며 데이터베이스에서 파일을 구성하는 데 사용됩니다. 각 부모 또는 시작 노드에는 4 개의 자식 노드가 있으며 각 자식에는 특정 양의 데이터가 있습니다. 데이터 한계가 경계를 넘어 서면 해당 노드에서 4 개의 하위 항목이 만들어집니다. 두 가지 주요 쿼드 트리 구조가 있습니다. 영역과 포인트 트리는 각각 디자인이 약간 다릅니다. 쿼드 트리는 데이터베이스와 함께 가장 많이 사용되지만 2D 이미지의 픽셀은 항상 네 부분으로 분리 될 수 있기 때문에 2D 이미지의 픽셀을 찾는 데 사용할 수 있습니다.

모든 나무와 같은 구조는 부모 또는 가지, 노드와 자식 또는 잎 노드로 만들어집니다. 부모는 시작점이며 광범위한 범주 기반 데이터를 포함하고 자식은 파일과 문서를 보유합니다. 쿼드 트리에서 모든 부모에는 4 명의 자식이 있어야합니다. 4 명의 자녀가 있어야하지만 모든 자녀가 데이터를 포함 할 필요는 없습니다. 없는 노드는 널 노드라고합니다. 이러한 널 노드는 종종 정체 상태를 유지하고 데이터를 기다립니다.

쿼드 트리의 각 자식 노드에는 데이터 제한이 있습니다. 이 한계는 일반적으로 전체 데이터베이스 크기로 정의됩니다. 정보가 너무 많아 한계를 넘어 설 경우 하위 노드는 기본적으로 출산을 통해 상위 노드가되어 추가 데이터를 모두 차지하는 하위 노드 4 개를 만듭니다. 일반적으로이 생성에는 하나 또는 두 개의 널 노드가 있지만 이는 노드에있는 데이터의 양에 따라 다릅니다.

영역과 점의 두 가지 주요 쿼드 트리가 있습니다. 영역 쿼드 트리는 4, 8 또는 16 파트와 같은 4의 거듭 제곱을 기반으로 전체 2D 영역을 파트로 분해하는 데 사용되며 종종 표현에 사용됩니다. 이 구조는 이미지 또는 데이터 필드 그래프에 가장 적합합니다. 포인트 버전은 이진 트리와 같으며 순서가 지정된 포인트에 가장 적합합니다. 이 변형은 노드가 흩어져있는 리전 버전과 달리 모든 노드가 튀어 나오는 중심점이 있기 때문에 진정한 트리입니다.

쿼드 트리의 가장 일반적인 용도는 데이터베이스를 분리하고 구성하는 것이지만 이것이 유일한 용도는 아닙니다. 이미지에서 특정 픽셀을 찾기 위해 만든 알고리즘은 일반적으로 쿼드 트리를 사용합니다. 이미지의 각 픽셀은 4 개의 동일한 부분으로 분리 될 수 있기 때문입니다. 이로 인해 쿼드 트리는 픽셀 검색에 고유하게 적합합니다.