✍️ 이론/자료구조, 알고리즘

[자료구조] 트리(Tree) - 트라이 트리(Trie tree)

아래의 영상들을 바탕으로 작성되었습니다. 좋은영상 감사합니다. Trie(트라이) Tree에 대해서 - https://youtu.be/TohdsR58i3Q Trie - Insert and Search | GeeksforGeeks - https://youtu.be/dUBkaqrcYT8 0. 트라이 트리(Trie tree)란? (2023.03.16 수정) 문자열 검색을 빠르게 해주는 이진 검색 트리 구조. 한 레벨당 한 문자씩 저장되므로 M이 문자열의 최대 길이라면 문자열 검색시 시간복잡도는 O(Mlogn) 다. 트라이를 이용하면 시간복잡도 O(M)이 걸리는 문자열 검색구조를 만들 수 있다. 참고 -> https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%..

[자료구조] 트리(Tree) - 이진 힙(Binary Heaps)

아래의 유툽영상을 바탕으로 작성되었습니다. 좋은영상 감사합니다. Binary Heaps (Min-Heaps and Max-Heaps) - https://youtu.be/jfwjyJvbbBI 0. 힙(Heaps)란? 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위한 완전 이진 트리를 기본으로 한 자료구조. root에 가장 작은 값이 오면 최소 힙(min heap), root에 가장 큰 값이 오면 최대 힙(max heap) 1. 최소 힙에 노드 삽입하기(Insert) 1. 완전 노드의 맨 끝(leaf)에 노드를 추가하되, 완전 이진 트리(Complete binary tree)를 유지해야 하므로 마지막 레벨의 왼쪽부터 추가. 2. 부모노드 > 새노드 라면 부모와 새노드의 자리를 바꿈. 3. 부모노드 < 새..

[자료구조] 트리(Tree) - 트리의 종류, 3가지 순회방법

아래의 유툽영상을 바탕으로 작성되었습니다. 좋은영상 감사합니다. Tree의 종류 : https://youtu.be/LnxEBW29DOw 0. 트리(tree)란? 즉 Array, LinkedList, Stack, Queue같이 선형구조가 아닌, 부모자식의 관계를 가지는 계층형 그래프. 1. 이진 트리(Binary tree) Binary tree : 부모 노드가 자식 노드를 최대 2개씩만 갖고있는 트리. Ternary tree : 자식 노드를 2개 이상 갖고 있는 트리 2. 이진 검색 트리(Binary Search Tree) Binary tree : 노드들간의 대소관계는 고려하지 않는다. Binary search tree : left child와 그 이하 노드들의 데이터가 현재 노드(부모 노드)의 데이터 보..