
์๋ ํ์ธ์ Foma ๐ป ์ ๋๋ค!
์ค๋์ ํธ๋ฆฌ ์๋ฃ๊ตฌ์กฐ ์ค ๊ท ํ ๋ํ์ (์ด๋ฆ ์์ฒด๊ฐ Balanced - Tree)์ธ B-Tree์ ๋ํด ์์๋ณด๊ฒ ์ต๋๋ค.
๋ฐ๋ก ์์ํ ๊ฒ์~
B-Tree์ ๋ฐฐ๊ฒฝ
B-ํธ๋ฆฌ(B-tree)๋ ๋ฐ์ดํฐ๋ฒ ์ด์ค์ ํ์ผ ์์คํ ์์ ๋๋ฆฌ ์ฌ์ฉ๋๋ ํธ๋ฆฌ ์๋ฃ๊ตฌ์กฐ์ ์ผ์ข ์ผ๋ก, ์ด์ง ํธ๋ฆฌ๋ฅผ ํ์ฅํด ํ๋์ ๋ ธ๋๊ฐ ๊ฐ์ง ์ ์๋ ์์ ๋ ธ๋์ ์ต๋ ์ซ์๊ฐ 2๋ณด๋ค ํฐ ํธ๋ฆฌ ๊ตฌ์กฐ์ด๋ค. - ์ํค ๋ฐฑ๊ณผ -
์ฆ, ์ด์ง ํธ๋ฆฌ๋ฅผ ์กฐ๊ธ ๋ ํจ์จ์ ์ผ๋ก ํ์ฅํ ์๋ฃ๊ตฌ์กฐ์์!
์ด์ง ํ์ ํธ๋ฆฌ๋ ์ต์ ์ ๊ฒฝ์ฐ O(n)์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ๊ธฐ ๋๋ฌธ์ ๊ทธ๊ฒ์ ์กฐ๊ธ ๋ ํจ์จ์ ์ผ๋ก ๋ง๋ ๊ฒ์ด
O(logn)์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ๋ AVL ํธ๋ฆฌ์์ต๋๋ค.
ํ์ง๋ง ๋ง์ฝ 2์ฒ๋ง๊ฐ์ ๋ฐ์ดํฐ๊ฐ ์๋ค๋ฉด log20,000,000 = 24 ์ฆ, ์ต๋ 24๋ฒ ํ์ํ๊ฒ ๋ฉ๋๋ค.
์ฌ๊ธฐ์ 24๋ฒ๋ณด๋ค ๋ ์ ๊ฒ ํ์ํ ์ ์์๊น? ๋ฅผ ์๊ฐํ๊ฒ ๋๋๋ฐ ๊ทธ๊ฒ ๋ฐ๋ก "๋ธ๋์น(์์)๋ฅผ ํ์ฅ์ํค์"์์ต๋๋ค.
์ฝ๊ฒ ์ค๋ช ํ๋ฉด ์ด์งํธ๋ฆฌ๋ ์์(๋ธ๋์น)์ด ๋ฌด์กฐ๊ฑด 2๊ฐ์์์?
๋์ "์์์ ์ฌ๋ฌ ๊ฐ ๊ฐ์ง๋ฉด์ ๋์ด๋ฅผ ์ค์ด์!" ํด์ ๋์จ ๊ฒ ๋ฐ๋ก B - Tree์ ๋๋ค.
๋ ธ๋๊ฐ ๊ฐ์ง ์ ์๋ ์ต๋ ์์์ ์๋ฅผ M์ด๋ผ๊ณ ํ๋ค๋ฉด M์ฐจ B-Tree๋ก ๋ถ๋ฆฌ๊ฒ ๋ฉ๋๋ค.
B-Tree ๊ท์น
B-Tree ์๋ฃ๊ตฌ์กฐ๋ฅผ ๊ตฌ์ฑํ๊ธฐ ์ํด์ ๋ช ๊ฐ์ง ๊ท์น์ด ์ฑ๋ฆฝํด์ผ ํฉ๋๋ค.
1. ๋ ธ๋ ์์ k๊ฐ์ ๋ฐ์ดํฐ๊ฐ ์๋ค๋ฉด ์์ ๋ ธ๋ ์๋ k+1๊ฐ์ฌ์ผ ํ๋ค.
์ด๊ธ๋๋ ์ โ

๋ง์กฑํ๋ ์ ๐๐ป

