[Red Black Tree] 1. 리눅스 C 개발 환경 구성 / RB Tree 이해

1. 리눅스 C 개발 환경 구성 / RB Tree 이해

2. 파이썬으로 RB Tree 구현

3. C언어 기초 문법 공부

4. 파이썬으로 작성된 RB Tree를 C 코드로 번역

5. C에서 추가적으로 구현해야 할 부분(포인터 사용, 메모리 할당 및 삭제 등) 공부 후 구현

6. testcase 검사 후 에러 부분 보수

 

 

Ubuntu 20.04 LTS (x86_64) 환경을 구성하기 위해서 WSL2 가상머신을 이용했다.

WSL2를 쓰면 패키지 빌드 중 몇가지 에러가 뜨지만 구글링하면 다 나와서 쉽게 해결 가능하다.

 

AWS EC2를 이용해도 되지만 로컬에서 하는게 취향에 맞는다.

github도 팀원과 공유가 필요할 때만 쓰고 코드들은 전부 하드에 정리해두고 있다.

필요한건 전부 손 닿는 위치에 두고싶은 느낌

 

 

RB트리는 이진 탐색 트리의 일종이다.

보통의 이진 탐색 트리는 대소관계에 의해 새 노드의 위치가 결정되어서, 평균적으로는 logn의 시간복잡도를 가지지만 삽입되는 노드의 값이나 순서가 운이 나쁠 경우 최악 n의 시간복잡도를 가진다.

RB트리는 각 노드에 Red or Black의 색을 부여해 이 단점을 보완하고, 트리의 깊이를 logn 선에서 유지한다.

각 노드에 색을 부여하고, 색에 따라 재정렬이 이루어지는 등 일반적인 이진 탐색 트리에 비해 삽입과 삭제시 거쳐야할 과정이 많다. 규칙은 위키에 잘 나와있다.(https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC)