[Java] Binary Tree
Binary Tree๋ ํธ๋ฆฌ๋ฅผ ํตํด ๋ฐ์ดํฐ๋ฅผ ๋น์ ํ์ ์ผ๋ก ๊ด๋ฆฌํ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
์์ ํฌ์คํ ์์ BST(Binary Search Tree)์ ๋ํด์ ์ค๋ช ํ๋๋ฐ BST๋ ์ด์ง ํธ๋ฆฌ๋ฅผ ๊ธฐ๋ฐํ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
์ Binary Tree๋ฅผ ์ฌ์ฉํ ๊น?
Tree Post์์๋ ์ค๋ช ํ๋๋ฐ ์ผ๋ฐ DAG์ ๊ฐ์ Tree๋ ํจ์จ์ฑ ์ธก๋ฉด์์ ๋๋ฌด ๋ถ์กฑํ๋ค. ๊ทธ์ Graph์ ๋ค๋ฆ์ด ์๋ค.
๊ทธ๋์ ์ค์ ๋ฐ์ดํฐ ์ฒ๋ฆฌ๋ฅผ ํ๊ธฐ ์ํด Binary Tree๋ก ํจ์จ์ฑ์ ๊ทน๋ํํ๋ ๋ฐฉ๋ฒ์ ์ฑํํ ๊ฒ์ด๋ค.
ํฌ๊ฒ Binary Tree์ ๋ ์ข ๋ฅ๋ฅผ ์์๋ณด์.
1. ์์ ์ด์ง ํธ๋ฆฌ
2. ํธํฅ ํธ๋ฆฌ
์ด ์ธ์๋ ๋ง์ง๋ง Binary Tree์ ํต์ฌ์ ์ค๋ช ํ๊ธฐ์ ๋ ๊ฐ์ง๊ฐ ์ต๊ณ ์ธ ๊ฒ ๊ฐ๋ค.
์ ๋๊ฐ์ง ๊ฐ๋ ์ ์ธ๊ธํ ์ด์ ๋ BST์ ๋ฌธ์ ์ ๋๋ฌธ์ด๋ค.
์์ ์์ฑํ BST ์ฝ๋์์ ์์ ๊ฐ์ ์ผ์ชฝ, ํฐ ๊ฐ์ ์ค๋ฅธ์ชฝ์์ sub tree๋ฅผ ์์ฑํ๋ฉด์ ์ ์ ๋ฆฌ๊ฐ ๋์ด์์๋ค.
๋ง์ฝ, ๊ทธ๋ฆผ์ฒ๋ผ ์ค๋ฆ์ฐจ์์ผ๋ก๋ง ๋ฐ์ดํฐ๋ฅผ ์ ๋ ฅํ๋ค๋ฉด? ํธํฅํธ๋ฆฌ๊ฐ ๋ฐ์ํ๋ค๋ ๊ฒ์ด๋ค.
๋ฐ์ดํฐ๊ฐ 100๋ง๊ฐ๊ฐ ์ค๋ฆ์ฐจ์์ผ ๋, Log_2(100๋ง) ์์ ์ ํํ์์ผ๋ก ๋ฐ๋๋ค๋ ๊ฒ์ด๋ค.
์ฝ 50,000๋ง ๋ฐฐ ๋๋ ค์ง๋ค. ๋ฌผ๋ก ๋ฐ์ดํฐ๊ฐ ๋ ๋ง์์ง์๋ก ๋ ๋๋ ค์ง ๊ฒ์ด๋ค. ์ด๋ฐ ๋ฌธ์ ๊ฐ BST์์ ๋ฐ์ํ๋ค๋ ๊ฒ์ด๋ค.
์ค์ ๋ก ์ด๊ฒ์ ํด๊ฒฐํ๊ธฐ ์ํ ๋ฐฉ๋ฒ ์ค ํ๋๊ฐ ์์ ์ด์งํธ๋ฆฌ๋ฅผ ์ ์งํ๋ ๊ฒ์ธ๋ฐ ์ผ์ชฝ ์ฌ์ง์์ 4๋ฅผ ์ง์ ๋๋ ์์ ์ด์งํธ๋ฆฌ๊ฐ ์ ์ง๋์ง ์๊ณ ์๋ค๋ ๊ฒ์ด๋ค. ์ด๊ฒ์ ํด๊ฒฐํ๋ ๋ฐฉ๋ฒ์ด ์๊ฐ๊ท ํํธ๋ฆฌ (Self-Balancing Tree) ์ด๋ฉฐ ๋ํ์ ์ผ๋ก Red-Black Tree, AVL Tree๊ฐ ์กด์ฌํ๋ค.
์ด ์๊ฐ๊ท ํ ํธ๋ฆฌ๋ฅผ ์ด์ฉํ ๊ฒ์ด Java์ TreeSet๊ณผ TreeMap ์ธ๋ฐ ์๊ฐ์ด ๋๋ฉด ํ ๋ฒ ์์ฑํด๋ณด์...
๋ฒ์ธ๋ก Binary Tree์๋ ๋ฌธ์์ด ๊ฒ์์ ์ํ Trie, ์ต์๊ฐ๊ณผ ์ต๋๊ฐ ๊ฒ์์ ํจ์จ์ ์ธ Heap์ด๋ผ๋ ์๋ฃ๊ตฌ์กฐ ๋ํ ์กด์ฌํ๋ค.