2. ๋ ธ๋ ์์ ๋ฐ์ดํฐ๋ ์ ๋ ฌ๋์ด ์์ด์ผ ํ๋ค.
์ด๊ธ๋๋ ์ โ

๋ง์กฑํ๋ ์ ๐๐ป

3. ์์ ๋ ธ๋์ ๋ฐ์ดํฐ๋ ๋ถ๋ชจ์ ๋ฐ์ดํฐ ๊ฐ์ ๋ฐ๋ผ ๋ฐฐ์น๋๋ค.
์์ ๋ ธ๋๋ค์ ๋ถ๋ชจ ๋ ธ๋์ ๋ฐ์ดํฐ n๋ฒ์งธ๋ณด๋ค ์์ ๊ฐ์ด ๋ฐฐ์น๋๊ณ ๋๋จธ์ง ํ ๊ฐ์ ์์ ๋ ธ๋์ ๋ง์ง๋ง ๋ ธ๋๋ณด๋ค ๋ ํฐ ๊ฐ์ด ๋ฐฐ์น๋ฉ๋๋ค.
์ด๊ธ๋๋ ์ โ
0๋ฒ์งธ ์์ ๋ ธ๋๋ ๋ถ๋ชจ์ 0๋ฒ์งธ ๋ฐ์ดํฐ์ธ 4๋ณด๋ค ์์์ผ ํ๊ณ ,1๋ฒ์งธ ์์ ๋ ธ๋๋ ๋ถ๋ชจ์ 1๋ฒ์งธ ๋ฐ์ดํฐ์ธ 10๋ณด๋ค ์์์ผ ํฉ๋๋ค.
2๋ฒ์งธ ์์ ๋ ธ๋๋ ๋ง์ง๋ง ๋ฐ์ดํฐ ๋ณด๋ค ๋ ํฐ ๊ฐ๋ค์ด ๋ฐฐ์น๋ฉ๋๋ค.

๋ง์กฑํ๋ ์ ๐๐ป

4. ๋ฃจํธ ๋ ธ๋๊ฐ ๋ฆฌํ ๋ ธ๋๊ฐ ์๋ ๊ฒฝ์ฐ ํญ์ 2๊ฐ ์ด์์ ์์์ ๊ฐ๋๋ค.
๋์ ์ โ

๋ง์กฑํ๋ ์ ๐๐ป

5. M์ฐจ B-Tree๋ผ๋ฉด ๋ฃจํธ ๋ ธ๋์ ๋ฆฌํ ๋ ธ๋๋ฅผ ์ ์ธํ๊ณ ์ต์ M/2๊ฐ ์ด์์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ง๊ณ ์์ด์ผ ํ๋ค.
๋ง์ฝ 4์ฐจ B-Tree๋ผ๋ฉด ์ต๋ 4๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ง ์ ์๊ณ 2(4/2)๊ฐ ์ด์์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ ธ์ผ ํฉ๋๋ค.
์ด๊ธ๋๋ ์ โ

๋ง์กฑํ๋ ์ ๐๐ป

6. ๋ชจ๋ ๋ฆฌํ ๋ ธ๋์ ๋์ด๋ ๊ฐ์์ผ ํฉ๋๋ค.
์ด๊ธ๋๋ ์ โ

๋ง์กฑํ๋ ์ ๐๐ป

7. ๋ฆฌํ ๋ ธ๋์ ๋ฐ์ดํฐ ์๋ M-1 ์ดํ์ฌ์ผ ํ๋ค.
3์ฐจ B-Tree๋ผ๋ฉด ๋ง์ง๋ง ๋ฆฌํ ๋ ธ๋ ์๋ 2๊ฐ ์ดํ์ฌ์ผ ํ๋ค.
์ด๊ธ๋๋ ์ โ

๋ง์กฑํ๋ ์ ๐๐ป

Search
B-Tree๋ฅผ ํ์ํ๋ ๋ฐฉ๋ฒ์ ๊ฐ๋จํฉ๋๋ค.
์ฐพ๊ณ ์ ํ๋ ๊ฐ๋ณด๋ค ๋ ํฐ ๊ฐ์ด ์๋ ์์น์ ์ธ๋ฑ์ค๋ฅผ ๊ฐ์ง ์์ ๋ ธ๋(์๋ค๋ฉด ๋ฐ์ดํฐ ์๋งํผ)๋ก ์ด๋ํด์ค๋๋ค.
๋ง์ฝ ์ฌ๊ธฐ์ 5๋ฅผ ์ฐพ๊ธฐ ์ํด์ ์ด๋ป๊ฒ ํด์ผ ํ ๊น์?

