week 04 {swjungle} {Red Black Tree}
INDEX
- 0016 swjungle ๐ค
- ์ด์ง๊ฒ์ํธ๋ฆฌ red black tree | ๊ตฌํ ์ธํฐํ์ด์ค ํ์ธ๋ฐ๋.
- 4์ฃผ์ฐจ swjungle ์๋ด ํ์ด์ง
- rbtree-lab {GH}
- msambol/dsa/trees/red_black_tree.py {GH}
- missing-semester ์ฌ๋ฌ๋ถ์ CS ๊ต์ก์์ ๋๋ฝ๋ ํ๊ธฐ | CS ํ๊ธฐ์์ ๊ฐ๋ฅด์ณ์ฃผ์ง ์์ง๋ง ๊ฑฐ์ ํ์์ ์ผ๋ก ์์์ผ ํ๋ ์ฃผ์ ๋ค์ ๋ํ ๋ด์ฉ์ ๋ค๋ฃจ๊ณ ์์.
- 0015.1 CSAPP Third Edition Bryant, Randal E. O'Hallaron, David. ๐ป
๊ตฌํ ๊ท์น
src/rbtree.c
์ด์ธ์๋ ์์ ํ์ง ์๊ณ test๋ฅผ ํต๊ณผํด์ผ ํฉ๋๋ค.make test
๋ฅผ ์ํํ์ฌPassed All tests!
๋ผ๋ ๋ฉ์์ง๊ฐ ๋์ค๋ฉด ๋ชจ๋ test๋ฅผ ํต๊ณผํ ๊ฒ์ ๋๋ค.- Sentinel node๋ฅผ ์ฌ์ฉํ์ฌ ๊ตฌํํ๋ค๋ฉด
test/Makefile
์์CFLAGS
๋ณ์์-DSENTINEL
์ด ์ถ๊ฐ๋๋๋ก comment๋ฅผ ์ ๊ฑฐํด ์ค๋๋ค.
๊ณผ์ ์ ์๋ (Motivation)
- ๋ณต์กํ ์๋ฃ๊ตฌ์กฐ(data structure)๋ฅผ ๊ตฌํํด ๋ด์ผ๋ก์จ ์์ ๊ฐ ์์น
- C ์ธ์ด, ํนํ ํฌ์ธํฐ(pointer)์ malloc, free ๋ฑ์ system call์ ์ต์ํด์ง.
- ๋์ ๋ฉ๋ชจ๋ฆฌ ํ ๋น(dynamic memory allocation)์ ์ง์ ์ฌ์ฉํด ๋ด์ผ๋ก์จ ๋์ ๋ฉ๋ชจ๋ฆฌ ํ ๋น์ ํ์์ฑ ์ฒด๊ฐ ๋ฐ data segment์ ๋ํ ์ดํด๋ ์์น
- ๊ณ ๊ธ ์ธ์ด์์ ๊ธฐ๋ณธ์ผ๋ก ์ ๊ณต๋๋ ์๋ฃ๊ตฌ์กฐ๊ฐ ์ธ๋ถ์ ์ผ๋ก๋ ์ด๋ป๊ฒ ๊ตฌํ๋์ด ์๋์ง ๊ฒฝํํจ์ผ๋ก์จ ๊ณ ๊ธ ์ธ์ด ์ฌ์ฉ์์๋ ํจ์จ์ฑ ๊ณ ๋ ค
์ฐธ๊ณ ๋ฌธํ
- ์ํค๋ฐฑ๊ณผ: ๋ ๋-๋ธ๋ ํธ๋ฆฌ (์์ด)
- CLRS book (Introduction to Algorithms) 13์ฅ ๋ ๋ ๋ธ๋ ํธ๋ฆฌ - Sentinel node๋ฅผ ์ฌ์ฉํ ๊ตฌํ
- Wikipedia:๊ท ํ ์ด์ง ํธ๋ฆฌ์ ๊ตฌํ ๋ฐฉ๋ฒ๋ค
CSAPP ์ฝ์ ๊ณณ๋ค
- ์ปดํจํฐ์์คํ
๊ต์ฌ
- 3์ฅ: ํ๋ก๊ทธ๋จ์ ๊ธฐ๊ณ์์ค ํํ (ํนํ 3.4, 3.7, 3.8)
- 7์ฅ: ๋ง์ปค (ํนํ 7.1, 7.4, 7.9, ๊ทธ๋ฆผ 7.15)
- 8์ฅ: ์์ธ์ ์ธ ์ ์ด ํ๋ฆ (ํนํ 8.1, 8.5)
- 9์ฅ: ๊ฐ์๋ฉ๋ชจ๋ฆฌ (ํนํ 9.9, 9.11)
Before start...
์ผ์ฃผ์ผ์ ์ด๋ป๊ฒ ๋ณด๋ผ์ง์ ๋ํ ๋ฉํ์ ์ธ ์ค๊ณฝ์ ๋ณด์. ์คํฐ๋๋ฅผ ํ๋, ์ค์ ๊ตฌํ์ ๊ฐ์ธ์ ๋ชซ์ด๋ผ๊ณ ํ๋ค. ํํ์ค๋น ์ฑํฐ์ ๋๋ต์ ์ธ ์์๋ผ์ธ์ด ์ฃผ์ด์ง๋ค.
๋น์ฅ ํด์ผํ ๊ฒ
ํํ์ค๋น
- C์ธ์ด ๊ณต๋ถ,
- ๋ฌธ๋ฒ ๊ณต๋ถ ํ linked list๋ฅผ ์ด์ฉํ ใ ฃist, queue, tree ๊ตฌํ ๋ฑ ๋ค์ํ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ง์ ๊ตฌํํ๊ณ ๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ฅผ ๋ง๋ค์ด ๊ฐ๋ฉด์
- Linux/GCC ์ฌ์ฉ๋ฒ ์ตํ๊ธฐ,
- RB tree ์ด๋ก ,
- malloc/free ์ฌ์ฉ๋ฒ ํ์ , RB tree ๊ตฌํ ์์๋ก ์งํ
- rbtree-lab ๋ฆฌํฌ์ ๋ฉ์ดํฌํ์ผ์ ์๋
make test
๋ฅผ ์คํํ์ฌ ํต๊ณผํ๊ธฐ
์ค๋ช
ํ ๊ฒ๋ค์ ๋๋ ์ ๊ณต๋ถํ๊ณ ๋์์์ ์ ์๊ธฐ๋ฅผ ํ๋ค. ๋ค ๊ฐ์ด ๊ฐ์ ๋ฒ์๋ฅผ ๊ณต๋ถํ๊ณ ๋ค ๊ฐ์ด ๋ฐํํ๋ค.
์๊ฐ ๋ง์ถ๊ธฐ (์ค์ 10์) ์ผ์์ผ ์ ์ธ -> ๋ฆ์ ์ ์ ์๊ฒ ๋๋ค.
๊ธ์์ผ๊น์ง
- C์ ๋ํ ๊ธฐ๋ณธ๋ฌธ๋ฒ ํ์ต | 0017 C ๐
- static,
array, string, multi-dimension array, string array, pointer,structure, dynamic memory allocation, conditional compile, preprocessors
- static,
RB-tree, malloc-lab์ ๋์์ ๊ณต๋ถํ๊ณ Python์ผ๋ก ๊ตฌํ์ ์๋ํด๋ณด๋ ๊ฒ์ผ๋ก ๋ฌด์์ด ํ์ํ์ง์ ๋ํ ์ธ์ฌ์ดํธ๋ฅผ ์ป์ ์ ์์ ๊ฒ์ด๋ค.
ํ ์์ผ
- [v] malloc, calloc, realloc {C}, struct,
-
- CLRS book 13์ฅ ๋ ๋๋ธ๋ ํธ๋ฆฌ์ ์ผํฐ๋ ๋ ธ๋๋ฅผ ์ฌ์ฉํ ๊ตฌํ ์ฐธ์กฐํ ๊ฒ
์์์ผ
ํ์์ผ
- [ ]