쓰리까지 오다니... 길어지면 가독성이 떨어질까봐 나누다보니 이렇게 되었다.
뭐 근데 워낙 내용도 많고해서 이정도로 나누긴 해야한다.
글에 담지 못한, 내가 모르는 내용도 많으리라 생각되니 쓰리도 사실 부족하다.
여튼 트리관련 글의 마지막 글이다.
Priority Queue(우선순위 큐)
Binary Heap이 Binary Search 와 다른 점을 이해하려면 Priority Queue를 알아야한다.
Priority Queue는 우선 Queue와는 다르다.
FIFO의 룰을 가진 Queue와는 달리 더 높은 가치가 있는 data를 먼저 보내주는 것이 Priority Queue이다.
밑의 Priority Queue의 insert과정을 보낸 알 수 있을 것이다.
이처럼 값이 insert 되면서 동시에 정렬이 되기 때문에 data의 우선순위를 아는데 용이하다.
장점
Better than O(n)
priority
Flexible Size
Fast insert
단점
Slow lookup
관련 포스트 : https://www.geeksforgeeks.org/implementation-priority-queue-javascript/
Trie (트라이)
data searching 에 주로 사용되는 tree이다.
주로 string 문자열 search에 쓰인다.
Trie는 Binary Tree는 아니다. 찾는 문장, 단어에 따라 노드를 따라가서 전체 문자열을 찾는다.
구글 검색창에 A를 치면 ARE, AS 등이 연관으로 나오는 이유 -> 바로 이 Trie 덕분이다.
시간복잡도
시간복잡도는 특이하게 O(단어의 길이)이다.
BUT
공간복잡도에서는 이미 쓴 단어를 두번 저장할 필요가 없기 때문에 많은 이득을 볼 수 있다.
여기까지 트리에 대해 알아보았다. 쉽지 않는 내용들이 포함되어 있지만 기본적으로 모든 트리들의 존재이유는 이해하기 어렵지 않았다.
참고
Udemy " Master the Coding Interview: Data Structures + Algorithms " - Zero To Mastery