๋ฃจํธ ๋ ธ๋๋ถํฐ ํ์ํด์ค๋๋ค.
๋ฃจํธ ๋
ธ๋์ 6(0๋ฒ์งธ)์ด 5๋ณด๋ค ๋ ํฌ์ฃ ? 0๋ฒ์งธ ์์ ๋
ธ๋๋ก ์ด๋ํฉ๋๋ค.

0๋ฒ์งธ ์์ ๋ ธ๋ 2์ 4 ์ค์์ ๋ ํฐ ๊ฐ์ด ์์ผ๋ฏ๋ก 2๋ฒ์งธ(๋ฐ์ดํฐ ์) ์์ ๋ ธ๋๋ก ์ด๋ํด์ค๋๋ค.

Insert
์ฝ์ ํ๊ธฐ ์ํด์ 2๊ฐ์ง ๊ฒฝ์ฐ๊ฐ ์์ต๋๋ค.
1. ๋ฆฌํ ๋ ธ๋๊ฐ M-2๊ฐ ์ดํ์ธ ๊ฒฝ์ฐ
์ด ๊ฒฝ์ฐ์ ๊ทธ๋ฅ ์ฝ์ ํ๋ฉด ๋ฉ๋๋ค.
3์ฐจ B-Tree์ 10์ ์ฝ์ ํ๋ ๊ฒฝ์ฐ

10์ด ๋ค์ด๊ฐ ๊ณต๊ฐ์ด [9] 1๊ฐ ๋ฐ์ ์์ผ๋ฏ๋ก ๊ทธ๋ฅ ์ฝ์ ํด ์ค๋๋ค.

2. ๋ฆฌํ ๋ ธ๋๊ฐ M-1๊ฐ์ธ ๊ฒฝ์ฐ
์ฝ์ ํ ๋ค์ ์ค์๊ฐ์ ๊ธฐ์ค์ผ๋ก ๋ถํ ํ๊ณ ์ค์๊ฐ์ ๋ถ๋ชจ๋ ธ๋๋ก ํฉ์ณ์ง๊ฑฐ๋ ์๋ก์ด ๋ ธ๋๋ก ์์ฑ๋๊ณ
ํด๋น ์ค์๊ฐ์ ๋ฐ๋ผ์ ์์ ๋ ธ๋๊ฐ ๋ฐฐ์น๋ฉ๋๋ค.
์๋ 3์ฐจ B-Tree์ 17์ด ์ฝ์ ๋ ๊ฒฝ์ฐ

[14,15,16]๋ก 7๋ฒ์งธ ๊ท์น์ธ "๋ฆฌํ ๋ ธ๋๋ M-1์ด์ฌ์ผ ํ๋ค."์ ์ด๊ธ๋๊ฒ ๋ฉ๋๋ค.

๊ณ ๋ก 14,15,16์ ์ค์๊ฐ์ธ 15์ ๋ถ๋ชจ ๋ ธ๋๋ก ํฉ์นฉ๋๋ค.
์ฌ๊ธฐ์ 3๋ฒ์งธ ๊ท์น์ธ "์์ ๋ ธ๋์ ๋ฐ์ดํฐ๋ ๋ถ๋ชจ์ ๋ฐ์ดํฐ ๊ฐ์ ๋ฐ๋ผ ๋ฐฐ์น๋๋ค."์ ์ด๊ธ๋ฉ๋๋ค.

๊ณ ๋ก ๋ฐ์ดํฐ์ ๊ฐ์ ๋ง๊ฒ ๋ฐฐ์นํด์ฃผ๋ฉด ์๋์ ๊ฐ์ด B-Tree๊ฐ ์์ฑ๋ฉ๋๋ค.

