์ด์ง ํธ๋ฆฌ(binary tree)๋? ๊ฐ๊ฐ์ ๋ ธ๋๊ฐ ์ต๋ ๋ ๊ฐ์ ์์ ๋ ธ๋๋ฅผ ๊ฐ์ง๋ ํธ๋ฆฌ ์๋ฃ ๊ตฌ์กฐ. ์ด์ง ํธ๋ฆฌ(Binary Tree)๋ ์ต๋ 2๊ฐ์ ์์์ ๊ฐ์ง ์ ์๋ ํธ๋ฆฌ์ด๋ค.
ํธ๋ฆฌ(Tree)๋ ๋๋ฌด์ ํํ๋ฅผ ๋ค์ง์ ๊ฒ๊ณผ ๊ฐ์ ํํ์ ์๋ฃ๊ตฌ์กฐ
๋ฃจํธ ๋
ธ๋(root node)
: ์ต์๋จ ๋
ธ๋๊ฐ์ง
: ๋ฅผ ์ด์ฉํด์ ๊ฐ๊ฐ์ ๋
ธ๋๋ก ์ฐ๊ฒฐ๋ฆฌํ ๋
ธ๋(reaf node)
: ๊ฐ์ฅ ๋ง์ง๋ง ๋
ธ๋๋ถ๋ชจ ๋
ธ๋
: ์ด๋ค ๋
ธ๋์ ๋ฐ๋ก ์์ ์ฐ๊ฒฐ๋์ด ์๋ ๋
ธ๋์์ ๋
ธ๋
: ์ด๋ค ๋
ธ๋์ ๋ฐ๋ก ์๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋
ธ๋ํ์ ๋
ธ๋
: ๊ฐ์ ๋ถ๋ชจ ๋
ธ๋์ ์์๋ค๊ธธ์ด(length)
: ์ถ๋ฐ ๋
ธ๋์์ ๋ชฉ์ ์ง ๋
ธ๋๊น์ง ๊ฑฐ์ณ์ผ ํ๋ ๊ฐ์ง์ ์๋ฅผ ์๋ฏธ๊น์ด(Depth)
: ๋ฃจํธ ๋
ธ๋์์ ํน์ ๋
ธ๋๊น์ง์ ๊ธธ์ด๋์ด(Height)
: ๋ฃจํธ ๋
ธ๋์์ ๊ฐ์ฅ ๊น์ ๋
ธ๋๊น์ง์ ๊ธธ์ด์ด์ง ํธ๋ฆฌ(Binary Tree)
๋ ์ต๋ 2๊ฐ์ ์์์ ๊ฐ์ง ์ ์๋ ํธ๋ฆฌํฌํ ์ด์ง ํธ๋ฆฌ(Full Binary Tree)
: ๋ฆฌํ ๋
ธ๋๋ฅผ ์ ์ธํ ๋ชจ๋ ๋
ธ๋๊ฐ ๋ ์์์ ๊ฐ์ง๊ณ ์๋ ํธ๋ฆฌ์์ ์ด์ง ํธ๋ฆฌ(Complete Binary Tree)
: ๋ชจ๋ ๋
ธ๋๋ค์ด ์ผ์ชฝ ์์๋ถํฐ ์ฐจ๊ทผ์ฐจ๊ทผ ์ฑ์์ง ๋
ธ๋๋์ด ๊ท ํ ํธ๋ฆฌ(Height Balanced Tree)
๋ ์ผ์ชฝ ์์ ํธ๋ฆฌ์ ์ค๋ฅธ์ชฝ ์์ ํธ๋ฆฌ์ ๋์ด๊ฐ 1 ์ด์ ์ฐจ์ด ๋์ง ์๋ ํธ๋ฆฌ