0323 TIL

looggiยท2023๋…„ 3์›” 22์ผ
0

TILs

๋ชฉ๋ก ๋ณด๊ธฐ
43/114
post-thumbnail

์ž๋ฃŒ๊ตฌ์กฐ

  1. BST(Binary Search Tree)์™€ Binary Tree์— ๋Œ€ํ•ด ์„ค๋ช…ํ•ด์ฃผ์„ธ์š”

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

์ด์ง„ ํŠธ๋ฆฌ

Binary Tree
ํŠธ๋ฆฌํ˜•ํƒœ์˜ ์ž๋ฃŒ๊ตฌ์กฐ๋กœ ๋น„๊ต ๊ฐ€๋Šฅํ•œ ์ž๋ฃŒ๋ฅผ ์ •๋ฆฌํ•˜๋Š” ๋ฐ ์“ฐ์ž„
k๊ฐ€ 2์ธ ์ •๋ ฌ K-ํ•ญ ํŠธ๋ฆฌ์˜ ํŠน์ˆ˜ํ•œ ๊ฒฝ์šฐ๋‹ค

๊ฐ๊ฐ์˜ ์ž๋ฃŒ๋Š” ๋…ธ๋“œ(node, ๋ถ„๊ธฐ์ )์— ์ €์žฅ
๋…ธ๋“œ๋Š” ์ตœ๋Œ€ ๋‘ ๊ฐœ(์™ผ์ชฝ๊ณผ ์˜ค๋ฅธ์ชฝ)์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค

์ด์ง„ํŠธ๋ฆฌ์—์„œ๋Š” ํŠธ๋ฆฌ์ˆœํšŒ๋กœ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋‹ค

์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ

๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์„ ์ œ์™ธํ•˜๊ณ  ๋ชจ๋“  ๋ ˆ๋ฒจ์ด ์ฑ„์›Œ์ ธ์žˆ๋‹ค (ํฌํ™”์ด์ง„ํŠธ๋ฆฌ)
๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์„ ์ฑ„์šธ ๋• ์™ผ์ชฝ์—์„œ ์˜ค๋ฅธ์ชฝ ์ˆœ์œผ๋กœ ๋…ธ๋“œ๋ฅผ ์ฑ„์šด๋‹ค

โžก๏ธ ํž™(ํž™ํŠธ๋ฆฌ)์˜ ๋ฒ ์ด์Šค
์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ๊ตฌํ˜„ํ•˜๊ฑฐ๋‚˜ ํž™์ •๋ ฌ์„ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค

  • ์šฐ์„ ์ˆœ์œ„ ํ๋Š” ๋ฐฐ์—ด, ๋งํฌ๋“œ๋ฆฌ์ŠคํŠธ, ํž™์œผ๋กœ ๊ตฌํ˜„์ด ๊ฐ€๋Šฅํ•˜๋‹ค

์ด์ง„ ํž™: ํž™์˜ ์ข…๋ฅ˜ ์ค‘ ํ•˜๋‚˜๋กœ ์ž์‹ ๋…ธ๋“œ์˜ ์ˆ˜๊ฐ€ ์ตœ๋Œ€ 2๊ฐœ์ธ ํž™
๋ฐฐ์—ด๋กœ ํ‘œํ˜„ํ•˜๊ธฐ ์ข‹์€ ๊ตฌ์กฐ- ๋‚ญ๋น„์—†์ด ๋ฐฐ์น˜๊ฐ€๋Šฅ

  • ํŠธ๋ฆฌ์˜ ๋ฐฐ์—ด ํ‘œํ˜„์€ ์ธ๋ฑ์Šค๊ฐ€ 1๋ถ€ํ„ฐ ์‹œ์ž‘๋œ๋‹ค

https://eng.libretexts.org/Bookshelves/Computer_Science/Programming_and_Computation_Fundamentals/Book%3A_Algorithm_Design_and_Analysis_(Justo)/02%3A_Searching_Binary_Search_Trees_and_Heaps

