[비교] Tree 구조 API 디자인

Intro

토이프로젝트 진행 중 트리 구조의 데이터를 서버에 저장해야 할 일이 생겼다.

저장 API를 구현하는 방식으로 아래의 2가지 방법이 떠올랐는데, 이 방법들의 장단점을 비교해보자.

 

1. 트리 구조 그대로 요청
2. 트리의 각 노드를 쪼개 배열 형태로 요청

---

트리 구조 그대로 요청

{
    "name": "test",
    "root": {
        "content": "node1",
        "child": [
            {
                "content": "node1-1",
                "child": [
                    {
                        "content": "node1-1-1",
                        "child": []
                    }
                ]
            },
            {
                
                "content": "node1-2",
                "child": [
                    {
                        "content": "node1-2-1",
                        "child": []
                    }
                ]
            }
        ]
    }
}

 

• Tree 구조 그대로 요청하기 때문에, Child에서 Parent 노드를 찾을 필요 없이 바로 저장 가능하다.
  즉, 시간복잡도가 O(n)이다.
• 재귀 호출이 필요하다.
  BFS를 사용하면 재귀호출 없이도 구현할 수 있지만, Queue에 Child 노드를 넣을 때 Parent 노드도 Pair 형태로 같이 넣고 빼야 하는 등 복잡하고 가독성이 떨어진다.

---

배열 형태로 요청

{
    "name": "test",
    "node_list": [
        {
            "id": 1,
            "content": "node1",
            "parent": null
        },
        {
            "id": 2,
            "content": "node1-1",
            "parent": 1
        },
        {
            "id": 3,
            "content": "node1-2",
            "parent": 1
        },
        {
            "id": 4,
            "content": "node1-1-1",
            "parent": 2
        },
        {
            "id": 5,
            "content": "node1-2-1",
            "parent": 3
        }
    ]
}

 

• Parent ID를 통해 부모 노드를 찾기 때문에, 부모 노드를 검색하는 과정에서 비용이 많이 소모된다.
  한 Child 노드가 Parent를 찾기 위해 모든 노드의 id를 참조하기 때문에, 시간복잡도가 O(n^2)가 된다.
• 재귀호출이 필요없다.
• 검색 API의 Response와 유사한 형태이기 때문에 일관성을 유지할 수 있다.

---

결론

이번 프로젝트는 전체 노드 수에 제한이 걸려있기 때문에, 시간복잡도가 O(n^2)인것에 대한 비용 증가가 그리 크지 않다.

때문에 성능을 조금 포기하고, 가독성과 일관성을 챙기는 2번 방식을 사용했다.

---

이 글은 고민을 정리한 글이기 때문에 주관적인 생각이 다소 포함되어있으며, 잘못된 내용이 포함되어있을 수 있습니다.

잘못된 부분이나 해결방안은 댓글로 남겨주시면 감사하겠습니다.