Tree

ํŠธ๋ฆฌ๋Š” ์ผ๋ฐ˜์ ์œผ๋กœ ๋Œ€์ƒ ์ •๋ณด์˜ ๊ฐ ํ•ญ๋ชฉ๋“ค์„ ๊ณ„์ธต์ ์œผ๋กœ ์—ฐ๊ด€๋˜๋„๋ก ๊ตฌ์กฐํ™”์‹œํ‚ค๊ณ ์ž ํ•  ๋•Œ ์‚ฌ์šฉํ•˜๋Š” ๋น„์„ ํ˜• ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค.
๋ฐ์ดํ„ฐ ์š”์†Œ๋“ค์˜ ๋‹จ์ˆœํ•œ ๋‚˜์—ด์ด ์•„๋‹Œ ๋ถ€๋ชจ-์ž์‹ ๊ด€๊ณ„์˜ ๊ณ„์ธต์  ๊ตฌ์กฐ๋กœ ํ‘œํ˜„์ด ๋œ๋‹ค.
ํŠธ๋ฆฌ๋Š” ๊ทธ๋ž˜ํ”„์˜ ํ•œ ์ข…๋ฅ˜์ด๋ฉฐ ์‚ฌ์ดํด์ด ์—†๋‹ค.

์šฉ์–ด

  • node: ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•˜๊ณ  ์žˆ๋Š” ๊ฐ ์š”์†Œ
  • Edge(๊ฐ„์„ ): ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•˜๊ธฐ ์œ„ํ•ด ๋…ธ๋“œ์™€ ๋…ธ๋“œ๋ฅผ ์—ฐ๊ฒฐํ•˜๋Š” ์„ 
  • Root Node: ์ตœ์ƒ์œ„ ๊ณ„์ธต์— ์กด์žฌํ•˜๋Š” ๋…ธ๋“œ
  • level: ํŠธ๋ฆฌ์˜ ํŠน์ • ๊นŠ์ด๋ฅผ ๊ฐ€์ง€๋Š” ๋…ธ๋“œ์˜ ์ง‘ํ•ฉ
  • degree(์ฐจ์ˆ˜): ํ•˜์œ„ ํŠธ๋ฆฌ ๊ฐœ์ˆ˜ / ๊ฐ„์„  ์ˆ˜ (degree) = ๊ฐ ๋…ธ๋“œ๊ฐ€ ์ง€๋‹Œ ๊ฐ€์ง€์˜ ์ˆ˜
  • Terminal Node ( = leaf Node, ๋‹จ๋ง ๋…ธ๋“œ) : ํ•˜์œ„์— ๋‹ค๋ฅธ ๋…ธ๋“œ๊ฐ€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์ง€ ์•Š์€ ๋…ธ๋“œ
  • Internal Node (๋‚ด๋ถ€๋…ธ๋“œ, ๋น„๋‹จ๋ง ๋…ธ๋“œ) : ๋‹จ๋ง ๋…ธ๋“œ๋ฅผ ์ œ์™ธํ•œ ๋ชจ๋“  ๋…ธ๋“œ๋กœ ๋ฃจํŠธ ๋…ธ๋“œ๋ฅผ ํฌํ•จํ•œ๋‹ค.

์ด์ง„ํŠธ๋ฆฌ(Binary Tree)

์ด์ง„ํŠธ๋ฆฌ๋Š” ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ๋…ธ๋“œ๋“ค์˜ ์ตœ๋Œ€ ์ฐจ์ˆ˜(degree)๊ฐ€ 2์ธ ๋…ธ๋“œ๋“ค๋กœ ๊ตฌ์„ฑ๋˜๋Š” ํŠธ๋ฆฌ์ด๋‹ค.

  • ์ด์ง„ํŠธ๋ฆฌ์˜ ๋ ˆ๋ฒจ i์—์„œ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๋…ธ๋“œ์˜ ์ˆ˜๋Š” 2^i์ด๋‹ค. (i>=0)
  • ๊นŠ์ด๊ฐ€ k์ธ ์ด์ง„ํŠธ๋ฆฌ๊ฐ€ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๋…ธ๋“œ์˜ ์ˆ˜๋Š” 2^k-1์ด๋‹ค.(k>=1)

์ด์ง„ํŠธ๋ฆฌ๋Š” ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ(Completable Binary Tree)์™€ ํฌํ™” ์ด์ง„ ํŠธ๋ฆฌ(Perfect Binary Tree), ์ „ ์ด์ง„ ํŠธ๋ฆฌ(Full Binary Tree)๋ผ๊ณ  ํ•˜๋Š” ํŠน๋ณ„ํ•œ ํŠธ๋ฆฌ ๊ตฌ์กฐ๋ฅผ ์ •์˜ํ•  ์ˆ˜ ์žˆ๋‹ค.

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

  • ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•˜๊ณ  ์žˆ๋Š” ์ž„์˜์˜ ๋‘ ๋‹จ๋ง ๋…ธ๋“œ์˜ ๋ ˆ๋ฒจ ์ฐจ์ด๊ฐ€ 1์ดํ•˜์ด๊ณ ,
  • ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์„ ์ œ์™ธํ•œ ๋ชจ๋“  ๋ ˆ๋ฒจ์— ์กด์žฌํ•  ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ๊ฐ–๊ณ  ์žˆ์œผ๋ฉฐ,
  • ์™ผ์ชฝ์—์„œ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์ฑ„์›Œ์ง€๋Š” ์ด์ง„ํŠธ๋ฆฌ
  • heap

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

  • ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ 0๊ฐœ ๋˜๋Š” 2๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ–๋Š” ํŠธ๋ฆฌ.

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

  • ๋ชจ๋“  ๋ ˆ๋ฒจ์— ๋…ธ๋“œ๊ฐ€ ์ฐจ์žˆ๋Š” ์ƒํƒœ๋กœ ์ตœ๋Œ€ ๋…ธ๋“œ ์ˆ˜์ธ 2^k-1๊ฐœ๋กœ ์ฑ„์›Œ์ ธ ์žˆ๋Š” ํŠธ๋ฆฌ
  • ์ „ ์ด์ง„ ํŠธ๋ฆฌ์ด๋ฉด์„œ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ์ธ ๊ฒฝ์šฐ

์ด์ง„ ํŠธ๋ฆฌ์˜ ํ‘œํ˜„

  1. ๋ฐฐ์—ด์„ ์ด์šฉํ•œ ํ‘œํ˜„

  • ๋นˆ ๋…ธ๋“œ์— ๋Œ€ํ•ด์„œ๋Š” ๊ณ„์† ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ๋ฉ”๋ชจ๋ฆฌ ๋‚ญ๋น„
  • ๋ฐ์ดํ„ฐ์˜ ์‚ฝ์ž…, ์‚ญ์ œ ์—ฐ์‚ฐ์‹œ ๋…ธ๋“œ์˜ ๋ ˆ๋ฒจ ๋ณ€๊ฒฝ์œผ๋กœ ์ธํ•œ ๋ฐ์ดํ„ฐ์˜ ์ด๋™ ๋ฐœ์ƒ
  1. ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ฅผ ์ด์šฉํ•œ ํ‘œํ˜„
  • ๊ฐ ๋…ธ๋“œ๋Š” dataํ•„๋“œ์™€ ์™ผ์ชฝ ์„œ๋ธŒ ํŠธ๋ฆฌ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ํ•„๋“œ, ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒ ํŠธ๋ฆฌ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ํ•„๋“œ๋กœ ๊ตฌ์„ฑ

์ด์ง„ ํŠธ๋ฆฌ ์ˆœํšŒ

  1. ์ค‘์œ„ ์ˆœํšŒ(inorder traversal)
    ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ -> ๋ฃจํŠธ -> ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ
    ๋ฃจํŠธ ๋…ธ๋“œ๊ฐ€ ๊ฐ€์šด๋ฐ์— ์˜จ๋‹ค.
    4-2-5-1-3
    .
  2. ํ›„์œ„ ์ˆœํšŒ(postorder traversal)
    ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ -> ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ -> ๋ฃจํŠธ
    ๋ฃจํŠธ ๋…ธ๋“œ๊ฐ€ ํ›„์œ„์— ์˜จ๋‹ค.
    4-5-2-3-1
    .
  3. ์ „์œ„ ์ˆœํšŒ(preorder traversal)
    ๋ฃจํŠธ -> ์™ผ์ชฝ -> ์˜ค๋ฅธ์ชฝ
    ๋ฃจํŠธ ๋…ธ๋“œ๊ฐ€ ๋งจ ์•ž์— ์˜จ๋‹ค.
    1-2-4-5-3

์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ(Binary Search Tree)

๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ ์ž์‹ ์˜ ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์—๋Š” ํ˜„์žฌ๋…ธ๋“œ๋ณด๋‹ค ์ž‘์€ ํ‚ค๊ฐ’์ด, ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์—๋Š” ํ˜„์žฌ ๋…ธ๋“œ๋ณด๋‹ค ํฐ ๊ฐ’์ด ์˜ค๋Š” ๊ทœ์น™์„ ๋งŒ์กฑํ•˜๋Š” ์ด์ง„ํŠธ๋ฆฌ์ด๋‹ค.

๋ชจ๋“  ์™ผ์ชฝ ์ž์‹๋“ค <= n < ๋ชจ๋“  ์˜ค๋ฅธ์ชฝ ์ž์‹๋“ค (๋ชจ๋“  ๋…ธ๋“œ n์— ๋Œ€ํ•ด์„œ ๋ฐ˜๋“œ์‹œ ์ฐธ)
๊ทœ์น™ 1. ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ๋…ธ๋“œ์— ์ €์žฅ๋œ ํ‚ค๋Š” ์œ ์ผํ•˜๋‹ค.
๊ทœ์น™ 2. ๋ฃจํŠธ ๋…ธ๋“œ์˜ ํ‚ค๊ฐ€ ์™ผ์ชฝ ์„œ๋ธŒ ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ์–ด๋– ํ•œ ๋…ธ๋“œ์˜ ํ‚ค๋ณด๋‹ค ํฌ๋‹ค.
๊ทœ์น™ 3. ๋ฃจํŠธ ๋…ธ๋“œ์˜ ํ‚ค๊ฐ€ ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒ ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ์–ด๋– ํ•œ ๋…ธ๋“œ์˜ ํ‚ค๋ณด๋‹ค ์ž‘๋‹ค.
๊ทœ์น™ 4. ์™ผ์ชฝ๊ณผ ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ๋„ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์ด๋‹ค.

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

Red-Black Tree

๋ ˆ๋“œ๋ธ”๋ž™ ํŠธ๋ฆฌ๋Š” ์ž๊ฐ€๊ท ํ˜•์ด์ง„ํƒ์ƒ‰ ํŠธ๋ฆฌ(self-balancing binary search tree)๋กœ์จ, ๋Œ€ํ‘œ์ ์œผ๋กœ ์—ฐ๊ด€๋ฐฐ์—ด(associative array) ๋“ฑ์„ ๊ตฌํ˜„ํ•˜๋Š”๋ฐ ์“ฐ์ด๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค.

ํŠน์ง•

