PlanB의 백엔드 엔지니어링

Binary search tree(이진 탐색 트리)는 아래의 전제조건들이 존재하는 이진 트리다.

• 모든 노드의 값은 유일하다.
• 값들은 전순서가 있다(임의의 두 원소의 비교가 가능하다).
• 어떤 노드의 왼쪽 서브트리는 그 노드보다 작은 값을 가진 노드들로 이루어져 있다.
• 어떤 노드의 오른쪽 서브트리는 그 노드와 같거나 큰 값을 가진 노드들로 이루어져 있다.
• 좌우 서브트리는 각각이 이진 탐색 트리여야 한다.

탐색

이진 탐색 트리에서 값 x를 가진 노드를 탐색하고자 할 때, 트리에 해당 값을 가진 노드가 존재하면 해당 노드를 반환하고, 존재하지 않으면 NULL을 반환한다고 가정해 보자.

• 값이 root node와 일치하는 경우, root node를 반환한다.
• x가 root node보다 작은 경우, 왼쪽 서브트리에서 재귀적으로 탐색한다.
• x가 root node보다 큰 경우, 오른쪽 서브트리에서 재귀적으로 탐색한다.
• 더이상 탐색할 서브트리가 없다면, NULL을 반환한다.

기본적인 탐색 알고리즘인 이진 탐색과 매우 유사하다.

삽입

• 삽입을 하기 전, 탐색을 수행한다.
• 탐색을 모두 마친 뒤, 삽입하려는 key와 일치하는 노드가 존재하면 삽입에 실패한다.
• 일치하는 노드가 존재하지 않으면(위에 작성한 탐색 순서에 따라, NULL이 반환되면), 가장 마지막으로 탐색한 서브트리의 root node와 값을 비교한 뒤 작으면 왼쪽, 같거나 크면 오른쪽에 해당 노드를 삽입한다.

각 노드들은 값에 대해 unique해야 하기 때문에, 삽입 전 탐색 과정이 존재한다.

삭제

삭제도 삽입과 동일하게 먼저 탐색을 수행하고, 노드가 존재하는 경우에만 삭제를 수행한다. 삭제는 삭제 대상이 되는 노드의 자식 수에 따라 동작이 달라진다.

• leaf node 삭제 : 해당 노드를 단순히 삭제한다. 가장 단순한 형태의 삭제.
• child node가 하나인 노드 삭제 : 해당 노드를 삭제하고, child node를 그 자리에 대입한다.
• child node가 두 개인 노드 삭제 : 해당 노드를 삭제하고, 왼쪽 서브트리에 있는 값 중 가장 큰 값, 또는 오른쪽 서브트리에 있는 값 중 가장 작은 값을 parent node와 연결시켜 준다.

삽입과 삭제가 일어나는 경우, 트리의 한 쪽이 비대해지는 경우가 생긴다. 이로 인해 높이 균형이 맞지 않는(unbalanced) 이진 탐색 트리는, 높이 균형이 맞는(balanced) 이진 탐색 트리에 비해 탐색에 대한 평균 노드 접근 수가 높다. 이는 시간복잡도에 영향을 미치므로, 삽입과 삭제가 일어나는 경우 트리를 높이 균형이 맞도록 변형시켜 트리의 높이를 작게 유지하는 self-balanced binary search tree(자가 균형 이진 탐색 트리)라는 ADT가 있다. 따라서 다음 몇 개의 글에서 self-balanaced binary search tree를 구현하기 위한 이론들에 대해 더 깊게 알아볼텐데, 따라서 Red-black tree처럼 조금 더 우리에게 익숙한 이름들이 보일 것이다.

맨날 뭐 결정만 하느라 지쳤으니, 이제 드디어 조금이라도 생산적인 작업을 해보자. API 스펙 설계와 문서화 방식 결정인데, 우리가 여태까지 의사결정한 결과물들이 이 작업의 기반이 되어 도움을 줄 것이다. 여기로 다시 끌어와 보면,

