[λ°λΈμ½μ€ Day5] 2022.10.21
πμ€λ λ°°μ΄ κ²
νΈλ¦¬
: λ Έλλ‘ κ΅¬μ±λμ΄ μμΌλ©° λͺ¨λ μ μ μ΄ μ°κ²°λ κ·Έλνμ΄λ€.
루νΈ(Root): λΆλͺ¨κ° μλ λ Έλ, μ΅κ³ μ μ
λ Έλ(Node): ꡬμ±μμ
κ°μ (Edge): λ Έλμ λ Έλ κ°μ μ°κ²°μ
리νλ Έλ(Leaf Node): μμμ΄ μλ λ Έλ
λ 벨(Level): λ Έλμμ νΉμ λ ΈλκΉμ§μ κΉμ΄
λ그리(Degree): λ Έλμ μμμ μ/κ°μ μ μ
κΉμ΄(depth): 루νΈμμ νΉμ λ ΈλκΉμ§μ κ°μ μ μ
λμ΄(height): 리νμμ νΉμ λ ΈλκΉμ§ κ°μ₯ κΈ΄ κ²½λ‘μ κ°μ μ μ
νΉμ§
- λ£¨νΈ μ μ μ μ μΈν λͺ¨λ μμ λ Έλλ νλμ λΆλͺ¨ λ Έλλ₯Ό κ°μ§λ€.
- λ Έλκ° nκ°μΈ νΈλ¦¬λ νμ n-1κ°μ κ°μ μ κ°μ§λ€.
μ’ λ₯
- νΈν₯νΈλ¦¬ : λͺ¨λ λ Έλλ€μ΄ νλμ μμλ§μ κ°μ§ κ²½μ°
- μ΄μ§νΈλ¦¬: κ° λ Έλμ μμ λ Έλκ° 2κ° μ΄νμΈ κ²½μ°
-μμ μ΄μ§νΈλ¦¬: λ§μ§λ§ λ 벨μ μ μΈνκ³ μ μ μ΄ λͺ¨λ μ±μμ Έ μλ κ²½μ°
-ν¬ν μ΄μ§νΈλ¦¬: λ§μ§λ§ λ 벨λ λͺ¨λ μ±μμ Έ μλ κ²½μ°
μ°μ μμ ν
:μ°μ μμκ° λμ μμκ° λ¨Όμ λκ°λ ν
ν
:μμ μ΄μ§νΈλ¦¬μ μΌμ’ μΌλ‘ μ°μ μμ νλ₯Ό ꡬννλ μλ£κ΅¬μ‘°
μμκ° μ½μ , μμ λ λλ§λ€ λ°λ‘ μ λ ¬λλ νΉμ§μ΄ μλ€.
νμ μ’ λ₯
- μ΅λ ν
: λΆλͺ¨ λ Έλμ ν€ κ°μ΄ μμ λ Έλμ ν€ κ°λ³΄λ€ κ°κ±°λ ν° κ²½μ°
- μ΅μ ν
:λΆλͺ¨ λ Έλμ ν€ κ°μ΄ μμ λ Έλμ ν€ κ°λ³΄λ€ κ°κ±°λ μμ κ²½μ°
νΈλΌμ΄
:λ¬Έμμ΄μ μ μ₯νκ³ ν¨μ¨μ μΌλ‘ νμνκΈ° μν νΈλ¦¬ ννμ μλ£κ΅¬μ‘°
νΉμ§
- κ²μμ΄ μλμμ±, μ¬μ μ°ΎκΈ° λ±μ μμ©λ μ μλ€.
- λ¬Έμμ΄μ λΉ λ₯΄κ² μ°Ύμ μ μλ€.
- μμ λ Έλλ₯Ό κ°λ¦¬ν€λ ν¬μΈν°λ₯Ό λͺ¨λ μ μ₯ν΄μΌ νκΈ° λλ¬Έμ μ μ₯ 곡κ°μ λ§μ΄ μ¬μ©νλ€.
πλ°°μ΄ μ
μλ£κ΅¬μ‘° μ΄λ ΅λ€~~ κ°μλ€μΌλ©΄ μΌμ κ·Έλ κ΅° νκ³ μ΄ν΄λμ§λ§ λ¬Έμ λ‘ λ§λλ©΄?? μ΄κ² λ¬΄μ¨ μ리μ§?? μΆμ΄ μ§λ€. μ§μ ꡬνν΄λ³΄λ©΄μ μ΅μν΄μ§κ³ λ¬Έμ λ λ§μ΄ νμ΄λ΄μΌ ν κ² κ°λ€.
π»μμΌλ‘ λ°°μ°κ³ μΆμ κ²
-μλ£κ΅¬μ‘° 볡μ΅νκΈ°
μ°Έκ³ μλ£
-νλ‘κ·Έλλ¨Έμ€ κ°μ
-https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html