week 04 {swjungle} {Red Black Tree}

INDEX

๊ตฌํ˜„ ๊ทœ์น™

๊ณผ์ œ์˜ ์˜๋„ (Motivation)

์ฐธ๊ณ ๋ฌธํ—Œ

CSAPP ์ฝ์„ ๊ณณ๋“ค

Before start...

์ผ์ฃผ์ผ์„ ์–ด๋–ป๊ฒŒ ๋ณด๋‚ผ์ง€์— ๋Œ€ํ•œ ๋ฉ”ํƒ€์ ์ธ ์œค๊ณฝ์„ ๋ณด์ž. ์Šคํ„ฐ๋””๋ฅผ ํ•˜๋˜, ์‹ค์ œ ๊ตฌํ˜„์€ ๊ฐœ์ธ์˜ ๋ชซ์ด๋ผ๊ณ  ํ•œ๋‹ค. ํƒํ—˜์ค€๋น„ ์ฑ•ํ„ฐ์— ๋Œ€๋žต์ ์ธ ์•„์›ƒ๋ผ์ธ์ด ์ฃผ์–ด์ง„๋‹ค.

๋‹น์žฅ ํ•ด์•ผํ•  ๊ฒƒ

ํƒํ—˜์ค€๋น„

์„ค๋ช…ํ•  ๊ฒƒ๋“ค์„ ๋‚˜๋ˆ ์„œ ๊ณต๋ถ€ํ•˜๊ณ  ๋Œ์•„์™€์„œ ์ €์‹œ๊ธฐ๋ฅผ ํ•œ๋‹ค. ๋‹ค ๊ฐ™์ด ๊ฐ™์€ ๋ฒ”์œ„๋ฅผ ๊ณต๋ถ€ํ•˜๊ณ  ๋‹ค ๊ฐ™์ด ๋ฐœํ‘œํ•œ๋‹ค.

์‹œ๊ฐ„ ๋งž์ถ”๊ธฐ (์˜ค์ „ 10์‹œ) ์ผ์š”์ผ ์ œ์™ธ -> ๋Šฆ์ž ์„ ์•ˆ ์ž๊ฒŒ ๋œ๋‹ค.

๊ธˆ์š”์ผ๊นŒ์ง€

RB-tree, malloc-lab์„ ๋™์‹œ์— ๊ณต๋ถ€ํ•˜๊ณ  Python์œผ๋กœ ๊ตฌํ˜„์„ ์‹œ๋„ํ•ด๋ณด๋Š” ๊ฒƒ์œผ๋กœ ๋ฌด์—‡์ด ํ•„์š”ํ•œ์ง€์— ๋Œ€ํ•œ ์ธ์‚ฌ์ดํŠธ๋ฅผ ์–ป์„ ์ˆ˜ ์žˆ์„ ๊ฒƒ์ด๋‹ค.

ํ† ์š”์ผ

์›”์š”์ผ

ํ™”์š”์ผ