• HTTP API 설계 원칙을 기반으로 API 스펙을 디자인하기로 했다.
• JSON을 직렬화 포맷으로 결정했다.
• Authorization 헤더로 인증 정보를 명시하기로 했다.
• 인증 스키마에 JWT 기반의 Bearer를 사용하기로 했다.

이번 챕터는 글이 꽤 길어질 것 같아서, 두 편으로 나눠 진행한다.

도입 이유

'뭔가 하기 전에는 설계부터 해야지!'라는 의미 없는 이유라면 시도조차 안 했을텐데, 이 과정이 필요한 이유가 좀 있다.

• 개발에 착수하기 전에 구조에 대해 고민할 시간이 생긴다.
• 어차피 API 스펙을 프론트엔드에게 전달할 때는 문서로 정리해야 한다.
• 실제로 로직을 작성하기 전에 스펙을 리뷰하는 단계가 생기고, 아직 코드를 작성하지 않았으니 변경 사항을 빠르게 반영할 수 있다.
• 문서를 착실하게 작성해 두면, 커뮤니케이션으로 낭비하는 시간이 줄어든다.

작업 - API 스펙 설계

일반적인 프로젝트라면 기획서, 기본적인 와이어프레임, UI처럼 기능 명세를 살펴볼 수 있을만한 산출물이 나오고 난 상태여야 한다. 하지만 우리 프로젝트 팀 멤버는 가상 인물이므로 산출물같은 게 없으니 게시판 서비스에 필요할만한 기능들을 대충 떠올려서 설계해보도록 하자. HTTP API 설계 원칙에 따라 진행할텐데, 사실 이게 표준이 따로 있는 것이 아니고 조직마다 설계 원칙이 다르다. 우리는 Heroku 플랫폼 API를 개발한 조직이 정리한 디자인 가이드를 참고하겠다. 한국어 버전도 있으니 한 번쯤 읽어보도록 하자. 어떤 디자인 가이드를 사용할지에 대해서도 의사결정을 따로 했으면 어떨까 싶기도 했는데, 다들 뭐 비슷한 소리만 해서 깔끔히 정리된 거 하나 선택해서 참고해도 큰 문제 없을 것이라는 판단이다. 표준이 없다면 규칙은 조직이 납득 가능한 선에서 정하기 나름이니 말이다.

설계를 얼마나 구체적으로 할 지는 사람마다 다르지만, 나는 그냥 기능마다 엔드포인트와 함께 간단히 한두줄 정도로 정리해보려 한다. 필자는 원래 이런 것들을 notion이나 bear같은 메모 도구로 정리하곤 하는데, 글을 써야 하니 여기에 정리하도록 하겠다. 참고로 엔드포인트는 HTTP method + URI를 의미한다.

작업

정리한 API 스펙은 다음과 같다. {...}과 같은 URI는 path parameter를 뜻한다.

• GET /check-duplicate/email/{email} : 이메일 중복체크 API
• POST /signup : 회원가입 API. ID는 이메일을 사용하며, 이메일로 확인 링크가 전송된다. 이메일/비밀번호/닉네임을 받는다.
• GET /verify : 회원가입 확인 링크 클릭 시 GET으로 호출하게 될 API. 이메일 전송 시 query string에 확인 링크의 ID를 담아 GET /verify?verify_id=am38gjbkeo같은 링크를 전달할 것이다. /verify/{verify_id}처럼 path parameter를 사용할 수도 있으나, GET 요청의 명시성을 늘리고 나중에 확인 링크에 더 많은 정보를 담게 될수도 있을테니 이렇게 했다.
• GET /auth : 로그인 API. JWT 포맷으로 인코딩된 access token과 refresh token을 발급한다.
• GET /refresh : access token refresh API. refresh token의 expire가 얼마 남지 않았다면 refresh token도 새로 만들어서 발급해 준다.
• POST /board/categories : 카테고리 생성 API
• GET /board/categories : 카테고리 목록 API
• GET /board/categories/{category_id}/posts : 특정 카테고리의 게시글 목록 API
• POST /board/categories/{category_id}/posts : 게시글 작성 API
• PATCH /board/posts/{post_id} : 게시글 수정 API
• DELETE /board/posts/{post_id} : 게시글 삭제 API
• GET /board/posts/{post_id}/content : 게시글 내용 API
• GET /board/posts/{post_id}/comments : 게시글의 댓글 목록 API
• POST /board/posts/{post_id}/comments : 댓글 작성 API
• DELETE /board/comments/{comment_id} : 댓글 삭제 API

