Open SW-H opened 1 year ago
์๊ฐ ๊ท ํ ์ด์ง ํ์ ํธ๋ฆฌ๋ก์ ์ฐ๊ด ๋ฐฐ์ด ๋ฑ์ ๊ตฌํํ๋๋ฐ ์ฐ์ด๋ ์๋ฃ ๊ตฌ์กฐ (์๊ฐ ๊ท ํ ์ด์ง ํ์ ํธ๋ฆฌ : ๋ ธ๋์ ์ฝ์ ๊ณผ ์ญ์ ๊ฐ ์ด๋ฃจ์ด์ง ๋ ์๋์ผ๋ก ๊ท ํ ํธ๋ฆฌ๋ฅผ ์ ์งํ๋ ์ด์ง ํ์ ํธ๋ฆฌ - AVL, ๋ ๋-๋ธ๋ ํธ๋ฆฌ, ์ด์ง ํ)
โ๏ธ ๋ ๋-๋ธ๋ ํธ๋ฆฌ์ ์กฐ๊ฑด
$\quad$ (NIL : null leaf, ์๋ฃ๋ฅผ ๊ฐ์ง ์๊ณ ํธ๋ฆฌ์ ๋์ ๋ํ๋ด๋ ๋ ธ๋)
โ๏ธ ๋ฐ์ดํฐ ์ฝ์ ๊ณผ์
Double Red ํด๊ฒฐ ๋ฐฉ๋ฒ : Restructuring, Recoloring
Restructuring
๐ฝ ๋ ๋-๋ธ๋ ํธ๋ฆฌ(Red-Black Tree = RB Tree)
โ๏ธ ๋ ๋-๋ธ๋ ํธ๋ฆฌ์ ์กฐ๊ฑด
$\quad$ (NIL : null leaf, ์๋ฃ๋ฅผ ๊ฐ์ง ์๊ณ ํธ๋ฆฌ์ ๋์ ๋ํ๋ด๋ ๋ ธ๋)
โ๏ธ ๋ฐ์ดํฐ ์ฝ์ ๊ณผ์
Double Red ํด๊ฒฐ ๋ฐฉ๋ฒ : Restructuring, Recoloring
Restructuring