Red - Black Tree
๋ ๋ ๋ธ๋ ํธ๋ฆฌ
https://ko.wikipedia.org/wiki/๋ ๋-๋ธ๋_ํธ๋ฆฌ
๋ ๋-๋ธ๋ ํธ๋ฆฌ - ์ํค๋ฐฑ๊ณผ, ์ฐ๋ฆฌ ๋ชจ๋์ ๋ฐฑ๊ณผ์ฌ์
๋ ๋-๋ธ๋ ํธ๋ฆฌ(red-black tree)๋ ์๊ฐ ๊ท ํ ์ด์ง ํ์ ํธ๋ฆฌ(self-balancing binary search tree)๋ก์, ๋ํ์ ์ผ๋ก๋ ์ฐ๊ด ๋ฐฐ์ด ๋ฑ์ ๊ตฌํํ๋ ๋ฐ ์ฐ์ด๋ ์๋ฃ๊ตฌ์กฐ๋ค. 1978๋ ๋ ์ค ๊ท๋ฐ์ค(Leo J. Guibas)์ ๋ก๋ฒํธ
ko.wikipedia.org
์ด์ง ํ์ํธ๋ฆฌ์ ํ ์ข ๋ฅ
BTS์ worst case์ ๋จ์ ์ ๊ฐ์ - ์ค์ค๋ก ๊ท ํ์ ๋ง์ถ๋ฉฐ ํธํฅ๋ ํธ๋ฆฌ๊ฐ ๋์ง์๋๋ก ํ๋ค.
์ต์ ์ ๊ฒฝ์ฐ์๋ ์๊ฐ๋ณต์ก๋๊ฐ O(logN)
๊ท์น
- ๋ ๋์ ๋ธ๋์ผ๋ก๋ง ์ด๋ฃจ์์ง๋ค.
- ๋ฃจํธ ๋ ธ๋๋ ๋ธ๋์ด๋ค.
- nil๋ ธ๋๋ ๋ธ๋์ด๋ค.
- ๋ ๋์ ์์์ ๋ ๋๋ง ์ฌ์์๋ค.
- ์์์ ๋ ธ๋์์ ์์ nil ๋ ธ๋๊น์ง ๊ฐ๋ ๊ฒฝ๋ก์ ๋ธ๋ ๋ ธ๋์ด ๊ฐ์๋ ๊ฐ๋ค. (์๊ธฐ์์ ์ ์ธ)
๊ท ํ์ ๋ง์ถ ํธ๋ฆฌ์์ ๋ ์๋ ๊ฐ ๊ฐ์ ์์ ๊ฐ์ง๋ ๋ถ๋ชจ์ ๋ ์๋ ์ ์์ ๋ฐ๊ฟ์ค๋ 5๋ฒ ์์ฑ์ ์ ์งํ๋ค.
Black height
์์์ ๋ ธ๋์์ ์์ nill๋ ธ๋๊น์ง ๊ฐ๋ ๊ฒฝ๋ก์ ๋ธ๋ ๋ ธ๋์ ๊ฐ์
ํ์
ํ์ ์ ํ๋ ์ด์ ๋ ํธํฅ๋ ํธ๋ฆฌ๊ฐ ๋์ง์๊ฒ ํ๊ธฐ์ํด ๊ฐ์ ๋๊ธฐ๋ ค๋๋ฐ BST ํน์ง ๋ํ ์ ์งํ๋ฉด์ ๋๊ธฐ๊ธฐ ์ํด ํ์ ์ ์ฌ์ฉํ๋ค.
์ฝ์
- ์ผ๋ฐ์ ์ธ BST(์ด์งํ์ํธ๋ฆฌ)์ ๋์ผํ๊ฒ ์ฝ์
์ฝ์ ํ๋ ๋ ธ๋์ด ์์์ ํญ์ red๋ก ํ๋ค. >> 5๋ฒ ๊ท์น์ ์ ์งํ๊ธฐ ์ํด
- ์ฝ์ ํ ์๋ฐ ์ฌ๋ถ ํ์ธ ํ ๊ท ํ ๋ง์ถ๊ธฐ - 4,2๋ฒ ๊ท์น ์๋ฐ ๊ฐ๋ฅ
1. 4๋ฒ ์์ฑ์๋ฐ์ ๋ฐ๋ฅธ 3๊ฐ์ง case
case 3 : ์ฝ์ ํ ๋ ธ๋๊ฐ ๋ถ๋ชจ์ ์ผ์ชฝ ์๋ ์ผ๋ ๋ถ๋ชจ๋ red์ด๋ฉฐ ํ ์๋ฒ์ง์ ์ผ์ชฝ ์๋ & ์ผ์ด ๋ ธ๋๊ฐ black ์ผ๋
๋ถ๋ชจ์ ํ ์ด๋ฒ์ง์ ์์ ๋ฐ๊ฟ์ค ๋ค์ ํ ์๋ฒ์ง ๊ธฐ์ค์ผ๋ก ์ค๋ฅธ์ชฝ์ผ๋ก ํ์
case 2 : ๋ถ๋ชจ์ ์ค๋ฅธ์ชฝ ์๋ ์ด๋ฉฐ(๊บฝ์ธ ๋ถ๋ถ), ๋ถ๋ชจ๋ red๊ณ ํ ์๋ฒ์ง์ ์ผ์ชฝ ์๋ ์ด๋ฉฐ ์ผ์ด๋ ธ๋๊ฐ black ์ผ๋
๊บฝ์ธ ๋ถ๋ถ์ ํผ์นํ(๋ถ๋ชจ๋ฅผ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ์ผ๋ก ํ์ ) case3๊ณผ ๋์ผํ๊ฒ ํด๊ฒฐํ๋ค.
case 1 : ์ผ์ด์ด black์ผ๋ (red๊ฐ ํ์ชฝ์ผ๋ก ๋ชฐ๋ ค์์ง์๋ค.)
์๋ ์ ์์ด ๋๋ค ๊ฐ์ผ๋ฉด ๋ถ๋ชจ์ ์๊ณผ ๋ณ๊ฒฝ๊ฐ๋ฅํ๋ค - ํธ๋ฆฌ์ ๊ท์น
2. 2๋ฒ ์์ฑ์๋ฐ์ ๋ฃจํธ ๋ ธ๋์ ์์ black์ผ๋ก ๋ณ๊ฒฝ
์ญ์
- ์ผ๋ฐ์ ์ธ BTS์ ๋์ผํ๊ฒ ์ญ์
์ญ์ ๋ ธ๋์ ์๋ ์ ์์ ๋ฐ๋ฅธ ํ์ธ
- ์๊ฑฐ๋ ํ๋๋ผ๋ฉด ์ญ์ ๋๋ ๋ ธ๋ ๋ณธ์ธ ์ ์ญ์
- ๋๋ช ์ด๋ฉด ์ญ์ ๋๋ successor(๋๋ณด๋ค ์์ ์ ์ค ์ ์ผ ํฐ ์)์ ์ ์ญ์
- ์ญ์ ํ ์๋ฐ ์ฌ๋ถ ํ์ธ ํ ๊ท ํ๋ง์ถ๊ธฐ
์ด๋ค ์์ด ์ญ์ ๋๋์ง์ ๋ฐ๋ผ ์๋ฐ์ฌ๋ถ ํ์ธ
- ์ญ์ ๋๋ ์์ด red์ผ ๊ฒฝ์ฐ ์ด๋ค ์์ฑ๋ ์๋ฐํ์ง ์๋๋ค.
- ์ญ์ ๋๋ ์์ด Black์ผ ๊ฒฝ์ฐ : 2,4,5 ๊ท์น ์๋ฐ ๊ฐ๋ฅ
๊ทธ ์ค 5๋ฒ ์์ฑ์ ํญ์ ์๋ฐํ๊ฒ ๋๋ค.
5๋ฒ ์์ฑ์ ๋ค์ ๋ง์กฑ์ํค๊ธฐ ์ํด์ ๋์ฒด๋ ธ๋์ extra black์ ๋ถ์ฌํ๋ค.
red and black์ ๊ฒฝ์ฐ : black์ผ๋ก ๋ฐ๊ฟ์ค๋ค. (4,5๋ฒ ์์ฑ ๋ชจ๋ ๋ง์กฑํ๊ฒ๋จ)
doubly black์ ๊ฒฝ์ฐ : ๋ ธ๋์ ํ์ ์ ์๊ณผ ํ์ ์ ์์์ ์์ ๋ฐ๋ผ 4๊ฐ์ง case
case 4 : ์ค๋ฅธ์ชฝ ํ์ ๊ฐ black์ด๊ณ , ๊ทธ ํ์ ์ ์ค๋ฅธ์ชฝ ์๋ ๊ฐ red์ผ๋
ํด๋น red๋ฅผ doublely black์๋ก ์ฎ๊ธดํ์ extra black์ ์ฎ๊ฒจ red and black์ ๋ง๋ค์ด ํด๊ฒฐํ๋ค.
(1) ํธ๋ฆฌ ๊ท์น์ ๋ฐ๋ผ C, E ์ D์ ์์ ๋ฐ๊ฟ red๋ฅผ D๋ก ์ฏ๊ธด๋ค. - C๊ฐ ๋ญ์ง๋ชจ๋ฅด๋๊น C์๊ฒ extra black์ ๋ถ์ฌํ๋ค.
(2) B์ D(red)์ ์์ ๋ฐ๊ฟ์คํ B๋ฅผ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ์ผ๋ก ํ์ ํ๋ค.
(3) A,C์ extra black์ B๋ก ์ฏ๊ฒจ์ค๋ค. B๊ฐ red and black์ ๋๋ฉฐ ํด๊ฒฐ๋๋ค.
case 3 : ์ค๋ฅธ์ชฝ ํ์ ๊ฐ black์ด๊ณ , ๊ทธ ์ผ์ชฝ ์๋ ๊ฐ red / ์ค๋ฅธ์ชฝ ์๋ ๊ฐ black ์ผ๋
ํ์ ์ ์ค๋ฅธ์ชฝ ์๋ ๋ฅผ red๊ฐ ๋๊ฒ ๋ง๋ค์ด์ case4 ์ ์ฉํ๋ค.
(1) C์ D์ ์์ ๋ฐ๊พผํ D๋ฅผ ๊ธฐ์ค์ผ๋ก ์ค๋ฅธ์ชฝ์ผ๋ก ํ์ ํ๋ค.
(2) case4๋ฅผ ์ ์ฉํ๋ค.
case 2 : ์ค๋ฅธ์ชฝ ํ์ ๊ฐ black์ด๊ณ , ํ์ ์ ๋ ์๋ ๋ black์ผ๋
doubly black๊ณผ ๊ทธ ํ์ ๋ฅผ black์ ๋ถ๋ชจ๋ ธ๋์๊ฒ extra black์ ๋๊ธด๋ค.
B์ ๋ ธ๋๊ฐ doubly black์ด ๋๋ค๋ฉด ๋ค์ ๋ฐ๋ณต
case 1 : ์ค๋ฅธ์ชฝ ํ์ ๊ฐ black์ธ ๊ฒฝ์ฐ
๋ถ๋ชจ์ ํ์ ์ ์์ ๋ฐ๊พธ๊ณ ๋ถ๋ชจ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ์ผ๋ก ํ์ ํ๋ค case ์ค ํ๋๋ก ํด๊ฒฐ
์ฐธ๊ณ ์๋ฃ
Introduction To Algorithms - ํ๋น์์นด๋ฐ๋ฏธ ์ถํ
์ ์ฐฌ์ ๊ต์๋ https://youtu.be/SHdYv41iCmE
์ฌ์ด์ฝ๋ https://youtu.be/2MdsebfJOyM
์ฝ๋
'SW์ฌ๊ดํ๊ต ์ ๊ธ > ๊ฐ๋ฐ์ผ์ง - TIL' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Week04] ์๊ณ ๋ฆฌ์ฆ - ๋นํธ ๋ง์คํน (2) | 2022.04.26 |
---|---|
[Week03] ์๊ณ ๋ฆฌ์ฆ - DFS / BFS ๋ฐฑ์ค ๋ฌธ์ (5) | 2022.04.21 |
[Week03] ์๊ณ ๋ฆฌ์ฆ - ์ ๋์จ ํ์ธ๋ (3) | 2022.04.20 |
[Week02] ์๊ณ ๋ฆฌ์ฆ - ํ (feat. python) (2) | 2022.04.14 |
[Week02] ์๊ณ ๋ฆฌ์ฆ - ์ด๋ถํ์ (5) | 2022.04.09 |
๋๊ธ