[Data Structure] ๐ ํธ๋ฆฌ์ ํ (Tree & Heap)
๐ ํธ๋ฆฌ(Tree)๋?
ํธ๋ฆฌ๋ ๊ทธ๋ํ์ ํจ๊ป ๋น์ ํ ์๋ฃ๊ตฌ์กฐ ๋ก์จ ๋
ธ๋์ ๊ฐ์ ์ผ๋ก ์ด๋ฃจ์ด์ง ๊ณ์ธต๊ตฌ์กฐ๋ฅผ ๊ฐ์ง๊ณ ์๋ค.
๊ทธ๋ํ๋ n:m์ ๊ตฌ์กฐ์ด์ง๋ง, ํธ๋ฆฌ๋ n:1์ ๊ตฌ์กฐ๋ก ๋์ด ์๋ค.
๊ทธ๋ํ์ ํ ์ข
๋ฅ๋ก์จ, ์ฌ์ดํด์ด ์๋ ํ๋์ ์ฐ๊ฒฐ ๊ทธ๋ํ(Connected Graph)์ด๋ค.
- ๋ฃจํธ ๋ ธ๋(root node) : ๋ถ๋ชจ๊ฐ ์๋ ๋ ธ๋
- ๋ถ๋ชจ ๋ ธ๋ : ๋ ธ๋๋ก ์ฐ๊ฒฐ๋ ์์ ์ธต์ ๋ ธ๋
- ์์ ๋ ธ๋ : ๋ ธ๋๋ก ์ฐ๊ฒฐ๋ ํ์ ์ธต์ ๋ ธ๋
๐ ํธ๋ฆฌ์ ์ข ๋ฅ
- ์ด์ง ํธ๋ฆฌ
- ์ด์ง ํ์ ํธ๋ฆฌ
- ์์ ์ด์ง ํธ๋ฆฌ
- ๊ท ํ ํธ๋ฆฌ
- ํธํฅ ํธ๋ฆฌ
๐ ์ด์ง ํ์ ํธ๋ฆฌ
์ด์ง ํ์ ํธ๋ฆฌ๋ ์ฐ์ ์์ ํ ๊ตฌํ์ ์ํ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
๋
ธ๋์ ์ผ์ชฝ ๊ฐ์ง์๋ ํญ์ ๋ถ๋ชจ๋
ธ๋๋ณด๋ค ์์ ๊ฐ์ด ๋ค์ด๊ฐ๋ฉฐ, ์ผ์ชฝ๊ฐ์ง๋ณด๋ค ์ค๋ฅธ์ชฝ ๊ฐ์ง์ ๋ ํฐ๊ฐ์ด ์๋๋ก ๊ตฌ์ฑ๋๋ค.
๋ฐฐ์ด๊ณผ ๊ฐ์ ๋ค๋ฅธ ์๋ฃ๊ตฌ์กฐ์ ๋นํด ์ฝ์
, ์ญ์ ์๋๊ฐ O(log(n))์์ค์ผ๋ก ๋๋ฆฌ์ง๋ง, ๋ฐฐ์ด์ ์ต๋๊ฐ/์ต์๊ฐ์ ๊ตฌํ ๋, ์ต์
์ ๊ฒฝ์ฐ์ O(n^2)์ ์๊ฐ์ด ๊ฑธ๋ฆฌ์ง๋ง, ์ด์ง ํ์ ํธ๋ฆฌ ๊ธฐ๋ฐ์ผ๋ก ์๋ฃ๊ตฌ์กฐ๋ฅผ ๊ตฌํํ ์, ์ฝ์
, ์ญ์ ๊ฐ ํญ์ O(log(n))๋งํผ๋ง ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
๐ ํ(heap)์ด๋?
ํ(heap)
์ด๋ ๋ค์๊ณผ ๊ฐ๋ค.
- ๋ฐ์ดํฐ์์ ์ต๋๊ฐ๊ณผ ์ต์๊ฐ์ ๋น ๋ฅด๊ฒ ์ฐพ๊ธฐ ์ํด ์ฌ์ฉ๋๋ ์์ ์ด์ง ํธ๋ฆฌ ํํ์ด๋ค.
- ํ์ ์ผ์ข ์ ๋ฐ์ ๋ ฌ ์ํ(๋์จํ ์ ๋ ฌ ์ํ) ์ด๋ฉฐ ์ต๋ํ๊ณผ ์ต์ํ์ผ๋ก ๋๋์ด์ง๋ค.
- ์ต๋ํ์ ์์๋ ธ๋๋ณด๋ค ๋ถ๋ชจ๋ ธ๋์ ๊ฐ์ด ํฌ๋ค.
- ์ต์ํ์ ๋ถ๋ชจ๋ ธ๋๋ณด๋ค ์์๋ ธ๋์ ๊ฐ์ด ํฌ๋ค.
- ์ค๋ณต์ ํ์ฉํ๋ค.
์ต์ํ์ ๋ฃจํธ๊ฐ์ด ๊ฐ์ฅ ์์ ๊ฐ์ ๊ฐ์ง๊ฒ ๋๋ ํธ๋ฆฌ์ด๋ค.
์ต๋ํ์ ๋ฃจํธ๊ฐ์ด ๊ฐ์ฅ ํฐ ๊ฐ์ ๊ฐ์ง๊ฒ ๋๋ ํธ๋ฆฌ์ด๋ค.
์ต์ํ์ ๊ธฐ์ค์ผ๋ก
- ์ผ์ชฝ ์์ ๋ ธ๋ index = ๋ถ๋ชจ๋ ธ๋ index / 2
- ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋ index = ๋ถ๋ชจ๋ ธ๋ index / 2 + 1
- ๋ถ๋ชจ ๋ ธ๋ index = ๋ถ๋ชจ๋ ธ๋ index / 2
๐ ๊ด๋ จ ์์
tag:Array
tag:List
๊ฐ์ธ ๊ณต๋ถ ๊ธฐ๋ก์ฉ ๋ธ๋ก๊ทธ์
๋๋ค.
ํ๋ฆฌ๊ฑฐ๋ ์ค๋ฅ๊ฐ ์์ ๊ฒฝ์ฐ ์ ๋ณดํด์ฃผ์๋ฉด ๊ฐ์ฌํ๊ฒ ์ต๋๋ค.๐