์ „ ์ด์ง„ ํŠธ๋ฆฌ

๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ 0๋˜๋Š” 2๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง

์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ

์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ๋Š” ์ •๋ ฌ๋œ ์ด์ง„ํŠธ๋ฆฌ๋กœ ๋…ธ๋“œ์˜ ์™ผ์ชฝ ํ•˜์œ„ ํŠธ๋ฆฌ์—๋Š” ๋…ธ๋“œ๋ณด๋‹ค ์ž‘์€ ๊ฐ’์ด ๋“ค์–ด๊ฐ€๊ณ  ์˜ค๋ฅธ์ชฝ ํ•˜์œ„ ํŠธ๋ฆฌ์—๋Š” ๋…ธ๋“œ๋ณด๋‹ค ํฐ ๊ฐ’์ด ๋“ค์–ด๊ฐ€๋Š” ํ˜•ํƒœ

โžก๏ธ ์ด๋Ÿฌํ•œ ํ˜•ํƒœ๋•Œ๋ฌธ์— ํŠน์ •๊ฐ’์„ ๊ฒ€์ƒ‰ํ•  ๋•Œ ํƒ์ƒ‰ํ•  ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ๋ฐ˜์”ฉ ์ค„์–ด๋“ค์–ด ์†๋„๊ฐ€ ๋น ๋ฅด๋‹ค

์–ด๋ ˆ์ด์™€ ๋‹ค๋ฅด๊ฒŒ ๋งํฌ๋“œ๋ฆฌ์ŠคํŠธ์ฒ˜๋Ÿผ ์ฐธ์กฐ์— ์˜ํ•ด ์ •๋ ฌ๋˜์–ด ์‚ฝ์ž…๊ณผ ์‚ญ์ œ๊ฐ€ ๋น ๋ฅด๋‹ค

์ค‘๋ณต๋…ธ๋“œ๋ฅผ ๊ฐ€์ง€์ง€ ์•Š๋Š”๋‹ค(๋…ธ๋“œ์˜ ํ‚ค๋Š” ์œ ์ผํ•˜๋‹ค)

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

https://muckycode.blogspot.com/2015/01/binary-search-treebst.html
https://code-lab1.tistory.com/8

โšก ์‹œ๊ฐ„๋ณต์žก๋„

์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์—์„œ์˜ ๊ฒ€์ƒ‰ ์‹œ๊ฐ„๋ณต์žก๋„๋Š” ํŠธ๋ฆฌ์˜ ๋†’์ด
์กฐํšŒ, ์‚ฝ์ž…, ์‚ญ์ œ ๋ชจ๋‘

  • ๊ท ํ˜• ์ƒํƒœ: O(logN)
  • ๋ถˆ๊ท ํ˜• ์ƒํƒœ: O(N)

โšก ์‚ญ์ œ ๋ฐฉ๋ฒ•

  • ์‚ญ์ œํ•  ๋…ธ๋“œ์— ์ž์‹์ด ํ•˜๋‚˜๋งŒ ์žˆ๋Š” ๊ฒฝ์šฐ
    ๋…ธ๋“œ๋ฅผ ์‚ญ์ œํ•˜๊ณ  ์ž์‹ ๋…ธ๋“œ๋ฅผ ์‚ญ์ œ๋œ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ ๋…ธ๋“œ์— ์—ฐ๊ฒฐํ•˜๊ณ ,
  • ์ž์‹์ด ๋‘˜์ธ ๊ฒฝ์šฐ
    ๊ณ„์Šน์ž ๋…ธ๋“œ๋ฅผ ์ฐพ์•„ ์œ„์น˜๋ฅผ ๋ฐ”๊พผ ํ›„ ์‚ญ์ œํ•  ๋…ธ๋“œ๊ฐ€ ๋ฆฌํ”„์— ์œ„์น˜ํ•˜๊ฒŒ ๋˜๋ฉด ์‚ญ์ œํ•ฉ๋‹ˆ๋‹ค

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

