rbtree3 [WEEK 06] 크래프톤 정글 1기 WIL - Weekly I Learned 크래프톤 정글에서의 일주일간 성장일지입니다. 매주 주말 업데이트 예정이며, 앞으로도 잘 부탁드립니다. WIL은 에세이 형태로 진행되며 기술적인 내용이 전무합니다. 일요일에 팀 스터디하죠, 이번 주차 과제는 Red Black Tree 구현이었다. 균형 이진 탐색 알고리즘으로, 지금까지 배운 알고리즘의 몇 배가 되는 코드 양이 필요했다. 해당 알고리즘을 학습하는 데 시간이 필요했다. 팀은 총 세명으로, 다행히 한 분이 C언어를 학습하신 경험이 있었다. 그분을 중심으로 팀 스터디 일정이 잡혔고, C언어 · RBTree · CS:APP 3장을 학습해야 했다. 나에게 있어서 '오마이갓 비상사태'였다. (클릭 시 재생 · 소리 주의) 뭘 먼저 학습해야 하는 거지? 형 포인터.. 2022. 12. 6. [알고리즘] RB Tree삭제 동작 원리 #2 한국외대 '신찬수' 교수님과 '쉬운 코드'님의 강의 자료를 참고하였습니다. 개념을 공부하고, 시뮬레이터를 활용하여 노드의 동작 원리를 이해한다. 하단의 링크는 rbtree visualization을 확인할 수 있는 링크이다. 참고하여 학습을 진행한다. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html Red/Black Tree Visualization www.cs.usfca.edu #1 레드 블랙 트리 삭제 방식 0. 삭제 전 RB 트리 속성 만족한 상태 1. 삭제 방식은 일반적인 BST와 동일 2. 삭제 후 RB 트리 속성 위반 여부 확인 - 어떻게 확인할 수 있는가 3. RB트리 속성을 위반했다면 재조정 4. RB 트리 속성을 다시 만족 RB.. 2022. 11. 26. [알고리즘] RB Tree개념과 삽입 동작 원리 #1 한국외대 '신찬수' 교수님과 '쉬운 코드'님의 강의 자료를 참고하였습니다. 개념을 공부하고, 시뮬레이터를 활용하여 노드의 동작 원리를 이해한다. 하단의 링크는 rbtree visualization을 확인할 수 있는 링크이다. 참고하여 학습을 진행한다. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html Red/Black Tree Visualization www.cs.usfca.edu #1 레드블랙 트리 기본 개념과 특징 1. 레드블랙 트리 개념 1. 이진 탐색 트리(BST)의 한 종류 2. 스스로 균형 잡는 트리 3. BST의 worst case의 단점을 개선 : worst case = 한 방향으로 편향된 이진탐색 트리 > O(N) 4. 모든 노드.. 2022. 11. 26. 이전 1 다음
