1. R트리 기초

R트리 2차원 이산의 공간 데이터를 효율적으로 저장하고 조회하는 다차원 인덱스 구조이다.

• 점, 다각형, 등…
• 모든 데이터는 MBR(minimum Bounding Rectangle, 최소 경계 사각형)으로 표시된다.

실제 Point 혹은 객체의 MBR이 들어감.

MBR

• 여러 점이나 객체들을 하나의 사각형으로 완전히 감싸는 가장 작은 사각형
• ex (1,1), (2,5), (6,3), (5,7)의 점이 있으면 MBR은 (1,1~6,7)

R트리의 설명 사각형이 한 MBR을 나타냄

단계	무슨 일이 일어나는가?	정확한 표현
1	리프 노드 L1에 점 e 삽입 → 5개(M+1) 됨	오버플로우 발생
2	L1의 5개 엔트리(a,b,c,d,e)를 두 그룹으로 분할	예: 그룹1 {a,b,e} → 새 노드 L1′ 그룹2 {c,d} → 새 노드 L2′
3	기존 L1은 L1′로 교체되고, L2′는 새로 생김	→ 부모 입장에서는 자식 노드가 1개 → 2개로 늘어남
4	부모 노드의 해당 엔트리 1개가 → 두 개의 새로운 엔트리로 바뀜	부모 노드의 엔트리 수가 +1 증가
5	부모 노드도 이제 M+1이 되면 또 같은 과정 반복	부모도 split → 할머니 노드의 엔트리도 증가 → …
6	이 과정이 루트까지 올라가서 루트마저 split되면?	루트가 둘로 쪼개지고 새로운 루트가 생겨서 트리 높이가 +1 증가

엔트리

• R트리 한 노드안에 들어가는 한 칸의 데이터
• 엔트리는 MBR과 그 안의 점들을 포함한다.

노드

    private static class Node{

        boolean isLeaf; //리프 노드인지에 대한 변수

        List<Entry> entries; //엔트리에 대한 정보.

        Rectangle nodeMbr;      //해당 노드를 감싸는 MBR

        public Node(boolean isLeaf) {

            this.isLeaf = isLeaf;

            this.entries = new ArrayList<>();

            this.nodeMbr = null;

        }

    }

엔트리

    private static class Entry{

        Rectangle mbr;

        Point point;

        Node child;

        public Entry(Rectangle mbr, Point point, Node child) {

            this.mbr = mbr;

            this.point = point;

            this.child = child;

        }

    }

삽입

1. 적합한 리프를 찾는다.
   1. point를 넣었을 때 가장 덜 커지는 엔트리(사각형의 면적 증가량)을 찾아 계속 내려간다.
   2. 만약 면적 증가량이 둘다 같으면 두 MBR중 더 작은 면적을 선택
2. 해당 리프노드에 새 엔트리를 추가
3. 최대 엔트리 수: M(사용자가 정해줌) 이 넘어가면, MBR들이 들어있는 노드를 두개의 새로운 노드로 쪼갠다.

ex) 루트노드안의 엔트리 4개중 내부 노드안의 엔트리 → 리프노드 L1(a,b,c,d)일때

단계	무슨 일이 일어나는가?	정확한 표현
1	리프 노드 L1에 점 e 삽입 → 5개(M+1) 됨	오버플로우 발생
2	L1의 5개 엔트리(a,b,c,d,e)를 두 그룹으로 분할	예: 그룹1 {a,b,e} → 새 노드 L1′
그룹2 {c,d} → 새 노드 L2′
3	기존 L1은 L1′로 교체되고, L2′는 새로 생김	→ 부모 입장에서는 자식 노드가 1개 → 2개로 늘어남
4	부모 노드의 해당 엔트리 1개가 → 두 개의 새로운 엔트리로 바뀜	부모 노드의 엔트리 수가 +1 증가
5	부모 노드도 이제 M+1이 되면 또 같은 과정 반복	부모도 split → 할머니 노드의 엔트리도 증가 → …
6	이 과정이 루트까지 올라가서 루트마저 split되면?	루트가 둘로 쪼개지고 새로운 루트가 생겨서 트리 높이가 +1 증가

탐색

주어진 사각형Q에 대해서 Q와 겹치는 모든 점을 찾는 과정

1. 루트노드부터 조회 시작
2. Q와 겹치는 MBR이 있으면 그 엔트리를 따라 내려간다.
3. 최소 엔트리로 내려간 후 해당 엔트리 안에서 들어가는 점이 어떤 것인지 확인해야할 필요가 있음.

탐색 구현

    @Override

    public Iterator<Point> search(Rectangle rectangle) {        //반환값이 이터레이터

        // TODO 탐색함수 구현

        //  1. 여기서 포인터 리스트 리턴

        //  2. 만약 루트가 없거나, 엔트리가 없다면 빈이터레이터 리턴

        //  3. 점 구하는 함수 부르고, 돌아오면 해당하는 리스트 리턴

        if(root == null || root.entries.isEmpty()) return Collections.emptyIterator();

        List<Point> result = new ArrayList<>();

        searchPoints(root, rectangle, result);

        return result.iterator();

    }

점 탐색(재귀적으로 구현)

private void searchPoints(Node node, Rectangle rectangle, List<Point> result) {

        //TODO 재귀 탐색 함수 구현

        // 1. 받아온 사각형에 엔트리들 순회하며, 겹치는 mbr 탐색

        // 2. 리프노드면 mbr의 포인트가 사각형에 들어오는지 확인

        // 3. 포함되면 결과값에 추가

        for(Entry entry : node.entries){

            if(intersects(entry.mbr, rectangle)){       //사용자가 그린 사각형에 MBR이 겹치는 지 확인

                if(node.isLeaf){                //그게 리프노드라면

                    if(entry.point != null && contains(rectangle, entry.point)){    //entry의 포인트들이 사각형에 들어오는지 확인

                        result.add(entry.point);        //있으면 결과값에 추가

                    }

                }

                else{       //내부노드라면

                    if(entry.child != null){    //만약 자식노드가 존재한다면

                        searchPoints(entry.child, rectangle, result);   //재귀

                    }

                }

            }

            //MBR이 겹치지 않으면 다음 MBR로 넘어감

        }

    }

intersects함수와 contain함수의 경우 사각형끼리 겹치는지, 사각형 안에 점이 들어오는지 확인하는 함수이다.

R트리의 이용

R트리의 경우 내 위치에서 몇 미터의 거리에 있는 건물이 어디인지 찾는 매우 빠른 알고리즘이다.

• 따라서 네비게이션, 지도 등에 사용할 수 있다.

일반적으로 찾을 경우 점들을 찾아가며 하나하나 위치를 판별해주어야 하지만, B트리와 비슷하게, 자신에서 가장 가까울수 있는 점들만 빠르게 탐색 가능하다는게 장점이다.