Balanced Tree(๊ท ํ˜•์žกํžŒ ์ด์ง„ํŠธ๋ฆฌ)
์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ๋ฌธ์ œ์ ์„ ๋ณด์™„ํ•œ BST

  • ๋ถˆ๊ท ํ˜• ์ƒํƒœ์ผ ๋•Œ ์‹œ๊ฐ„๋ณต์žก๋„ ์ฆ๊ฐ€

โšก ์ด์ง„ ๊ท ํ˜• ํƒ์ƒ‰ ํŠธ๋ฆฌ

  • AVL
  • Red-Black

โšก ๋น„์ด์ง„ ๊ท ํ˜• ํƒ์ƒ‰ํŠธ๋ฆฌ

  • 2-3 ํŠธ๋ฆฌ
  • 2-3-4 ํŠธ๋ฆฌ
  • B ํŠธ๋ฆฌ
    • B- Tree
      ์ผ๋ฐ˜์ ์œผ๋กœ BํŠธ๋ฆฌ๋ผ๊ณ  ๋ถ€๋ฆ„
      ์ž์‹ ๋…ธ๋“œ์˜ ์ˆ˜๊ฐ€ 2๋ณด๋‹ค ํฐ ํŠธ๋ฆฌ
      M์ฐจ BํŠธ๋ฆฌ๋Š” ์ตœ์†Œ M//2๊ฐœ ์ตœ๋Œ€ M๊ฐœ์˜ ์ž์‹์„ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” BํŠธ๋ฆฌ
      ex. 3์ฐจ๋Š” 1~3๊ฐœ์˜ ์ž์‹๋…ธ๋“œ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค
      ํ•˜๋‚˜์˜ ๋…ธ๋“œ์— ๋‘ ๊ฐœ ์ด์ƒ์˜ ๋ฐ์ดํ„ฐ(ํ‚ค)๊ฐ€ ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๋‹ค
      ํ•˜๋‚˜์˜ ๋…ธ๋“œ์— ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋ฐ์ดํ„ฐ์˜ ๊ฐฏ์ˆ˜๋Š” ์ตœ์†Œ M//2 ์ตœ๋Œ€ M-1์ด๋‹ค
      ex. 3์ฐจ๋Š” 0~2๊ฐœ ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค โ†’ ์˜ค๋ฒ„ํ•˜๋ฉด ๋ถ„๋ฆฌ๊ฐ€ ์ผ์–ด๋‚จ
      ๋…ธ๋“œ์˜ ๋ฐ์ดํ„ฐ๊ฐ€ k๊ฐœ๋ผ๋ฉด ๊ทธ ์ž์‹๋…ธ๋“œ๋Š” k+1๊ฐœ๋‹ค โ†’ ํฌ์ธํ„ฐ๋„ k+1๊ฐœ
      ํ•ญ์ƒ ์ •๋ ฌ๋œ ์ƒํƒœ
      ๋ชจ๋“  ๋ฆฌํ”„๋…ธ๋“œ๊ฐ€ ๊ฐ™์€ ๋ ˆ๋ฒจ์— ์กด์žฌ โ†’ ๋ฃจํŠธ-์ž„์˜์˜ ๋ฆฌํ”„๊นŒ์ง€์˜ ๊ธธ์ด๊ฐ€ ๊ฐ™๋‹ค
      ํƒ์ƒ‰์€ ๋ฃจํŠธ โ†’ ๋ฆฌํ”„
      ์‚ฝ์ž…์€ ํƒ์ƒ‰ ํ›„ ๋ฆฌํ”„ โ†’ ๋ฃจํŠธ
    • B+ Tree
      ๋ฆฌํ”„๋…ธ๋“œ์˜ ์ƒ์œ„ ๋…ธ๋“œ๋“ค์€ ๋ชจ๋‘ ๋ฆฌํ”„์˜ ์ธ๋ฑ์Šค ์—ญํ• ์„ ํ•จ(๋น„๋‹จ๋ง ๋…ธ๋“œ)
      ๋ชจ๋“  key, data๊ฐ€ ๋ฆฌํ”„๋…ธ๋“œ์— ๋ชจ์—ฌ์žˆ์Œ
      ๋ฐ์ดํ„ฐ๋ฅผ ์ฐพ๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋ฌด์กฐ๊ฑด ๋ฆฌํ”„๊นŒ์ง€ ๊ฐ€์•ผํ•จ
      ๋ชจ๋“  ๋ฆฌํ”„๋…ธ๋“œ๊ฐ€ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋กœ ์—ฐ๊ฒฐ๋˜์–ด์žˆ์Œ
      • ๋ฆฌํ”„๋…ธ๋“œ์—์„œ ์„ ํ˜•๊ฒ€์‚ฌ๋ฅผ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ์–ด ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ ๋งค์šฐ ๋‚ฎ์•„์ง

B-Tree์˜ ๊ฐ ๋…ธ๋“œ๋Š” ๋””์Šคํฌ์˜ ๋ธ”๋ก๊ณผ ๊ฐ™๊ธฐ ๋•Œ๋ฌธ์— ๋…ธ๋“œ ํ•˜๋‚˜๋ฅผ ์ ‘๊ทผํ•˜๋Š” ๊ฒƒ์€ ๋””์Šคํฌ๋ฅผ ํ•œ๋ฒˆ ๋” ์ ‘๊ทผํ•˜๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค. ๊ทธ๋Ÿฌ๋ฏ€๋กœ ๋ณด๋‹ค ์ ์€ ์ˆ˜์˜ ๋…ธ๋“œ๋ฅผ ์ƒ์„ฑํ•˜๋Š” ๊ฒƒ์ด ์ƒ‰์ธ๊ตฌ์กฐ์˜ ์„ฑ๋Šฅ์„ ๋†’์ผ ์ˆ˜ ์žˆ๋‹ค. ์ƒ์„ฑ๋˜๋Š” ๋…ธ๋“œ์˜ ์ˆ˜๋ฅผ ์ค„์ด๊ธฐ ์œ„ํ•ด B-Tree์˜ ๋ณ€ํ˜•์œผ๋กœ B* ํŠธ๋ฆฌ๊ฐ€ ๋‚˜์˜ค๊ฒŒ ๋˜์—ˆ๋‹ค.

  • B* Tree
    B-Tree์˜ ์‚ฝ์ž…๊ณผ ์‚ญ์ œ์‹œ ๋ฐœ์ƒํ•˜๋Š” ๋ถ„๋ฆฌ์™€ ํ•ฉ๋ณ‘ ์—ฐ์‚ฐ์„ ์ตœ์†Œํ™”
  • B+ Tree
    B-Tree์˜ ์ˆœํšŒ์ž‘์—…(๋…ธ๋“œ ๋ฐฉ๋ฌธ)์˜ ์–ด๋ ค์›€์„ ๊ฐœ์„ 

*B-Tree๋Š” Balanced Tree(๊ท ํ˜•์žกํžŒ ์ด์ง„ํŠธ๋ฆฌ)๋กœ ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ๋ฐ ํŒŒ์ผ์‹œ์Šคํ…œ์— ๋„๋ฆฌ ์“ฐ์ด๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค. ์Šค์Šค๋กœ ๊ท ํ˜•์„ ์œ ์ง€ํ•จ

์ตœ๋Œ€, ์ตœ์†Œ๊ฐ’๋งŒ์„ ์ฐพ๊ณ ์ž ํ•œ๋‹ค๋ฉด Heap, ๋ชจ๋“  ๊ฐ’์„ ์ •๋ ฌํ•˜๊ณ  ์‹ถ๋‹ค๋ฉด BST