모호함이 많다. 예를 들어, 게시글 목록 API에서는 페이지 개념이 들어갈 것인지, 페이지 당 게시글 갯수는 몇 개로 할 것인지, 회원가입 시 닉네임의 중복을 체크할 것인지, 비밀번호의 최소/최대 자릿수는 몇으로 할 것인지 등이다. 이런 건 기획 단에서 의사결정해 주어야 하는 부분이지만, 상황이 그렇지 않으므로 문서화 단계에서 적절히 이런 제약 사항들을 끼워넣을 것이다. API 처리 결과의 구분(이메일 중복 시 409, 게시글 삭제 권한이 없는 경우 403 등)도 문서화 단계에서 명시하겠다.

Tree의 순회는 트리에서 각각의 노드를 정확히 한 번만 방문하는 과정이다. Linked list나 array와 같은 선형 자료 구조는 논리적으로 한 가지의 순회 방법만이 존재하지만, 트리의 순회에는 많은 방법이 존재한다. 순회는 모든 n-ary tree에 대해 일반화될 수 있으나, 가장 자료가 많고 일반적인 binary tree의 순회에 대해서 알아보도록 하겠다.

순회

tree 내부의 tree를 sub-tree라고 부른다. 순회에는 이러한 sub-tree 개념이 등장한다.

전위(preorder) 순회(root-left-right)

• 현재 node를 방문한다.
• 왼쪽 sub-tree를 전위 순회한다.
• 오른쪽 sub-tree를 전위 순회한다.

전위 우선 순회는 깊이 우선 순회(depth-first traversal)라고도 한다. 전위 표기법에서 자주 사용된다.

중위(inorder) 순회(left-root-right)

• 왼쪽 sub-tree를 중위 순회한다.
• 현재 node를 방문한다.
• 오른쪽 sub-tree를 중위 순회한다.

후위(postorder) 순회(left-right-root)

• 왼쪽 sub-tree를 후위 순회한다.
• 오른쪽 sub-tree를 후위 순회한다.
• 현재 node를 방문한다.

왼쪽 sub-tree 순회-오른쪽 sub-tree 순회라는 순서는 고정이고, root node를 언제 방문하는지에 따라 전위, 중위, 후위로 나뉜다. sub-tree들을 동일한 order로 순회하므로 재귀적인 특성이 강하고, 실제로 코드에 옮길 때도 재귀함수를 사용한다.

sub-tree를 순회하는 구조라 순회의 대상이 계속해서 바뀌기 때문에 조금 헷갈릴 수 있으나, 아래의 사진을 보면 이해에 조금 도움이 될 수도 있다.

레벨 순서(level-order) 순회

이는 sub-tree 개념이 들어가지 않고, 낮은 level부터 왼쪽에서 오른쪽 방향으로 순회한다. 너비 우선 순회(breadth-first traversal)라고도 한다.

위 tree를 전/중/후위, 레벨 순서 순회 각각의 방식으로 순회하면,

• 전위 순회 : F-B-A-D-C-E-G-I-H
• 중위 순회 : A-B-C-D-E-F-G-H-I
• 후위 순회 : A-C-E-D-B-H-I-G-F
• 레벨 순서 순회 : F-B-G-A-D-I-C-E-H