1 minute read

๐Ÿ“˜ ํŠธ๋ฆฌ(Tree)๋ž€?

ํŠธ๋ฆฌ๋Š” ๊ทธ๋ž˜ํ”„์™€ ํ•จ๊ป˜ ๋น„์„ ํ˜• ์ž๋ฃŒ๊ตฌ์กฐ ๋กœ์จ ๋…ธ๋“œ์™€ ๊ฐ„์„ ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๊ณ„์ธต๊ตฌ์กฐ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค.
๊ทธ๋ž˜ํ”„๋Š” n:m์˜ ๊ตฌ์กฐ์ด์ง€๋งŒ, ํŠธ๋ฆฌ๋Š” n:1์˜ ๊ตฌ์กฐ๋กœ ๋˜์–ด ์žˆ๋‹ค.
๊ทธ๋ž˜ํ”„์˜ ํ•œ ์ข…๋ฅ˜๋กœ์จ, ์‚ฌ์ดํด์ด ์—†๋Š” ํ•˜๋‚˜์˜ ์—ฐ๊ฒฐ ๊ทธ๋ž˜ํ”„(Connected Graph)์ด๋‹ค.

  • ๋ฃจํŠธ ๋…ธ๋“œ(root node) : ๋ถ€๋ชจ๊ฐ€ ์—†๋Š” ๋…ธ๋“œ
  • ๋ถ€๋ชจ ๋…ธ๋“œ : ๋…ธ๋“œ๋กœ ์—ฐ๊ฒฐ๋œ ์ƒ์œ„ ์ธต์˜ ๋…ธ๋“œ
  • ์ž์‹ ๋…ธ๋“œ : ๋…ธ๋“œ๋กœ ์—ฐ๊ฒฐ๋œ ํ•˜์œ„ ์ธต์˜ ๋…ธ๋“œ

๐Ÿ“– ํŠธ๋ฆฌ์˜ ์ข…๋ฅ˜

  • ์ด์ง„ ํŠธ๋ฆฌ
  • ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ
  • ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ
  • ๊ท ํ˜• ํŠธ๋ฆฌ
  • ํŽธํ–ฅ ํŠธ๋ฆฌ

๐Ÿ“– ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ

์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋ž€ ์šฐ์„ ์ˆœ์œ„ ํ ๊ตฌํ˜„์„ ์œ„ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค.
๋…ธ๋“œ์˜ ์™ผ์ชฝ ๊ฐ€์ง€์—๋Š” ํ•ญ์ƒ ๋ถ€๋ชจ๋…ธ๋“œ๋ณด๋‹ค ์ž‘์€ ๊ฐ’์ด ๋“ค์–ด๊ฐ€๋ฉฐ, ์™ผ์ชฝ๊ฐ€์ง€๋ณด๋‹ค ์˜ค๋ฅธ์ชฝ ๊ฐ€์ง€์— ๋” ํฐ๊ฐ’์ด ์žˆ๋„๋ก ๊ตฌ์„ฑ๋œ๋‹ค.
๋ฐฐ์—ด๊ณผ ๊ฐ™์€ ๋‹ค๋ฅธ ์ž๋ฃŒ๊ตฌ์กฐ์— ๋น„ํ•ด ์‚ฝ์ž…, ์‚ญ์ œ์†๋„๊ฐ€ O(log(n))์ˆ˜์ค€์œผ๋กœ ๋Š๋ฆฌ์ง€๋งŒ, ๋ฐฐ์—ด์€ ์ตœ๋Œ€๊ฐ’/์ตœ์†Œ๊ฐ’์„ ๊ตฌํ•  ๋•Œ, ์ตœ์•…์˜ ๊ฒฝ์šฐ์— O(n^2)์˜ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฌ์ง€๋งŒ, ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ ๊ธฐ๋ฐ˜์œผ๋กœ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ๊ตฌํ˜„ํ•  ์‹œ, ์‚ฝ์ž…, ์‚ญ์ œ๊ฐ€ ํ•ญ์ƒ O(log(n))๋งŒํผ๋งŒ ๊ฑธ๋ฆฌ๊ฒŒ ๋œ๋‹ค.


๐Ÿ“– ํž™(heap)์ด๋ž€?

ํž™(heap) ์ด๋ž€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

  • ๋ฐ์ดํ„ฐ์—์„œ ์ตœ๋Œ€๊ฐ’๊ณผ ์ตœ์†Œ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ์ฐพ๊ธฐ ์œ„ํ•ด ์‚ฌ์šฉ๋˜๋Š” ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ ํ˜•ํƒœ์ด๋‹ค.
  • ํž™์€ ์ผ์ข…์˜ ๋ฐ˜์ •๋ ฌ ์ƒํƒœ(๋Š์Šจํ•œ ์ •๋ ฌ ์ƒํƒœ) ์ด๋ฉฐ ์ตœ๋Œ€ํž™๊ณผ ์ตœ์†Œํž™์œผ๋กœ ๋‚˜๋ˆ„์–ด์ง„๋‹ค.
  • ์ตœ๋Œ€ํž™์€ ์ž์‹๋…ธ๋“œ๋ณด๋‹ค ๋ถ€๋ชจ๋…ธ๋“œ์˜ ๊ฐ’์ด ํฌ๋‹ค.
  • ์ตœ์†Œํž™์€ ๋ถ€๋ชจ๋…ธ๋“œ๋ณด๋‹ค ์ž์‹๋…ธ๋“œ์˜ ๊ฐ’์ด ํฌ๋‹ค.
  • ์ค‘๋ณต์„ ํ—ˆ์šฉํ•œ๋‹ค.

image

์ตœ์†Œํž™์€ ๋ฃจํŠธ๊ฐ’์ด ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ๊ฐ€์ง€๊ฒŒ ๋˜๋Š” ํŠธ๋ฆฌ์ด๋‹ค.
์ตœ๋Œ€ํž™์€ ๋ฃจํŠธ๊ฐ’์ด ๊ฐ€์žฅ ํฐ ๊ฐ’์„ ๊ฐ€์ง€๊ฒŒ ๋˜๋Š” ํŠธ๋ฆฌ์ด๋‹ค.

์ตœ์†Œํž™์„ ๊ธฐ์ค€์œผ๋กœ

  • ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ index = ๋ถ€๋ชจ๋…ธ๋“œ index / 2
  • ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ index = ๋ถ€๋ชจ๋…ธ๋“œ index / 2 + 1
  • ๋ถ€๋ชจ ๋…ธ๋“œ index = ๋ถ€๋ชจ๋…ธ๋“œ index / 2


๐Ÿ”— ๊ด€๋ จ ์˜ˆ์‹œ

tag:Array
tag:List



๊ฐœ์ธ ๊ณต๋ถ€ ๊ธฐ๋ก์šฉ ๋ธ”๋กœ๊ทธ์ž…๋‹ˆ๋‹ค.
ํ‹€๋ฆฌ๊ฑฐ๋‚˜ ์˜ค๋ฅ˜๊ฐ€ ์žˆ์„ ๊ฒฝ์šฐ ์ œ๋ณดํ•ด์ฃผ์‹œ๋ฉด ๊ฐ์‚ฌํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.๐Ÿ˜