peewoong 2024. 4. 12. 15:36

๐ŸŸฉ ํž™ = ํ‡ด์ ๋ฌผ

๋ฐ”๋‹ท์† ํ‡ด์ ๋ฌผ์ฒ˜๋Ÿผ ์•„๋ž˜์— ํฐ ๋ฐ”์œ„, ์ค‘๊ฐ„ ์ •๋„์˜ ๋Œ, ๊ทธ ์œ„์— ์ž‘์€ ๋ชจ๋ž˜ ์ˆœ์œผ๋กœ ์Œ“์—ฌ์žˆ๋‹ค.

 

๐ŸŸฉ ๊ทธ๋ž˜ํ”„์˜ ํŠธ๋ฆฌ ๊ตฌ์กฐ ์ค‘ ํ•˜๋‚˜(์™„์ „ ์ด์ง„ํŠธ๋ฆฌ)

๊ฐ ๋…ธ๋“œ์˜ ํ‚ค ๊ฐ’์ด ๊ทธ ์ž์‹์˜ ํ‚ค ๊ฐ’๋ณด๋‹ค ์ž‘์ง€ ์•Š๊ฑฐ๋‚˜(์ตœ๋Œ€ํž™), ํฌ์ง€ ์•Š์€(์ตœ์†Œํž™) ์™„์ „ ์ด์ง„ํŠธ๋ฆฌ

์™„์ „ ์ด์ง„ํŠธ๋ฆฌ๋Š” ์ค‘๋ณต์„ ํ—ˆ์šฉํ•˜์ง€ ์•Š์ง€๋งŒ ํž™์€ ํ—ˆ์šฉํ•œ๋‹ค.

 

๐ŸŸฉ ์ •๋ ฌ์„ ํšจ์œจ์ ์œผ๋กœ ์ˆ˜ํ–‰ํ•˜๋Š” ํŠธ๋ฆฌ

'์šฐ์„ ์ˆœ์œ„ ํ'๋ฅผ ๊ตฌํ˜„ํ•  ๋•Œ ์‚ฌ์šฉ

์ตœ๋Œ“๊ฐ’๊ณผ ์ตœ์†Ÿ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ์ฐพ๊ธฐ ์œ„ํ•ด ๊ณ ์•ˆ๋จ

๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜๋ฉด O(n)๋งŒํผ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฌ์ง€๋งŒ, ํž™์„ ์‚ฌ์šฉํ•˜๋ฉด O(logn)๋งŒํผ ์†Œ์š”๋˜๋ฏ€๋กœ, ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•  ๋•Œ๋ณด๋‹ค ๋น ๋ฅด๊ฒŒ ์ตœ์†Ÿ๊ฐ’, ์ตœ๋Œ“๊ฐ’์„ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

 

๐ŸŸฉ ํž™์—์„œ์˜ ๋ถ€๋ชจ-์ž์‹ ๊ด€๊ณ„

์˜ค๋ฅธ์ชฝ ์ž์‹์˜ ์ธ๋ฑ์Šค = (๋ถ€๋ชจ์˜ ์ธ๋ฑ์Šค) * 2 + 1

์™ผ์ชฝ ์ž์‹์˜ ์ธ๋ฑ์Šค = (๋ถ€๋ชจ์˜ ์ธ๋ฑ์Šค)  * 2

๋ถ€๋ชจ์˜ ์ธ๋ฑ์Šค = (์ž์‹์˜ ์ธ๋ฑ์Šค) / 2

 

๐ŸŒŸ ์šฐ์„ ์ˆœ์œ„ ํ

๋Œ€๊ธฐ ๋ฆฌ์ŠคํŠธ์—์„œ ํ•ญ์ƒ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋†’์€ ์‚ฌ๋žŒ์ด ๋จผ์ € ์„œ๋น„์Šค๋ฅผ ๋ฐ›๋Š” ๊ตฌ์กฐ

๋ฐ์ดํ„ฐ ๊ตฌ์กฐ์˜ ํ•˜๋‚˜๋กœ์„œ ๋ฐ์ดํ„ฐ๋ฅผ ์ž์œ ๋กญ๊ฒŒ ์ถ”๊ฐ€ํ•  ์ˆ˜ ์žˆ๋‹ค. ๋ฐ˜๋ฉด ๋ฐ์ดํ„ฐ๋ฅผ ์ถ”์ถœํ•  ๋•Œ๋Š” ์ตœ์†Ÿ๊ฐ’๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ์„ ํƒ

 

ํž™์„ ํ‘œํ˜„ํ•˜๋Š” ํŠธ๋ฆฌ ๊ตฌ์กฐ์—์„œ ๊ฐ ์ •์ ์„ '๋…ธ๋“œ(node)'๋ผ ํ•œ๋‹ค.

๋…ธ๋“œ๋Š” ์ตœ๋Œ€ 2๊ฐœ์˜ ์ž์‹์„ ๊ฐ–๋Š”๋‹ค. ์œ„์—์„œ๋ถ€ํ„ฐ ์ฑ„์›Œ์ง€๋ฉฐ, ๊ฐ™์€ ์ธต์—์„œ๋Š” ์™ผ์ชฝ๋ถ€ํ„ฐ ์ฑ„์›Œ์ง„๋‹ค.

๋˜ํ•œ, ํŠธ๋ฆฌ ๋ชจ์–‘์€ ๋ฐ์ดํ„ฐ์˜ ๊ฐœ์ˆ˜์— ์˜ํ•ด ์ •ํ•ด์ง„๋‹ค.

 

 

 

๐ŸŒŸ ์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ(BST, Binary Search Tree)

๐ŸŸฉ ์ด์ง„ ํƒ์ƒ‰ + ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ

์ด์ง„ ํƒ์ƒ‰์˜ ํšจ์œจ์ ์ธ ํƒ์ƒ‰ ๋Šฅ๋ ฅ์€ ์œ ์ง€ + ๋นˆ๋ฒˆํ•œ ์ž๋ฃŒ์˜ ์ž…๋ ฅ๊ณผ ์‚ญ์ œ๋ฅผ ๊ฐ€๋Šฅํ•˜๋„๋ก ํ•œ๋‹ค.

 

๐ŸŸฉ ๊ฐ ๋…ธ๋“œ์—์„œ ์™ผ์ชฝ์˜ ์ž์‹ ๋…ธ๋“œ๋Š” ํ•ด๋‹น ๋…ธ๋“œ๋ณด๋‹ค ์ž‘์€ ๊ฐ’์œผ๋กœ, ์˜ค๋ฅธ์ชฝ์˜ ์ž์‹ ๋…ธ๋“œ๋Š” ํ•ด๋‹น ๋…ธ๋“œ๋ณด๋‹ค ํฐ ๊ฐ’์œผ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค.

 

 

๐ŸŒŸ ํž™๊ณผ ์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ

๐ŸŸฉ ๊ณตํ†ต์ 

๋ชจ๋‘ ์™„์ „ ์ด์ง„ํŠธ๋ฆฌ

 

๐ŸŸฉ ์ฐจ์ด์ 

์ตœ๋Œ€ํž™ : ๊ฐ ๋…ธ๋“œ์˜ ๊ฐ’์ด ์ž์‹ ๋…ธ๋“œ๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๋‹ค.

์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ : ๊ฐ ๋…ธ๋“œ์˜ ์™ผ์ชฝ ์ž์‹์€ ๋” ์ž‘์€ ๊ฐ’์œผ๋กœ, ์˜ค๋ฅธ์ชฝ ์ž์‹์€ ๋” ํฐ ๊ฐ’์œผ๋กœ ์ด๋ฃจ์–ด์ ธ์žˆ๋‹ค.

์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ < ๋ถ€๋ชจ ๋…ธ๋“œ < ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ

ํž™์€ ์™ผ/์˜ค๋ฅธ์ชฝ ๋…ธ๋“œ์˜ ๊ฐ’์˜ ํฌ๊ธฐ๋Š” ์ƒ๊ด€์—†๋‹ค.

 

ํž™์€ ์ตœ๋Œ€/์ตœ์†Œ ๊ฒ€์ƒ‰์„, ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋Š” ํƒ์ƒ‰์„ ์œ„ํ•œ ๊ตฌ์กฐ

 

 

๐ŸŸฉ ์‚ฝ์ž…

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

๋ถ€๋ชจ์™€ ํฌ๊ธฐ ๋น„๊ตํ•˜๋ฉด์„œ ์œ„์น˜ ๋ณ€๊ฒฝ ๋ฐ ์‚ฝ์ž…ํ•œ๋‹ค.

 

๐ŸŸฉ ์‚ญ์ œ

ํž™ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ๋ชฉํ‘œ๋Š” ์ตœ๋Œ“๊ฐ’์ด๋‚˜ ์ตœ์†Ÿ๊ฐ’์„ ์•Œ์•„๋‚ด๋Š” ๊ฒƒ

๋•Œ๋ฌธ์— ๋ฐ์ดํ„ฐ๊ฐ€ ์‚ญ์ œ๋œ๋‹ค๋ฉด ๊ฐ€์žฅ ํฐ ๊ฐ’์ธ ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ๊ฐ’์ด ์‚ญ์ œ๋œ๋‹ค.

 

 

๋ถ€๋ชจ ๋…ธ๋“œ๊ฐ€ ๋น„์–ด์žˆ์œผ๋ฏ€๋กœ, ๊ฐ€์žฅ ์ตœํ•˜๋‹จ๋ถ€ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋กœ ์˜ฎ๊ธด๋‹ค.

๋ถ€๋ชจ ๋…ธ๋“œ์ธ 8๋ณด๋‹ค ๊ฐ’์ด ํฐ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์žˆ๋Š”์ง€ ๋น„๊ตํ•œ๋‹ค.

 

๐Ÿ‘‰ ์™ผ์ชฝ/์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ ๋ชจ๋‘ ๋ถ€๋ชจ ๋…ธ๋“œ๋ณด๋‹ค ํด ๊ฒฝ์šฐ,

์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ์™€ ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๋น„๊ตํ•˜์—ฌ, ๋” ํฐ ์ž์‹ ๋…ธ๋“œ์™€ ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ์œ„์น˜๋ฅผ ๋ฐ”๊พผ๋‹ค.

 

๐Ÿ‘‰ ์™ผ์ชฝ/์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ ์ค‘ ํ•˜๋‚˜๋งŒ ๋ถ€๋ชจ ๋…ธ๋“œ๋ณด๋‹ค ํด ๊ฒฝ์šฐ,

๋‘˜ ์ค‘์— ๋ถ€๋ชจ ๋…ธ๋“œ๋ณด๋‹ค ํฐ ์ž์‹ ๋…ธ๋“œ์™€ ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ์œ„์น˜๋ฅผ ๋ฐ”๊พผ๋‹ค.