tree 2

[Data Structure] ํž™ (Heap)

ํž™ (Heap) ? ๋ฐ์ดํ„ฐ์—์„œ ์ตœ๋Œ€๊ฐ’๊ณผ ์ตœ์†Œ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ์ฐพ๊ธฐ ์œ„ํ•ด ๊ณ ์•ˆ๋œ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ(Complete Binary Tree) - ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ : ๋…ธ๋“œ๋ฅผ ์‚ฝ์ž…ํ•  ๋•Œ, ์ตœํ•˜๋‹จ ์™ผ์ชฝ ๋…ธ๋“œ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ์‚ฝ์ž…ํ•˜๋Š” ํŠธ๋ฆฌ ํž™์„ ์‚ฌ์šฉํ•˜๋Š” ์ด์œ  ๋ฐฐ์—ด์— ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๊ณ , ์ตœ๋Œ€๊ฐ’๊ณผ ์ตœ์†Œ๊ฐ’์„ ์ฐพ์œผ๋ ค๋ฉด O(n)์ด ๊ฑธ๋ฆผ

[Data Structure] ํŠธ๋ฆฌ (Tree)

ํŠธ๋ฆฌ (Tree) ๊ตฌ์กฐ Node์™€ Branch๋ฅผ ์ด์šฉํ•ด์„œ, ์‚ฌ์ดํด์„ ์ด๋ฃจ์ง€ ์•Š๋„๋ก ๊ตฌ์„ฑํ•œ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ ์ด์ง„ ํŠธ๋ฆฌ(Binary Tree) ํ˜•ํƒœ์˜ ๊ตฌ์กฐ, ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ตฌํ˜„์— ๋งŽ์ด ์‚ฌ์šฉ ํŠธ๋ฆฌ ๊ด€๋ จ ์šฉ์–ด Node : ํŠธ๋ฆฌ์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๋Š” ๊ธฐ๋ณธ ์š”์†Œ(๋ฐ์ดํ„ฐ์™€ ๋‹ค๋ฅธ ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ์— ๋Œ€ํ•œ Branch ์ •๋ณด ํฌํ•จ) Root Node : ํŠธ๋ฆฌ ๋งจ ์œ„์— ์žˆ๋Š” ๋…ธ๋“œ Level : ์ตœ์ƒ์œ„ ๋…ธ๋“œ๋ฅผ Level 0 ์œผ๋กœ ํ–ˆ์„ ๋•Œ, ํ•˜์œ„ Branch๋กœ ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ์˜ ๊นŠ์ด Parent Node : ์–ด๋–ค ๋…ธ๋“œ์˜ ๋‹ค์Œ ๋ ˆ๋ฒจ์— ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ Child Node : ์–ด๋–ค ๋…ธ๋“œ์˜ ์ƒ์œ„ ๋ ˆ๋ฒจ์— ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ Leaf Node(Terminal Node) : Child Node๊ฐ€ ํ•˜๋‚˜๋„ ์—†๋Š” ๋…ธ๋“œ Sibling (Brother Node) : ๋™์ผ..