https://yoongrammer.tistory.com/71
https://gwang920.github.io/datastructure/BST/
https://code-lab1.tistory.com/217
https://sdesigner.tistory.com/79
https://wangin9.tistory.com/entry/B-tree-B-tree

  1. RBT(Red-Black Tree)์— ๋Œ€ํ•ด ์„ค๋ช…ํ•ด์ฃผ์„ธ์š”.

"๋ ˆ๋“œ-๋ธ”๋ž™ ํŠธ๋ฆฌ๋ž€ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ํŠน์ˆ˜ํ•œ ํ˜•ํƒœ๋กœ ์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ์˜ ํŠน์„ฑ์„ ๊ฐ€์ง€๋ฉด์„œ ์ตœ์•…์˜ ๊ฒฝ์šฐ์—๋„ ์ผ์ •ํ•œ ์‹คํ–‰์‹œ๊ฐ„์„ ๋ณด์žฅํ•˜์—ฌ ์‹ค์‹œ๊ฐ„ ์ฒ˜๋ฆฌ์™€ ๊ฐ™์€ ์‹คํ–‰์‹œ๊ฐ„์ด ์ค‘์š”ํ•œ ๊ฒฝ์šฐ์— ์œ ์šฉํ•œ ์ž๋ฃŒ๊ตฌ์กฐ"

๋ ˆ๋“œ-๋ธ”๋ž™ ํŠธ๋ฆฌ

์ž๊ฐ€ ๊ท ํ˜• ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ(self-balancing binary search tree)๋กœ O(logN)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค

๋ ˆ๋“œ-๋ธ”๋ž™ ํŠธ๋ฆฌ์—์„œ๋Š” ๋ฆฌํ”„ ๋…ธ๋“œ๋“ค์€ ๋น„์–ด์žˆ๊ณ , ์ž๋ฃŒ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์ง€ ์•Š๋‹ค

๋ ˆ๋“œ-๋ธ”๋ž™ ํŠธ๋ฆฌ๋ฅผ ํฌํ•จํ•œ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋Š”, ๋ชจ๋“  ๋…ธ๋“œ์— ๋Œ€ํ•ด '์ž์‹ ์ด ๊ฐ€์ง„ ์ž๋ฃŒ๋Š” ์ž์‹ ๋ณด๋‹ค ์˜ค๋ฅธ์ชฝ์— ์œ„์น˜ํ•œ ๋ถ€๋ถ„ํŠธ๋ฆฌ๊ฐ€ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋ชจ๋“  ์ž๋ฃŒ๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๊ณ , ์ž์‹ ๋ณด๋‹ค ์™ผ์ชฝ์— ์œ„์น˜ํ•œ ๋ถ€๋ถ„ํŠธ๋ฆฌ๊ฐ€ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋ชจ๋“  ์ž๋ฃŒ๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๋‹ค'๋ผ๋Š” ์กฐ๊ฑด์„ ๋งŒ์กฑํ•œ๋‹ค. ์ด๋Ÿฐ ํŠน์„ฑ ๋•Œ๋ฌธ์— ํŠน์ • ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ์ฐพ์•„ ๋‚ผ ์ˆ˜ ์žˆ์œผ๋ฉฐ, ๊ฐ ๊ตฌ์„ฑ์›์†Œ(elements)๊ฐ„์˜ ํšจ์œจ์ ์ธ in-order traversal์ด ๊ฐ€๋Šฅํ•˜๋‹ค.

  • ์ค‘์œ„์ˆœํšŒ : ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ โ†’ ๋ฃจํŠธ ๋…ธ๋“œ โ†’ ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ ์ˆœ์„œ๋กœ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธ
    ๋ฐ์ดํ„ฐ๊ฐ€ ์ž‘์€ ๊ฒƒ๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ(in order)๋ฐฉ๋ฌธํ•œ๋‹ค๊ณ  ์ƒ๊ฐํ•˜๋ฉด ๋จ
  • ์ „์œ„์ˆœํšŒpre order : ๋ฃจํŠธ โ†’ ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ โ†’ ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ

์ž๋ฃŒ์˜ ์‚ฝ์ž…๊ณผ ์‚ญ์ œ, ๊ฒ€์ƒ‰์—์„œ ์ตœ์•…์˜ ๊ฒฝ์šฐ์—๋„ ์ผ์ •ํ•œ ์‹คํ–‰ ์‹œ๊ฐ„์„ ๋ณด์žฅํ•œ๋‹ค(worst-case guarantees). ์ด๋Š” ์‹ค์‹œ๊ฐ„ ์ฒ˜๋ฆฌ์™€ ๊ฐ™์€ ์‹คํ–‰์‹œ๊ฐ„์ด ์ค‘์š”ํ•œ ๊ฒฝ์šฐ์— ์œ ์šฉ

  • ๋ฃจํŠธ ๋…ธ๋“œ๋ถ€ํ„ฐ ๊ฐ€์žฅ ๋จผ ์žŽ๋…ธ๋“œ ๊ฒฝ๋กœ๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ๊ฐ€, ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์žŽ๋…ธ๋“œ ๊ฒฝ๋กœ๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ์˜ ๋‘ ๋ฐฐ ๋ณด๋‹ค ํ•ญ์ƒ ์ž‘๋‹ค. ๋‹ค์‹œ ๋งํ•ด์„œ ๋ ˆ๋“œ-๋ธ”๋ž™ ํŠธ๋ฆฌ๋Š” ๊ฐœ๋žต์ (roughly)์œผ๋กœ ๊ท ํ˜•์ด ์žกํ˜€ ์žˆ๋‹ค
    โžก๏ธ ์‹œ๊ฐ„๋ณต์žก๋„๋Š” ํŠธ๋ฆฌ์˜ ๋†’์ด(๋˜๋Š” ๊นŠ์ด)์— ๋”ฐ๋ผ ๊ฒฐ์ •๋˜๊ธฐ ๋•Œ๋ฌธ์— ๋ณดํ†ต์˜ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์— ๋น„ํ•ด ํšจ์œจ์ ์ด๋‹ค
  • AVL์€ STRICTLY balancedํ•ด์„œ ์ตœ์•…์˜ ๊ฒฝ์šฐ ๋” ๋งŽ์€ rotation์ด ํ•„์š”ํ•˜๋‹ค
    • rotation: ํŠธ๋ฆฌ์˜ ์žฌ๊ตฌ์„ฑ ์ž‘์—…
      ํŠธ๋ฆฌ์— ์ž๋ฃŒ์˜ ์‚ฝ์ž…๊ณผ ์‚ญ์ œ๊ฐ€ ์ผ์–ด๋‚  ๋•Œ ๋ถˆ๊ท ํ˜•์ด ๋ฐœ์ƒํ•˜๊ณ  ๋กœํ…Œ์ด์…˜์„ ํ†ตํ•ด ๊ท ํ˜•์„ ์œ ์ง€ํ•œ๋‹ค

ํ•จ์ˆ˜ํ˜• ํ”„๋กœ๊ทธ๋ž˜๋ฐ์— ์œ ์šฉ

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC
https://withhamit.tistory.com/282

DP

  1. ๋™์  ๊ณ„ํš๋ฒ•(DP, Dynamic Programming)์— ๋Œ€ํ•ด ์„ค๋ช…ํ•ด์ฃผ์„ธ์š”.