balanced binary search tree

  • ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๊ฐ€ ํŽธํ–ฅ ํŠธ๋ฆฌ๊ฐ€ ๋  ๊ฒฝ์šฐ๋ฅผ ๋ฐฉ์ง€ํ•˜๋Š” ์กฐ๊ฑด์„ ์ถ”๊ฐ€ํ•จ
    • ๊ท ํ˜•์ด ์žกํ˜€ ์œ„ ๊ทธ๋ฆผ ๊ฐ™์€ ๊ฒฝ์šฐ๊ฐ€ ์•ˆ๋‚˜์˜จ๋‹ค -> ๋ ˆ๋“œ๋ธ”๋ž™ํŠธ๋ฆฌ์˜ ๋†’์ด๋Š” logn์— ๋ฐ”์šด๋“œ ๋œ๋‹ค -> ๋ ˆ๋“œ๋ธ”๋ž™ํŠธ๋ฆฌ์—์„œ ์‚ฝ์ž…, ์‚ญ์ œ, ๊ฒ€์ƒ‰ ์—ฐ์‚ฐ์€ O(logn)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๊ฒŒ ๋œ๋‹ค.
  • ์ž๋ฃŒ์˜ ์‚ฝ์ž…๊ณผ ์‚ญ์ œ, ๊ฒ€์ƒ‰์—์„œ ์ตœ์•…์˜ ๊ฒฝ์šฐ์—๋„ ์ผ์ •ํ•œ ์‹คํ–‰ ์‹œ๊ฐ„์„ ๋ณด์žฅํ•œ๋‹ค(worst-case guarantees).
    • ์ด๋Š” ์‹ค์‹œ๊ฐ„ ์ฒ˜๋ฆฌ์™€ ๊ฐ™์€ ์‹คํ–‰์‹œ๊ฐ„์ด ์ค‘์š”ํ•œ ๊ฒฝ์šฐ์— ์œ ์šฉํ•˜๊ฒŒ ์“ฐ์ผ ๋ฟ๋งŒ ์•„๋‹ˆ๋ผ, ์ผ์ •ํ•œ ์‹คํ–‰ ์‹œ๊ฐ„์„ ๋ณด์žฅํ•˜๋Š” ๋˜ ๋‹ค๋ฅธ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ๋งŒ๋“œ๋Š” ๋ฐ์—๋„ ์“ธ๋ชจ๊ฐ€ ์žˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค๋ฉด, ๊ฐ์ข… ๊ธฐํ•˜ํ•™ ๊ณ„์‚ฐ์— ์“ฐ์ด๋Š” ๋งŽ์€ ์ž๋ฃŒ ๊ตฌ์กฐ๋“ค์ด ๋ ˆ๋“œ-๋ธ”๋ž™ ํŠธ๋ฆฌ๋ฅผ ๊ธฐ๋ฐ˜์œผ๋กœ ๋งŒ๋“ค์–ด์ ธ ์žˆ๋‹ค.

์กฐ๊ฑด

  1. Root Property : ๋ฃจํŠธ๋…ธ๋“œ์˜ ์ƒ‰๊น”์€ ๊ฒ€์ •(Black)์ด๋‹ค.
    (์ถ”๊ฐ€๋˜๋Š” ๋…ธ๋“œ๋Š” ๋นจ๊ฐ•์ด๋‹ค)
  2. External Property : ๋ชจ๋“  external node๋“ค์€ ๊ฒ€์ •(Black)์ด๋‹ค.
  3. Internal Property : ๋นจ๊ฐ•(Red)๋…ธ๋“œ์˜ ์ž์‹์€ ๊ฒ€์ •(Black)์ด๋‹ค.
    == No Double Red(๋นจ๊ฐ„์ƒ‰ ๋…ธ๋“œ๊ฐ€ ์—ฐ์†์œผ๋กœ ๋‚˜์˜ฌ ์ˆ˜ ์—†๋‹ค.)
  4. Depth Property : ๋ชจ๋“  ๋ฆฌํ”„๋…ธ๋“œ์—์„œ Black Depth๋Š” ๊ฐ™๋‹ค.
    == ๋ฆฌํ”„๋…ธ๋“œ์—์„œ ๋ฃจํŠธ๋…ธ๋“œ๊นŒ์ง€ ๊ฐ€๋Š” ๊ฒฝ๋กœ์—์„œ ๋งŒ๋‚˜๋Š” ๋ธ”๋ž™๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜๋Š” ๊ฐ™๋‹ค.
    (๊ทธ๋ƒฅ ๋…ธ๋“œ์˜ ์ˆ˜๋Š” ๋‹ค๋ฅผ ์ˆ˜ ์žˆ์Œ.)

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

Double Red ํ•ด๊ฒฐ ์ „๋žต

์ด๋ ‡๊ฒŒ ์—ฐ์†ํ•ด์„œ ๋นจ๊ฐ• ๋…ธ๋“œ๊ฐ€ ์˜ค๊ฒŒ ๋˜์—ˆ์„ ๋•Œ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์€ ๋‘๊ฐ€์ง€ ์ด๋‹ค.

ํ˜„์žฌ insert๋œ ๋…ธ๋“œ์˜ uncle node(๋ถ€๋ชจ ๋…ธ๋“œ์˜ ํ˜•์ œ ๋…ธ๋“œ)๋ฅผ w๋ผ๊ณ  ํ• ๋•Œ,

  • w==Black ๐Ÿ‘‰ Restructuring
  • w==Red ๐Ÿ‘‰ Recoloring

์ฆ‰, insert๋…ธ๋“œ์˜ uncle node์˜ ์ƒ‰์„ ๊ธฐ์ค€์œผ๋กœ ํ•ด๊ฒฐ ์ „๋žต์ด ๋‹ฌ๋ผ์ง€๊ฒŒ ๋œ๋‹ค.

Restructing

  1. ๋‚˜(z)์™€ ๋‚ด ๋ถ€๋ชจ(v), ๋‚ด ๋ถ€๋ชจ์˜ ๋ถ€๋ชจ(Grand Parent)๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ
  2. ๋ฌด์กฐ๊ฑด ๊ฐ€์šด๋ฐ ์žˆ๋Š” ๊ฐ’์„ ๋ถ€๋ชจ๋กœ ๋งŒ๋“ค๊ณ  ๋‚˜๋จธ์ง€ ๋‘˜์„ ์ž์‹์œผ๋กœ ๋งŒ๋“ ๋‹ค.
  3. ์˜ฌ๋ผ๊ฐ„ ๊ฐ€์šด๋ฐ ์žˆ๋Š” ๊ฐ’์„ ๊ฒ€์ •(Black)์œผ๋กœ ๋งŒ๋“ค๊ณ  ๊ทธ ๋‘์ž์‹๋“ค์„ ๋นจ๊ฐ•(Red)๋กœ ๋งŒ๋“ ๋‹ค.
  • Restructuring์€ ๋‹ค๋ฅธ ์„œ๋ธŒํŠธ๋ฆฌ์— ์˜ํ–ฅ์„ ๋ผ์น˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์—(4๋ฒˆ์กฐ๊ฑด) ํ•œ๋ฒˆ์˜ ๊ณผ์ •์œผ๋กœ ์ข…๋ฃŒ.
    • Restructing ์ „ํ›„์˜ Black ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜์— ๋ณ€ํ™”๊ฐ€ ์—†๊ธฐ๋•Œ๋ฌธ์— ๋‹ค๋ฅธ์„œ๋ธŒํŠธ๋ฆฌ์— ์˜ํ–ฅ์„ ๋ผ์น˜์ง€ ์•Š์Œ
  • Restructuring์ž์ฒด์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋Š” O(1)์— ๋๋‚˜์ง€๋งŒ, (์ˆœ์„œ๊ฒฐ์ •์‹œ๊ฐ„ - ์ƒ์ˆ˜์‹œ๊ฐ„, ํŠธ๋ฆฌ๋กœ ๋งŒ๋“œ๋Š”์‹œ๊ฐ„ - ์ƒ์ˆ˜์‹œ๊ฐ„, ์›๋ž˜์žˆ๋˜ ๋…ธ๋“œ๋“ค์˜ ๊ตฌ์กฐ๋“ค์„ ๋ฐ”๊ฟ”์ฃผ๋Š” ์‹œ๊ฐ„ - ์ƒ์ˆ˜์‹œ๊ฐ„)
    Restructuring์€ ์–ด๋–ค ๋…ธ๋“œ๋ฅผ insertionํ•œ ๋’ค ์ผ์–ด๋‚˜๋ฏ€๋กœ ์ด ์ˆ˜ํ–‰์‹œ๊ฐ„์€ O(logn)์ด๋‹ค. ์ง€๊ธˆ ํ˜„์žฌ ๋…ธ๋“œ๊ฐ€ ๋“ค์–ด๊ฐˆ ์œ„์น˜๋ฅผ ๋จผ์ € ์ฐพ์•„์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ.

Recoloring

  1. ํ˜„์žฌ insert๋œ ๋…ธ๋“œ(c)์˜ ๋ถ€๋ชจ(p)์™€ ๊ทธ ํ˜•์ œ(u)๋ฅผ ๊ฒ€์ •(Black)์œผ๋กœ ํ•˜๊ณ  Grand Parent(๋‚ด ๋ถ€๋ชจ์˜ ๋ถ€๋ชจ)๋ฅผ ๋นจ๊ฐ•(Red)๋กœ ํ•œ๋‹ค.
  2. Grand Parent(๋‚ด ๋ถ€๋ชจ์˜ ๋ถ€๋ชจ)๊ฐ€ Root node๊ฐ€ ์•„๋‹ˆ์—ˆ์„ ์‹œ Double Red๊ฐ€ ๋‹ค์‹œ ๋ฐœ์ƒ ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • Recoloring์˜ ๊ฒฝ์šฐ Restructuring๊ณผ ๋‹ค๋ฅด๊ฒŒ propagation๋  ์ˆ˜ ์žˆ๋‹ค. ์ตœ์•…์˜๊ฒฝ์šฐ Root๊นŒ์ง€ ๊ฐˆ ์ˆ˜ ์žˆ์Œ.

AVL Tree์™€ Red Black Tree ์ฐจ์ด

  • AVL Tree๊ฐ€ Red Black Tree๋ณด๋‹ค ๋น ๋ฅธ Search๋ฅผ ์ œ๊ณต
    • AVL Tree๊ฐ€ ๋” ์—„๊ฒฉํ•œ Balanced๋ฅผ ์œ ์ง€ํ•˜๊ณ  ์žˆ๊ธฐ ๋•Œ๋ฌธ
  • Red Black Tree์€ AVL Tree๋ณด๋‹ค ๋น ๋ฅธ ์‚ฝ์ž…๊ณผ ์ œ๊ฑฐ๋ฅผ ์ œ๊ณต
    • AVL Tree๋ณด๋‹ค Balanced๋ฅผ ๋Š์Šจํ•˜๊ฒŒ ์œ ์ง€ํ•˜๊ณ  ์žˆ๊ธฐ ๋•Œ๋ฌธ
  • Red Black Tree๋Š” AVL Tree๋ณด๋‹ค ์ƒ‰๊น”์„ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•ด ๋” ๋งŽ์€ Space Complexity๊ฐ€ ํ•„์š”
  • Red Black Tree๋Š” ๋Œ€๋ถ€๋ถ„์˜ ์–ธ์–ด์˜ map, multimap, multiset์—์„œ ์‚ฌ์šฉ
  • AVL tree๋Š” ์กฐํšŒ์— ์†๋„๊ฐ€ ์ค‘์š”ํ•œ Database์—์„œ ์‚ฌ์šฉ

Heap

ํž™(heap)์€ ์™„์ „์ด์ง„ํŠธ๋ฆฌ(Complete binary tree) ๋ฅผ ๊ธฐ๋ณธ์œผ๋กœ ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ(tree-based structure) (์‹œ๊ฐ„๋ณต์žก๋„ : O(log N))

ํŠน์ง•

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

ํž™์˜ ์ข…๋ฅ˜

์ตœ๋Œ€ ํž™

๋ถ€๋ชจ๋…ธ๋“œ์˜ ํ‚ค๊ฐ’์ด ์ž์‹๋…ธ๋“œ์˜ ํ‚ค๊ฐ’๋ณด๋‹ค ํ•ญ์ƒ ํฐ ํž™
Max Heap์—์„œ๋Š” Root node ์— ์žˆ๋Š” ๊ฐ’์ด ์ œ์ผ ํฌ๋ฏ€๋กœ, ์ตœ๋Œ€๊ฐ’์„ ์ฐพ๋Š”๋ฐ ์†Œ์š”๋˜๋Š” ์—ฐ์‚ฐ์˜ time complexity ์ด O(1)์ด๋‹ค. ๊ทธ๋ฆฌ๊ณ  complete binary tree์ด๊ธฐ ๋•Œ๋ฌธ์— ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์—ฌ ํšจ์œจ์ ์œผ๋กœ ๊ด€๋ฆฌํ•  ์ˆ˜ ์žˆ๋‹ค. (์ฆ‰, random access ๊ฐ€ ๊ฐ€๋Šฅํ•˜๋‹ค. Min heap ์—์„œ๋Š” ์ตœ์†Œ๊ฐ’์„ ์ฐพ๋Š”๋ฐ ์†Œ์š”๋˜๋Š” ์—ฐ์‚ฐ์˜ time complexity ๊ฐ€ O(1)์ด๋‹ค.)

์ตœ์†Œ ํž™

๋ถ€๋ชจ๋…ธ๋“œ์˜ ํ‚ค๊ฐ’์ด ์ž์‹๋…ธ๋“œ์˜ ํ‚ค๊ฐ’๋ณด๋‹ค ํ•ญ์ƒ ์ž‘์€ ํž™
ํ‚ค๊ฐ’์˜ ๋Œ€์†Œ๊ด€๊ณ„๋Š” ๋ถ€๋ชจ-์ž์‹ ๊ฐ„์—๋งŒ ์„ฑ๋ฆฝํ•˜๊ณ  ํ˜•์ œ๊ฐ„์—๋Š” ์„ฑ๋ฆฝํ•˜์ง€ ์•Š๋Š”๋‹ค.

์‚ฝ์ž…

(max heap ๊ธฐ์ค€)

  1. ํž™์˜ ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ์›์†Œ์— ์›ํ•˜๋Š” ๊ฐ’์„ ์‚ฝ์ž…ํ•œ๋‹ค.
  2. ๋ถ€๋ชจ๊ฐ€ ์‚ฝ์ž… ์›์†Œ๋ณด๋‹ค ์ž‘๋‹ค๋ฉด(Max_Heap๊ธฐ์ค€) ๋ถ€๋ชจ์™€ ์ž์‹์˜ ๊ฐ’์„ ๊ตํ™˜ํ•œ๋‹ค.
  3. 2๋ฒˆ์—์„œ ๋ถ€๋ชจ๊ฐ€ ์—†๊ฑฐ๋‚˜, ๋ถ€๋ชจ๊ฐ€ ์ž์‹๋ณด๋‹ค ํด ๊ฒฝ์šฐ์— ์ข…๋ฃŒ

์‚ญ์ œ

(max heap ๊ธฐ์ค€)

  1. ๋ฃจํŠธ๋…ธ๋“œ๋ฅผ ์‚ญ์ œํ•˜๊ณ  ํž™์˜ ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋กœ ๊ฐ€์ ธ์˜จ๋‹ค.
  2. ๊ฐ€์ ธ์˜จ ๋ฃจํŠธ์™€ ์ž์‹๋…ธ๋“œ๋ฅผ ๋น„๊ตํ•˜๊ณ  ๊ฐ€์ ธ์˜จ ๋…ธ๋“œ๊ฐ€ ์ž‘์„ ๊ฒฝ์šฐ ์ž์‹๊ณผ ์œ„์น˜ ๋ณ€๊ฒฝ
  3. ์ž์‹ ๋…ธ๋“œ๊ฐ€ ๋”์ด์ƒ ์—†๊ฑฐ๋‚˜, ์ž์‹๋ณด๋‹ค ํด ๊ฒฝ์šฐ ์ข…๋ฃŒ

์ฐธ๊ณ 
https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
https://wayhome25.github.io/cs/2017/04/19/cs-23/
https://coderkoo.tistory.com/10
https://zeddios.tistory.com/237
https://nesoy.github.io/articles/2018-08/Algorithm-RedblackTree

profile
๊ฐœ๋ฐœ์˜ 'ใ„ฑ'์„ ์•Œ์•„๊ฐ€๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.๐Ÿ˜Š๐Ÿคž

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