Repository
https://github.com/Jinops/red-black-tree
개요
산업경영알고리즘 수업을 들으며, DP, 최소신장트리, 그래프 등 다양한 알고리즘과 자료구조를 배웠다. 이 수업의 자율과제로 레드블랙트리 구현 및 시각화를 하였는데, 수업시간에 개념만 다루고 실제 구현은 하지 않았던 내용이라 궁금증이 생겨 주제로 선정하였다.
이에 비롯해 트리의 시각화를 구현하였다. 수업 시간에 트리의 구조를 cui로만 보았을 때 느꼈던 불편함을 개선하고자 하였고, 같은 주제의 다른 결과물들도 크게 1,2개 이외에는 없어 유의미한 결과를 볼 수 있겠다 생각하였다.
다음은 코드 구조이다.
Red-Black Tree?
레드블랙트리는 이진탐색트리를 기반으로 한 탐색 알고리즘 및 자료구조이다. 일반적인 구조에서 더 나아가 Node에 Red/Black이라는 색상이 존재하며, 정해진 규칙에 따라 Node의 색을 결정, 또는 규칙을 만족하기 위해 Node 들의 위치를 변형시킨다.
레드블랙트리의 특성은 다음과 같다.
- 모든 노드는 red 혹은 black
- 루트 노드는 black
- 모든 리프 노드는 black
- 노드가 red면, 그 노드의 자식 노드는 black
- 각 노드로부터 경로에서 모두 같은 수의 black 노드 가진다
분업
총 2명의 팀원으로 해당 프로젝트를 진행하였다. 본인은 협업을 위한 구조 및 Class 설계, 삽입 구현, 시각화 및 최종 통합을 담당했다. 다른 팀원은 삭제 및 회전의 구현을 담당하였다.
과제의 요구사항에 수도코드 작성이 있어, 각자가 맡은 부분의 수도코드도 작성하였다.
알고리즘 구현
알고리즘 구현 자체는 참고자료들이 있어 크게 어렵지 않았다. 다만 Tree를 별도의 Class로 만들지에 대해 시행착오가 있었다.
무슨 말이냐 하면, 이전에 이진검색트리를 구현할 때에는 Node Class 하나에 left, right 자식을 다시 Node로 넣으므로써 최초 1개의 Node가 모든 하위 Node들을 참조할 수 있었다. 그러나 Red-Black Tree에서는, Rotate가 일어난 뒤에는 기존의 최상위 Node가 하위로 내려갈 수도 있다. 이 부분을 캐치하고 Tree Class를 추가적으로 만들어야 하는 이유를 두 팀원이 이해하는 과정이 필요했었다.
그 밖에 코드를 체계화 및 다른 공개된 코드와 차별화하기 위해 기능에 따른 상속 관계를 주기도 하고, Red Black Tree를 모듈화하는 등 소소한 개선을 통해 파이썬의 OOP에 한 발 더 가까워질 수 있었다.
시각화
Graphviz를 이용해 트리를 이미지화하고, PyQt5 라이브러리를 이용해 GUI를 만들었다. 비중이 크진 않지만 디자인에도 신경을 썼다. 그 외 삽입, 삭제 및 회전(Rotate) 과정을 보여주기 위해 이미지를 temp 폴더에 저장하여 관리하도록 하였다.
결과
학점도 학점이지만, 부끄러울 정도로 교수님께서 극찬을 해주셨다. 생각하기로는 1. 수업에 적절한 주제 선정(타 팀은 대부분 머신러닝 관련 기법을 선정했다), 2. 수업 시간 배운 내용으로부터의 확장, 3. 높은 완성도 세 가지가 주된 이유인 것 같다. 교수님께서 내년 수업 때 사용하고 싶다고 말씀을 해주셨는데, 정말 활용된다면 좋을 것 같다.
후속
Readme를 좀 더 길게 작성했다. 정확히는, 혹시 내년도 수업에 활용되거나 누군가 검색으로 쓰고자한다면, 환경 셋팅부터 실행까지 설명을 보고 바로 사용할 수 있는 것을 목표로 하였다.