"๋ณต์žกํ•œ ๋ฌธ์ œ๋ฅผ ๊ฐ„๋‹จํ•œ ์—ฌ๋Ÿฌ๊ฐœ์˜ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ  ํ‘ธ๋Š” ๊ฒƒ์œผ๋กœ ๋ฉ”๋ชจ์ด์ œ์ด์…˜์ด๋ผ๋Š” ๊ฐœ๋…์„ ํ†ตํ•ด ๋™์ผํ•œ ์—ฐ์‚ฐ์ด ๋ฐ˜๋ณต์ˆ˜ํ–‰๋˜์ง€ ์•Š๋„๋ก ์ €์žฅํ•ด์„œ ์‚ฌ์šฉํ•œ๋‹ค. ์ด ๋ฐฉ์‹์€ ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ์•ฝ๊ฐ„ ๋” ์‚ฌ์šฉํ•ด์„œ ์—ฐ์‚ฐ ์†๋„๋ฅผ ์ฆ๊ฐ€์‹œํ‚จ๋‹ค.
DP์—๋Š” bottom-up ๋ฐฉ์‹๊ณผ top-down๋ฐฉ์‹์ด ์žˆ๋‹ค bottom-up์€ ๋ฐ˜๋ณต๋ฌธ์„ ํ†ตํ•ด ๊ตฌํ˜„ํ•˜๋ฉฐ ์ž‘์€๋ฌธ์ œ์˜ ๋‹ต์„ ๋„์ถœํ•ด ํฐ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๋ฐฉ์‹์ด๊ณ  top-down์€ ๋ฌธ์ œ๋ฅผ ๋ฐ˜๋ณต๋˜๋Š” ์ž‘์€ ๋ถ€๋ถ„์œผ๋กœ ์ ์ฐจ ์ชผ๊ฐœ์„œ ์žฌ๊ท€๋ฅผ ํ†ตํ•ด ํ•ด๊ฒฐํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค."

๋ฉ”๋ชจ์ด์ œ์ด์…˜(memoization)์€ ์ปดํ“จํ„ฐ ํ”„๋กœ๊ทธ๋žจ์ด ๋™์ผํ•œ ๊ณ„์‚ฐ์„ ๋ฐ˜๋ณตํ•ด์•ผ ํ•  ๋•Œ, ์ด์ „์— ๊ณ„์‚ฐํ•œ ๊ฐ’์„ ๋ฉ”๋ชจ๋ฆฌ์— ์ €์žฅํ•จ์œผ๋กœ์จ ๋™์ผํ•œ ๊ณ„์‚ฐ์˜ ๋ฐ˜๋ณต ์ˆ˜ํ–‰์„ ์ œ๊ฑฐํ•˜์—ฌ ํ”„๋กœ๊ทธ๋žจ ์‹คํ–‰ ์†๋„๋ฅผ ๋น ๋ฅด๊ฒŒ ํ•˜๋Š” ๊ธฐ์ˆ ์ด๋‹ค.

โžก๏ธ๋ฐ˜๋ณต ์ˆ˜ํ–‰๋•Œ๋Š” ์—ฐ์‚ฐ ์—†์ด ์ €์žฅ๋œ ๊ฐ’์„ ๋ถˆ๋Ÿฌ์™€ ์‚ฌ์šฉํ•œ๋‹ค

  1. ๋™์  ๊ณ„ํš๋ฒ•(DP, Dynamic Programming)์ด ๊ฐ–๋Š” 2๊ฐ€์ง€ ์กฐ๊ฑด์€ ๋ฌด์—‡์ธ๊ฐ€์š”?

"DP๋ฅผ ์ด์šฉํ•ด์„œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ๋•Œ๋Š”์˜ 2๊ฐ€์ง€ ์กฐ๊ฑด์€ ํ•ด๋‹น ๋ฌธ์ œ๊ฐ€ ๋ถ€๋ถ„ ๋ฐ˜๋ณต๋˜์–ด ๊ตฌ์„ฑ๋˜์–ด์žˆ์œผ๋ฉด์„œ ์ด ๋ฌธ์ œ๋“ค์˜ ํ•ฉ์ด ์ „์ฒด ๋ฌธ์ œ์˜ ๋‹ต์ด ๋˜๋Š” ์ตœ์  ๋ถ€๋ถ„ ๊ตฌ์กฐ์—ฌ์•ผํ•œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค."

https://velog.io/@gillog/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

profile
looooggi

0๊ฐœ์˜ ๋Œ“๊ธ€