6주차의 시작
새로운 주차가 시작되었습니다. 새로운 팀원분들과 일주일에 코어타임에 어떤 내용을 공부할지 이야기 했습니다. 컴퓨터 시스템 같은 경우 저는 8장 예외처리 부분을 맡아서 월요일 설명하기로 했습니다.
동주님이 알려주셔서 RB 트리를 크래프톤 정글 레포에서 가져와서 RB 트리 프로젝트 파일을 돌려보는 방법을 배웠다.
1. 새 터미널 창에 make test을 작성해 빌드하고
2. make clean으로 밀어야한다.(안그럼 도커 GCC처럼 새로운 패치가 적용이 안된다)
동주님이 조언하신 RB 트리 공부 방법은 다음과 같다.
AVL트리를 먼저 개념과 동작방식을 분석하고 (밸런스 트리랑 일반 트리랑) 어떻게 밸런스를 찾는지 알면,
RB트리를 들어가자. (특히나 로테이트 함수를 확인하면 된다. 어떤 형식인지 보는 것이 중요!)
9:45 ~ 15:00
오전 중에 5주차 BST 개념과 이동석 코치님의 C언어 수업을 정리했다. 다 못해서 점심 지나고 몇시간 정도 더 정리했습니다.
15:00 ~ 16:00
EC2에 18.04 우분투 버전을 설치하여 Remote ssh로 연결하여 구축하려 했지만 실패했다.
기존에 문제 되었던 설치 버전 문제는 Remote ssh 0.7 버전으로 해결했는데, 어째서인지 node나 server.sh 파일이 완전히 설치되지 못했고, 폴더는 중간까지 덮어쓰다가 충돌 나서 서버 실행이 안 된다.
모두 지우고 다시 설치해도 마찬가지이다.
나도 높은 버전의 리눅스를 깔고 그 위에 도커를 깔아서 쓰는 방식으로 바꿔야겠다.
16:30 ~ 22:00
AVL 트리에 대해서 공부하고 노션에 정리했습니다. 해당 내용은 따로 포스팅하도록 하겠습니다.
코어 타임을 하기 전에 RB 트리 삽입 부분 또한 공부를 하고 갔습니다.
22:00 ~ 24:00(팀원 코어타임)
Red를 삽입하는 이유는 무엇인가?
→ Black을 삽입하면 무조건 규칙 위반한다. (Black Depth가 무조건 안맞음)
Red를 삽입하면 위반 될 수도 안될 수도 있다.
왜 바이너리 서치의 리스트가 아니라 RB 트리의 트리 구조를 쓰는 이유가 무엇인가?
→ 배열을 트리처럼 쓰려면 정렬이 되어 있어야한다.
배열에서 정렬을 수행하려면 O(Nlog(N))의 시간 복잡도가 필요하고, 정렬해야 서칭할 수 있다.
반면에, 트리는 정렬없이 입력할 때부터 기본적으로 정렬해서 들어가서 O(logN) 만큼만의 시간복잡도만 생긴다.
N이 클수록 컴퓨터에서는 더 의미가 없을 만큼의 시간이 필요하다.
트리에서 밸런스를 맞추는 과정이 왜 필요한가?
→ 삽입 순서에 큰 영향을 받는다. 자칫하면 밸런스를 맞지 않아서 선형 리스트와 비슷하게 될 수도 있다.
이진 트리에서 어떻게 일정한 log(n)의 시간 복잡도가 나오는가?
→ 트리는 위에서 부터 N / 2^1, N / 2^2, N / 2^3 ~ N / 2^(n-1)이 된다. 이렇게 k번을 시행한 해당 값들을 다 더하면
이 와같이 나타낼수 있고 양변에 2^k을 곱해주면, 위 식은 2^k = N 과 비슷하고 마지막으로 양 변에 2를 밑으로 하는 로그를 취해지면, K = logN 이라는 시간 복잡도를 알 수 있습니다.
시행 횟수인 k를 고려하여 자료개수 N에 대한 시간 복잡도는 Big O 표기법으로 O(logN) 입니다.
먼저, RB Tree에 들어가기 전에 AVL Tree에 대해 알아야한다. 그 이유는 RB의 rotation의 기본이 AVL에 있기 때문이다.
AVL Tree
AVL Tree는 balance facter를 1 이하로 유지하면서 일정한 균형을 유지한다. 균형 유지시, 삽입 → 부모 → 조부모 의 순으로 해결한다. (해당 내용 위의 AVL 설명 참고)
RB 트리
RB트리를 왜 쓰는가?
색으로 연산을 해서 삽입을 해도 연산을 거의하지 않는다. 그러니까 AVL보다 삽입 속도 보다 빠르다. 그리고 규칙이 널널하다.
RB 5가지 규칙들
1. 모든 노드는 Red 또는 Black이다.
- 루트 노드는 Black이다.
- 모든 리프 노드(NIL)들은 Black이다.
→ NIL은 Null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드이다. - Red 노드의 자식은 Black이다.
→ Red가 연속적으로 나올 수 없다. - 모든 리프 노드에서 Black Depth는 같다.
→ 루트 노드에서 리프 노드까지 가는 경로에서 만나는 Black 노드의 개수가 같다.
삽입 규칙
- Red 초기화 삽입
- 리프노드에서 삽입(NIL)
삽입 방식
- 삽입에서는 5번은 지켜짐, 그러나 부모가 red일 때 문제가생긴다.(black일땐 문제가 안생김)
- 삼촌이 레드일때 색바꾸고 조부모(부모의 부모)의 경우도 재귀로 풀면된다.
그 후 루트까지 올라가서 검은색으로 스위칭 후 리턴 - else 삼촌이 블랙이면 부모와 조부모의 색을 바꾸고, 로테이션을 수행하면된다.
- LL 케이스일 경우 부모와 조부모의 색을 스왑한 후 right rotation을 수행하면된다.
삭제 방식은 내일 알아 보겠지만, 미리 몇개의 힌트를 들었다.
삭제시. red를 삭제할때 문제가 되지 않음 black을 삭제할 때 문제가 생긴다.
00:00 ~ 04:30
코어타임이 끝나고 코어타임 내용을 정리하고 삽입에 대해 이해가 완료되는 대로 코드를 작성해보겠다.
그리고 은수님과 함께 내가 배웠던 삽입 구현에 대해 서로 발표하며 다시 살펴 보았다.
혼자 해보니 어느정도 어떤 식으로 돌아가는지 알게 되었다.