Remove
์ญ์ ๋ฅผ ํ ๊ฒฝ์ฐ 2๊ฐ์ง ๊ฒฝ์ฐ๊ฐ ์กด์ฌํฉ๋๋ค.
1. ๋ฆฌํ ๋ ธ๋์ธ ๊ฒฝ์ฐ
1-1) ์ญ์ ํ๋ ค๋ ๋ฐ์ดํฐ๊ฐ ์๋ ๋ ธ๋์ ์๊ฐ ์ต์๋ณด๋ค ํฐ ๊ฒฝ์ฐ
๊ทธ๋ฅ ์ญ์ ํด์ฃผ๊ณ ์์ ๋ ธ๋๋ฅผ ๋ฐ์ดํฐ์ ๋ง๊ฒ ์ฌ๋ฐฐ์น ํฉ๋๋ค.
์๋ 3์ฐจ B-Tree์์ 17์ ์ญ์ ํ ๊ฒฝ์ฐ

[17,24]์ด 1(์ต์ M/2)๋ณด๋ค ํฌ๊ธฐ ๋๋ฌธ์ 17์ ์ญ์ ํ๊ณ ์์ ๋ ธ๋๋ค์ ์ฌ๋ฐฐ์น ํฉ๋๋ค.

1-2) ์ญ์ ํ๋ ค๋ ๋ฐ์ดํฐ๊ฐ ์๋ ๋ ธ๋์ ์๊ฐ ์ต์์ด๊ณ ํ์ ๋ ธ๋์ ์๊ฐ ์ต์๋ณด๋ค ๋ง์ ๋
์ญ์ ํ๋ ค๋ ๋ฐ์ดํฐ๋ฅผ ์ญ์ ํ๊ณ ์ญ์ ํ๋ ค๋ ๋ ธ๋์ ์ธ๋ฑ์ค๋ฅผ ๊ฐ์ง ๋ถ๋ชจ ๋ ธ๋์ ๋ฐ์ดํฐ๋ก ๋ฐ๊ฟ์ค๋๋ค.
๊ทธ๋ฆฌ๊ณ ํ์ ๋ ธ๋ ์ค ์ต์๋ณด๋ค ๋ง์ ๋ ธ๋๊ฐ ์ผ์ชฝ ๋ ธ๋์ ๋ฐ์ดํฐ๋ผ๋ฉด ๊ฐ์ฅ ํฐ ๊ฐ์ ์ค๋ฅธ์ชฝ ๋ ธ๋์ ๋ฐ์ดํฐ๋ผ๋ฉด
๊ฐ์ฅ ์์ ๊ฐ์ ๋ฐ๊ฟ์ค ๋ถ๋ชจ ๋ ธ๋ ์๋ฆฌ์ ์ฑ์์ฃผ๊ณ ๋ฐ์ดํฐ์ ๋ง๊ฒ ์ฌ๋ฐฐ์น ํด์ค๋๋ค.
3์ฐจ B-Tree์์ 27์ ์ญ์ ํ ๊ฒฝ์ฐ

๋จผ์ 19๊ฐ 0๋ฒ์งธ ๋ ธ๋์ ์์ผ๋ฏ๋ก ๋ถ๋ชจ ๋ ธ๋์ 0๋ฒ์งธ ๋ฐ์ดํฐ์ธ 24๊ณผ ๋ฐ๊ฟ์ฃผ๊ณ 27์ ์ญ์ ํฉ๋๋ค.

์ผ์ชฝ ํ์ ๋ ธ๋์ ๊ฐ์ฅ ํฐ ๊ฐ์ ๋ถ๋ชจ๋ก ๋์ฒดํด ์ค๋๋ค.

1-3) ์ญ์ ํ๋ ค๋ ๋ ธ๋์ ํ์ ๋ ธ๋์ ์๊ฐ ๋ชจ๋ ์ต์์ด๊ณ , ๋ถ๋ชจ์ ๋ ธ๋๊ฐ ์ต์๋ณด๋ค ํฐ ๊ฒฝ์ฐ
์ญ์ ํ๋ ค๋ ๋ ธ๋ ์ธ๋ฑ์ค ์์น๋ฅผ ๊ฐ์ง ๋ถ๋ชจ์ ๋ฐ์ดํฐ๋ฅผ ๋์ฒดํด์ฃผ๊ณ ์ฌ๋ฐฐ์นํฉ๋๋ค.
3์ฐจ B-Tree 3์ ์ญ์ ํ ๊ฒฝ์ฐ

3์ ์ญ์ ํด์ฃผ๊ณ ๊ทธ ์๋ฆฌ์ 3์ด 1๋ฒ์งธ ๋ ธ๋์ ์์ผ๋ฏ๋ก [2,4]์ 1๋ฒ์งธ์ธ 4๋ฅผ ๋์ฒดํด ์ค๋๋ค.

