๐Ÿš€ What I Will Learn

  • ์ด์ง„ ํŠธ๋ฆฌ(binary tree) ์ž๋ฃŒ๊ตฌ์กฐ์˜ ํ•„์š”์„ฑ์— ๋Œ€ํ•ด ์ดํ•˜ํ•œ๋‹ค
  • ์ด์ง„ ํŠธ๋ฆฌ์™€ ๊ด€๋ จํ•œ ๋‹ค์–‘ํ•œ ์šฉ์–ด๋ฅผ ์ดํ•ดํ•œ๋‹ค

์ด์ง„ ํŠธ๋ฆฌ(binary tree)๋ž€? ๊ฐ๊ฐ์˜ ๋…ธ๋“œ๊ฐ€ ์ตœ๋Œ€ ๋‘ ๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง€๋Š” ํŠธ๋ฆฌ ์ž๋ฃŒ ๊ตฌ์กฐ. ์ด์ง„ ํŠธ๋ฆฌ(Binary Tree)๋Š” ์ตœ๋Œ€ 2๊ฐœ์˜ ์ž์‹์„ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” ํŠธ๋ฆฌ์ด๋‹ค.



์ด์ง„ ํŠธ๋ฆฌ(binary tree)

1๏ธโƒฃ ์ด์ง„ ํŠธ๋ฆฌ๋ž€?

ํŠธ๋ฆฌ(Tree)๋Š” ๋‚˜๋ฌด์˜ ํ˜•ํƒœ๋ฅผ ๋’ค์ง‘์€ ๊ฒƒ๊ณผ ๊ฐ™์€ ํ˜•ํƒœ์˜ ์ž๋ฃŒ๊ตฌ์กฐ


โœ”๏ธ ํŠธ๋ฆฌ์˜ ์šฉ์–ด ์ดํ•ด

  • ๋ฃจํŠธ ๋…ธ๋“œ(root node): ์ตœ์ƒ๋‹จ ๋…ธ๋“œ
  • ๊ฐ€์ง€: ๋ฅผ ์ด์šฉํ•ด์„œ ๊ฐ๊ฐ์˜ ๋…ธ๋“œ๋กœ ์—ฐ๊ฒฐ
  • ๋ฆฌํ”„ ๋…ธ๋“œ(reaf node): ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ

  • ๋ถ€๋ชจ ๋…ธ๋“œ: ์–ด๋–ค ๋…ธ๋“œ์˜ ๋ฐ”๋กœ ์œ„์— ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๋…ธ๋“œ
  • ์ž์‹ ๋…ธ๋“œ: ์–ด๋–ค ๋…ธ๋“œ์˜ ๋ฐ”๋กœ ์•„๋ž˜์— ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๋…ธ๋“œ

  • ํ˜•์ œ ๋…ธ๋“œ: ๊ฐ™์€ ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ์ž์‹๋“ค

  • ํŠธ๋ฆฌ์˜ ๊ธธ์ด(length): ์ถœ๋ฐœ ๋…ธ๋“œ์—์„œ ๋ชฉ์ ์ง€ ๋…ธ๋“œ๊นŒ์ง€ ๊ฑฐ์ณ์•ผ ํ•˜๋Š” ๊ฐ€์ง€์˜ ์ˆ˜๋ฅผ ์˜๋ฏธ

  • ๊นŠ์ด(Depth): ๋ฃจํŠธ ๋…ธ๋“œ์—์„œ ํŠน์ • ๋…ธ๋“œ๊นŒ์ง€์˜ ๊ธธ์ด

  • ํŠธ๋ฆฌ์˜ ๋†’์ด(Height): ๋ฃจํŠธ ๋…ธ๋“œ์—์„œ ๊ฐ€์žฅ ๊นŠ์€ ๋…ธ๋“œ๊นŒ์ง€์˜ ๊ธธ์ด


โœ”๏ธ ํŠธ๋ฆฌ์˜ ์ข…๋ฅ˜

  • ์ด์ง„ ํŠธ๋ฆฌ(Binary Tree)๋Š” ์ตœ๋Œ€ 2๊ฐœ์˜ ์ž์‹์„ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” ํŠธ๋ฆฌ

  • ํฌํ™” ์ด์ง„ ํŠธ๋ฆฌ(Full Binary Tree): ๋ฆฌํ”„ ๋…ธ๋“œ๋ฅผ ์ œ์™ธํ•œ ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ ๋‘ ์ž์‹์„ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ํŠธ๋ฆฌ

  • ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ(Complete Binary Tree): ๋ชจ๋“  ๋…ธ๋“œ๋“ค์ด ์™ผ์ชฝ ์ž์‹๋ถ€ํ„ฐ ์ฐจ๊ทผ์ฐจ๊ทผ ์ฑ„์›Œ์ง„ ๋…ธ๋“œ

  • ๋†’์ด ๊ท ํ˜• ํŠธ๋ฆฌ(Height Balanced Tree)๋Š” ์™ผ์ชฝ ์ž์‹ ํŠธ๋ฆฌ์™€ ์˜ค๋ฅธ์ชฝ ์ž์‹ ํŠธ๋ฆฌ์˜ ๋†’์ด๊ฐ€ 1 ์ด์ƒ ์ฐจ์ด ๋‚˜์ง€ ์•Š๋Š” ํŠธ๋ฆฌ




โœจ tl;dr

  • ์ด์ง„ ํŠธ๋ฆฌ๋Š” ๋งŽ์€ ์–‘์˜ ๋…ธ๋“œ๋ฅผ ๋‚ฎ์€ ๋†’์ด์—์„œ ๊ด€๋ฆฌํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ์ ์—์„œ ๋ฐ์ดํ„ฐ ํ™œ์šฉ์˜ ํšจ์œจ์„ฑ์ด ๋†’์•„์ง„๋‹ค
  • ๋ฐ์ดํ„ฐ ์ €์žฅ, ํƒ์ƒ‰ ๋“ฑ์˜ ๋‹ค์–‘ํ•œ ๋ชฉ์ ์—์„œ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค