๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
IT

[์ž๋ฃŒ๊ตฌ์กฐ] ํŠธ๋ฆฌ ์šฉ์–ด๋ž€?

by yunamom 2022. 5. 1.
๋ฐ˜์‘ํ˜•

โœจํŠธ๋ฆฌ(Tree) ๋ž€?  

 

๋ถ€๋ชจ-์ž์‹ ๊ฐœ๋…์„ ๊ฐ€์ง€๋Š” ๋น„์ˆœํ™˜์  ๊ฒฝ๋กœ๋กœ ์—ฐ๊ฒฐ๋˜์–ด์žˆ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค.

 

by yunamom

 

โœจํŠธ๋ฆฌ ๊ด€๋ จ ์ฃผ์š” ์šฉ์–ด  

 

by yunamom

๊ตฌ๋ถ„ ์„ค๋ช… ์˜ˆ์‹œ
Node ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ๊ธฐ๋ณธ ์›์†Œ ์˜ˆ) A,B,C,D,E,F,G,H,I,J
Root node
(๋ฟŒ๋ฆฌ ๋…ธ๋“œ)
(๋ฟŒ๋ฆฌ)๋ถ€๋ชจ๊ฐ€ ์—†๋Š” ์ตœ์ƒ์œ„ ๋ฃจํŠธ ๋…ธ๋“œ
ํŠธ๋ฆฌ๋Š” ํ•˜๋‚˜์˜ ๋ฃจํŠธ ๋…ธ๋“œ๋งŒ์„ ๊ฐ€์ง„๋‹ค.
์˜ˆ) A
Leaf node
(์žŽ ๋…ธ๋“œ)
์ž์‹์ด ์—†๋Š” ๋…ธ๋“œ (๋งจ ๋งˆ์ง€๋ง‰ ๋ ๋…ธ๋“œ) ์˜ˆ) H, I, J, F, G
Internal
(๋‚ด๋ถ€ ๋…ธ๋“œ)
Leaf node ๊ฐ€ ์•„๋‹Œ ๋…ธ๋“œ
Edge/Branch/Link
(๊ด€๊ณ„,๊ฐ€์ง€,๋ถ„๊ธฐ)
๋…ธ๋“œ๋ฅผ ์—ฐ๊ฒฐํ•˜๋Š” ์„  , ๋ฟŒ๋ฆฌ(root)์™€ ์žŽ(leaf)์‚ฌ์ด์˜ ๋ชจ๋“  ๋…ธ๋“œ ์˜ˆ) A, B, C, D, E
Degree
(๋…ธ๋“œ์˜ ์ฐจ์ˆ˜)
ํ•˜์œ„ ํŠธ๋ฆฌ๊ฐœ์ˆ˜ / ๊ฐ ๋…ธ๋“œ๊ฐ€ ์ง€๋‹Œ ๊ฐ€์ง€์˜ ์ˆ˜
(์—ฐ๊ฒฐ๋œ์ž์‹ ๋…ธ๋“œ์˜ ์ˆ˜)
์˜ˆ) A์˜ Degree = 2
Order
(๊ณ„์ˆ˜/์ฐจ์ˆ˜)
์ž์‹ ๋…ธ๋“œ๋“ค ์ค‘ ์ตœ๋Œ€ ๊ฐœ์ˆ˜
Depth
(๋…ธ๋“œ์˜ ๊นŠ์ด)
๋ฃจํŠธ์—์„œ ์–ด๋–ค ๋…ธ๋“œ์— ๋„๋‹ฌํ•˜๊ธฐ ์œ„ํ•ด ๊ฑฐ์ณ์•ผ ํ•˜๋Š” ๊ฐ„์„ ์˜ ์ˆ˜ ์˜ˆ) D ์˜ ๊ฒฝ๋กœ ๊นŠ์ด 2
Level
(๋…ธ๋“œ์˜ ๋ ˆ๋ฒจ)
ํŠน์ • ๊นŠ์ด๋ฅผ ๊ฐ€์ง€๋Š” ๋…ธ๋“œ์˜ ์ง‘ํ•ฉ (๊ฐ™์€ ๊นŠ์ด) ์˜ˆ) A์˜ ๋ ˆ๋ฒจ : ๋ ˆ๋ฒจ0
Height
(๋†’์ด)
๋ฃจํŠธ ๋…ธ๋“œ์—์„œ ๊ฐ€์žฅ ๊นŠ์ˆ™ํžˆ ์žˆ๋Š” ๋…ธ๋“œ์˜ ๊นŠ์ด ์˜ˆ) ๊ฐ€์žฅ ๊ธด ๊นŠ์ด : 4
Size
(ํฌ๊ธฐ)
ํŠน์ • ๋…ธ๋“œ๊ฐ€ ์ž์‹ ์„ ํฌํ•จํ•œ ์ž์†์˜ ์ˆ˜ ์˜ˆ) ๋…ธ๋“œ B์˜ ํฌ๊ธฐ : 6
Parent node
(๋ถ€๋ชจ)
์„ ์กฐ( ancestor ) : ๋ถ€๋ชจ ๋…ธ๋“œ์™€ ๊ทธ์˜ ๋ถ€๋ชจ๋“ค ์˜ˆ) D, E์˜ ๋ถ€๋ชจ๋…ธ๋“œ๋Š” B
Child node
(์ž์‹)
์ž์†( descendant ) : ์ž์‹ ๋…ธ๋“œ์™€ ๊ทธ ์ž์‹๋“ค ์˜ˆ) B์˜ ์ž์‹๋…ธ๋“œ๋Š” D, E
Sibling node
(ํ˜•์ œ)
๊ฐ™์€ ๋ถ€๋ชจ๋ฅผ ๊ฐ€์ง€๋Š” ๋…ธ๋“œ ์˜ˆ) D, E๋Š” ๊ฐ™์€ ๋ถ€๋ชจ๋ฅผ ๊ฐ–๋Š” ํ˜•์ œ๋…ธ๋“œ
Subtree
(์„œ๋ธŒํŠธ๋ฆฌ)
A๋ฅผ ๊ธฐ์ค€์œผ๋กœ B๋ฅผ ๋ฃจํŠธ๋กœ ํ•˜๋ฉด ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ, C๋ฅผ ๋ฃจํŠธ๋กœ ํ•˜๋ฉด ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ๋ผ๊ณ  ํ•œ๋‹ค.

 

300x250

์ฝ”๋“œ