[데브코스 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

-https://yoongrammer.tistory.com/68