[자료구조] 쿼드트리 (QuadTree)
쿼드트리 특징 -degree가 4인 트리(각 사분면에 속하는 요소가 한 개일때까지 나눈다) -performance: O(log4n) -불균형 트리 위의 쿼드 트리의 노드를 각 사분면 별로 mapping해서 트리형식으로 표현하면 아래와 같다. (왼쪽부터 차례대로 1,2,3,4사분면) 쿼드트리에서 root노드는 실제로 존재하지 않지만 mapping하여 표현할 때는 root노드를 그려준다. 나뉘어진 사분면의 개수와 각 사분면에 있는 1의 개수를 세는 함수이다. char graph[25][25]; int region[625] = { 0, }; int quad(int i, int j, int n, int cnt) { graph[i][j] = 0; region[cnt]++; if (i - 1 >= 0 && grap..
자료구조
2022. 7. 12. 15:20
