📚TIL

day4

트리(Tree)

• 방향 그래프이며 정점을 가리키는 간선이 하나밖에 없는 구조
• root - 가장 상위, node - 각 정점, leaf node - 자식이 없는 정점, level - 루트로 부터의 깊이 값, degree - 한 정점에서 뻗치는 간선 횟수
• 하나의 부모 정점만을 갖기 때문에 정점이 N개인 트리는 반드시 N-1개의 간선을 가지며, 루트에서 특정 정점으로 가는 경로는 유일함
• 트리 종류 : 이진트리, 완전 이진트리, 포화 이진트리, 편향 트리

힙(Heap)

• 우선순위 큐 : 우선순위가 높은 요소가 먼저 나가는 큐의 개념
• 이진트리 형태를 가지며 우선 순위가 높은 요소가 먼저 나가기위해 요소가 삽입, 삭제될 때 바로 정렬되는 것이 특징
• javascript에서는 힙을 직접 구현해서 사용

트라이(Trie)

• 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조
• 검색어 자동완성, 사전 찾기 등에 응용
• L이 문자열의 길이일 때 탐색과 삽입은 O(L)만큼 걸림
• 각 정점이 자식에 대한 모든 링크를 가지고 있기 때문에 저장공간을 많이 사용
• 트라이의 루트는 비어있으며 각 간선(링크)은 추가될 문자를 키로 가짐
• 해시 테이블과 연결 리스트를 이용하여 구현
  
  

🌊하루를 마치며

처음 힙에서 요소를 제거하는 과정이 복잡하여 비효율적이라는 생각을 했는데 과정을 이해하고 생각해보면서 다른 과정들보다 효율적이라는 것을 깨달았다. 또 일상에서 많이 접하던 자동완성 기능이 트라이를 응용하여 만들어 졌다는 것을 처음 알게 된 점이 흥미로웠다.

내일은 과제를 제출한 이후 밀린 강의를 듣고 실습을 진행할 계획이다. 이번주 목표했던 과업들을 주말에 모두 끝낼 수 있었으면 좋겠다..!