당연히 먼저 Question 모델과 Answer 모델에 추천기능에 사용될 속성을 추가해야한다.
pybo/models.py 에서 Question, Answer 모델에 voter 속성을 추가한다. 그런데 저상태로는 마이그레이션 시에 에러가 발생한다. User 모델에 연결된 속성이 author 와 voter 로 두 개이기 때문에 User 모델을 통해 Question 이나 Answer
인스턴스에 접근할 때 둘 중 어느것을 참조해야할지 모호해지기 때문이다.
이를 해결하기 위해 author 와 voter 속성에 각각 related_name 인자를 추가해줘야 한다. 이제 어떤 유저가 작성한 게시글을 볼 때는 user.author_question.all(), 추천한 게시글을 볼 때는 user.voter_question.all() 과 같이 표현할 수 있다.
모델 수정이 완료되었으니 makemigrations 와 migrate 명령어를 실행하여 마이그레이션을 수행해준다.
2. 게시글 추천
이제 본격적으로 게시글 추천 기능을 만들어야 한다. 먼저 게시글 상세페이지에 추천 버튼부터 생성해보자.
먼저 추천영역과 기존의 게시글 내용과 답글을 표시하던 영역을 분리하기 위해 더 큰 영역을 만들어 추천 영역을
col-1 속성으로, 기존 부분을 col-11 속성으로 하는 것으로 추천:기존내용의 비율이 1:11로 나타나도록 하였다.
추천 링크의 href 값을 #으로 하고 data-uri 인자를 넣은 것으로 알 수 있듯이 여기서도 자바 스크립트 코드를 사용하여
정말 추천할것인지 확인창을 띄울 것이다. 삭제를 위해 만들었던 코드에서 메시지 내용을 수정하고 .delete 를
.recommend 로 수정하는 것으로 간단하게 기능을 구현할 수 있다.
pybo/urls.py 에 vote_question 에 해당하는 url 매핑도 추가해준다. 이전 게시글에서 views.py 파일을 분리했기 때문에
아직 생성하진 않았지만 뷰 함수인 vote_question 이 정의될 vote_views.py 파일의 import 문을 작성하고 vote_views.py
에 정의된 뷰 함수임을 명시하며 매핑을 추가해준다.
그리고 실제로 views 디렉토리에 vote_views.py 파일을 위와 같이 작성한다. 추천 또한 로그인한 사용자만이 게시글마다
1인당 한번에 한해서 추천이 가능하도록 하며 본인이 작성한 게시글을 추천하려고 할 경우 에러메시지를 출력한다.
작업이 끝나면 게시글 상세 페이지로 리다이렉트 시켜준다.
이제 게시글 본문 옆에 받은 추천 수와 추천 버튼이 생겼음을 확인할 수 있다.
추천 버튼을 누르면 추천할 것인지 확인 메시지가 나타나며
본인의 게시글을 추천할 경우 에러메시지가 표시된다.
다른 계정으로 로그인하여 추천할 경우 정상적으로 추천수가 올라가는 것을 확인할 수 있다.
3. 답글 추천
게시글 추천을 이미 구현해보았으니 답글 추천을 구현하는 것도 간단하다. 빠르게 구현해보자.
모델의 수정은 이미 게시글 추천을 구현할 때 마쳐두었기 때문에 바로 추천 영역을 만들어준다. 게시글 때와 완전히
같은방식으로 작성하고 question.voter.count 를 answer.voter.count 로, data-uri 값에서 uri 매핑과 넘겨줄 id를
answer 에 해당하는 것으로 바꿔주면 된다.
pybo/urls.py 에 url 매핑도 추가해준다.
vote_views.py 에 vote_answer 함수를 위와 같이 구현해준다. 게시글 추천 함수에서 question 을 answer 로 바꿔주는
것만으로 완성이지만 redirect 시에 question_id 를 통해 게시글 상세 페이지로 이동해야 하기 때문에 answer.id 가
아니라 answer.question.id 를 넘겨주는 것에만 주의하면 된다.
이제 답글에도 정상적으로 추천기능이 동작하는 것을 확인할 수 있다.
4. 게시글 목록 페이지에서 추천수 표시하기
게시글 목록 페이지에서도 추천수가 표시되도록 수정해보자.
question_detail.html 에서 테이블 헤더에 추천 항목을 추가하고 badge 형태로 question.voter.count 를 표시하도록 한다.
수정하는 김에 가운데 정렬 해주는 것이 보기 좋은 항목들은 가운데 정렬하여 표시하도록 수정해주었다.
레드블랙 트리는 지난번에 다루었던 AVL 트리와 같은 자가 균형 이진 탐색 트리의 일종이다. 레드블랙 트리는
다음과 같은 조건을 만족한다.
모든 노드는 색을 가지고있으며 색은 붉은색 또는 검은색 중 하나이다.
루트 노드는 검은색이다.
모든 리프 노드(NIL)는 검은색이다.
붉은색 노드의 자식 노드는 검은색이다. => 붉은색 노드는 연속해서 나올 수 없다.
모든 리프노드에서 Black Depth가 같다. => 리프 노드에서 루트 노드까지 거슬러올라가며 만나는 블랙노드의 갯수가 모두 동일하다.
위 조건들을 만족함으로서 레드블랙 트리는 아주 중요한 특성을 가지게 된다. 모든 리프노드의 Black Depth가
같다면 그 사이에 붉은색 노드를 아무리 많이 끼워넣는다 해도 붉은색 노드는 연속으로 나올 수 없기 때문에
넣을 수 있는 붉은색 노드의 갯수는 (검은색 노드의 갯수 - 1) 개가 한계이다. 즉, 모든 리프노드의 깊이는
가장 얕은 리프노드의 깊이의 두 배를 넘을 수 없다. 이 특성 덕분에 AVL트리만큼은 아니어도 레드 블랙 트리는
상당히 균형잡힌 이진 탐색 트리가 된다.
2. 레드블랙 트리의 특징
AVL 트리와 마찬가지로 어떤 경우에도 삽입, 삭제, 검색에 O(logN)의 시간복잡도를 보장한다.
매 삽입/삭제마다 최악의 경우 많은 회전 연산이 발생하는 AVL 트리에 비해 삽입/삭제에 걸리는 시간이 비교적 적다.
많은 프로그래밍 언어의 해시맵이나 집합 등의 라이브러리를 구현하는데에 레드블랙 트리가 활용된다.
3. 삽입/삭제시 Double-Red 처리 알고리즘
레드블랙 트리는 삽입, 삭제 결과 발생한 규칙의 어긋남을 회전과 색변경을 통해 바로잡는다. 회전의 경우 AVL 트리에
사용했던 LL회전(right_rotation), RR회전(left_rotation)을 그대로 사용한다.
① 삽입
삽입 연산의 경우 문제의 발생여부를 아는것은 굉장히 간단하다. 삽입되는 노드는 기본적으로 붉은색 노드이기 때문에
삽입된 노드의 부모노드도 붉은색이라면 Double-Red 문제가 발생한다. 그리고 이 상태에서 문제해결은 삽입된 노드의 삼촌노드(부모 노드의 형제노드)의 색에 따라 두 가지 케이스로 나누어 진행된다.
Recoloring
삼촌노드의 색이 붉은색일 경우 발생
삼촌노드와 부모노드의 색을 모두 검은색으로 변경해준 다음 조부모노드(부모노드의 부모노드)의 색을 붉은색으로 변경해준다. 부모노드와 삼촌노드쪽 모두 검은색노드가 하나 늘어난 동시에 조부모노드가 붉은색이 되며 일괄적으로 하나씩 줄었기 때문에 balck depth에는 영향을 주지않는다.
다만 조부모 노드가 붉은색으로 바뀌면서 추가적으로 Double-Red 문제가 발생할 수 있기 때문에 조부모노드를 새로 삽입한 노드로 취급하여 DoubleRed 처리를 재차 실행한다.
즉, Recoloring은 한번 수행하고나서도 추가작업이 필요할 수 있다.
Restructuring
삼촌노드의 색이 검은색일 경우 발생
조부모노드 - 부모노드 - 삽입된 노드의 형태에 따라 회전 연산을 수행
LL 상태라면 조부모노드에 대해 right_rotation 수행 RR 상태라면 조부모노드에 대해 left_rotation 수행 LR 상태라면 부모노드에 대해 left_rotation 을 수행한 뒤 조부모노드에 대해 right_rotation 수행 RL 상태라면 부모노드에 대해 right_rotation 을 수행한 뒤 조부모노드에 대해 left_rotation 수행
Restructuring 의 경우 이 작업만으로 더이상의 추가적인 Double-Red 문제가 발생하지 않기 때문에 여기서 작업이 종료된다.
모든 작업이 종료되면 루트노드를 검은색으로 바꿔준다.
② 삭제
삭제연산은 조금더 복잡하다. 일반적인 이진탐색의 삭제연산의 경우 삭제할 노드의 좌측 서브트리중 최댓값 또는 우측 서브트리중 최솟값을 가져와 삭제된 노드를 대체하는 형태로 이뤄진다. 레드블랙트리는 그렇게 삭제가 이뤄진 후
규칙을 유지하기 위해 추가작업을 수행한다. 먼저 삭제된 노드 부분에는 문제가 발생하지 않는다. 삭제된 노드를 대체할 후임자 노드의 색을 삭제된 노드의 색으로 바꿔주면 되기 때문이다. 문제는 후임자 노드의 자리에서 발생한다.
삭제된 노드가 리프노드일 경우에는 삭제된 노드 자리를 대체한 NIL 노드가 C 노드가 되고 그 부모노드가 P 노드가
된다. C노드의 부모노드가 없는 경우에는 트리가 비어있는 상태이기 때문에 그대로 삭제연산을 종료한다.)
후임자 노드가 붉은색일 경우
후임자 노드가 붉은색이라면 사라지더라도 규칙에 아무 영향을 주지않는다.
후임자 노드가 검은색이고 후임자 노드의 한쪽 자식노드가 붉은색인 경우
후임자 노드가 검은색이어도 후임자 노드의 자식노드가 붉은색이라면 그 노드를 검은색으로 바꿔주면 문제가 간단히 해결된다.
후임자 노드와 후임자 노드의 한쪽 자식노드 모두 검은색인 경우
이 경우가 가장 복잡한 상황이다. 이 경우 후임자 노드의 한쪽 자식노드 C를 기준으로 그 부모노드 P, 형제노드 S, 가까운 조카노드 N1 과 먼 조카노드 N2 의 상태를 기준으로 다섯가지 케이스로 나누어 해결해나가야 한다. 여기서는 C가 P의 좌측 자식노드이고 S가 P의 우측 자식노드인 경우를 상정하여 설명한다. 만약 반대로 C가 P의 우측 자식노드인 경우에는 회전 방향을 반대로 해야한다.
케이스 1. P는 붉은색, S, N1, N2는 모두 검은색인 경우
P와 S의 색을 서로 맞바꾸는 것만으로 더이상의 추가작업 없이 간단히 해결할 수 있다.
다섯가지 케이스중 가장 간단한 케이스이다.
케이스 2. P, S, N1, N2 가 모두 검은색인 경우
S의 색을 붉은색으로 변경하는 것으로 C쪽과 S쪽 모두 검은색 노드가 하나씩 부족하도록 한다.
결과적으로 부모노드 P 기준으로 검은색노드가 하나 부족하게되어 P 노드에 문제를 떠넘길 수 있다.
C 를 P로, P를 P의 부모노드로 재설정하여 다시한번 해당하는 케이스를 찾아 작업을 진행하도록 한다
케이스 3. P, N1, N2는 검은색이고 S는 붉은색인 경우
P를 기준으로 left_rotation 을 수행한 뒤 P와 S의 색을 맞바꾼다. P의 색이 바뀌었기 때문에 바뀐 색상에 따라 다시한번 해당 케이스를 찾아 작업을 진행하도록 한다.
케이스 4. P의 색은 무관, S가 검은색이고 먼 조카노드 N2가 붉은색인 경우
P를 기준으로 left_rotation 을 수행한 뒤 P와 S의 색을 맞바꾼 뒤 먼 조카노드 N2를 검은색으로 변경한다.
케이스 5. P의 색은 무관, S가 검은색이고 가까운 조카노드 N1은 붉은색, 먼 조카노드 N2는 검은색인 경우
S를 기준으로 right_rotation 을 수행한 뒤 가까운 조카노드 N1과 S의 색을 맞바꾼다.
이 결과 케이스 4와 동일한 형태가 되니 계속해서 작업을 진행한다.
위 작업을 케이스 1 또는 케이스 4 작업을 수행하여 추가작업이 필요없어지거나 C가 루트노드에 도달하여 parent 노드가 존재하지 않을 때 까지 반복한다.
모든 작업이 끝나면 루트노드를 검은색으로 바꿔준다.
글을 작성하면서 레드블랙트리를 직접 구현해보았지만 적은 양의 데이터로 하나하나 삽입, 삭제를 수행했을 때는
정상적으로 작동하는 것으로 보였지만 대량의 데이터를 삽입/삭제 해보니 삭제연산중에 문제가 있어 오류가 발생하는
경우가 나타났다. 나중에 시간이 되면 처음부터 다시한번 구현해볼 필요가 있을 것 같다.
추가) 2021.10.13
좀더 알아보니 모든 노드가 좌우 자식노드로 검은색 NIL 노드를 가지도록 설계해야 구현이 쉬울 것으로 보여 설계를
처음부터 다시해보았다. 노드를 삽입할 때 삽입위치인 NIL 노드에 key값과 색상을 설정하고 좌우에 NIL 노드를 생성하여 붙이도록 했더니 삭제기능도 문제없이 작동하였다.