1-4) ์ญ์ ํ๋ ค๋ ๋ ธ๋,ํ์ ,๋ถ๋ชจ ๋ ธ๋ ๋ชจ๋ ์ต์์ธ ๊ฒฝ์ฐ
3์ฐจ B-Tree์์ 16์ ์ญ์ ํ ๊ฒฝ์ฐ

๋ฐ์ดํฐ๋ฅผ ์ญ์ ํด์ฃผ๊ณ ๋ถ๋ชจ ๋ ธ๋์ ์์ ๋ ธ๋๋ฅผ ํฉ์ณ์ค๋๋ค.

ํ์ ๋ ธ๋์ ์์๋ค๋ก ํฉ์ณ์ค๋๋ค.

ํ์ฌ ๋ ธ๋ ๋ฒ์งธ์ ๋ถ๋ชจ ๋ ธ๋ ์ธ๋ฑ์ค๋ฅผ ๋ด๋ ค์ค๋๋ค.

๋ฐ์ดํฐ๋ฅผ ์ฌ๋ฐ๋ฅด๊ฒ ๋ฐฐ์นํด์ค๋๋ค.

2. ๋ฆฌํ ๋ ธ๋๊ฐ ์๋ ๊ฒฝ์ฐ
2-1) ์ญ์ ํ๋ ค๋ ๋ ธ๋ ๋๋ ์์ ๋ ธ๋์ ์๊ฐ ์ต์๋ณด๋ค ํฐ ๊ฒฝ์ฐ
์ญ์ ํ ๋ค ์์์ ์ผ์ชฝ ๋ ธ๋์์ ๊ฐ์ฅ ํฐ ๊ฐ ๋๋ ์ค๋ฅธ์ชฝ ๋ ธ๋์์ ๊ฐ์ฅ ์์ ๊ฐ์ผ๋ก ๋์ฒดํด ์ค๋๋ค.
3์ฐจ B-Tree์์ 2๋ฅผ ์ญ์ ํ ๊ฒฝ์ฐ

2๋ฅผ ์ญ์ ํ ๋ค ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋์์ ๊ฐ์ฅ ์์ ๊ฐ์ธ 4์ ๋์ฒดํด ์ค๋๋ค.

2-2) ์ญ์ ํ๋ ค๋ ๋ ธ๋์ ์์ ๋ ธ๋๊ฐ ๋ชจ๋ ์ต์์ผ ๊ฒฝ์ฐ
์ญ์ ํ๋ ค๋ ๋ ธ๋๋ฅผ ์ญ์ ํ๊ณ ์์๋ค์ ํ๋๋ก ํฉ์ณ์ค๋๋ค.
3์ฐจ B-Tree์์ 4๋ฅผ ์ญ์ ํ๋ ๊ฒฝ์ฐ

์ญ์ ํด์ฃผ๋ ค๋ ๋ฐ์ดํฐ๋ฅผ ์ญ์ ํ๊ณ ์์๋ค์ ํฉ์ณ์ค๋๋ค.

์ญ์ ํด์ค ๋ ธ๋ ๋ฒ์งธ ์ธ๋ฑ์ค๋ฅผ ๊ฐ์ง ๋ถ๋ชจ ๋ ธ๋์ ๋ฐ์ดํฐ๋ฅผ ํ์ ๋ ธ๋์ ํฉ์ณ์ค ๋ค ํฉ์ณ์ค ์์ ๋ ธ๋๋ค์ ๊ทธ ์๋๋ก ๋ถ์ฌ์ค๋๋ค.

'๐ฅ Computer Science > Data Structure' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Data Structure] Trie๋? (feat. ์ด๋ก ) (0) | 2022.07.29 |
---|---|
[Data Structure] AVL ํธ๋ฆฌ ๊ตฌํํด๋ณด๊ธฐ (feat. Swift) (0) | 2021.12.06 |
[Data Structure] AVL(Adelson-Velsky and Landis) ํธ๋ฆฌ๋? (0) | 2021.12.01 |
[Data Structure] ์ด์ง ํ์ ํธ๋ฆฌ(Binary Search Tree) ๊ตฌํํด๋ณด๊ธฐ (feat.Swift) (0) | 2021.11.18 |
[Data Structure] ์ด์ง ํ์ ํธ๋ฆฌ(Binary Search Tree)๋? (0) | 2021.11.17 |
๋๊ธ