트리 (2) 썸네일형 리스트형 트라이(Trie) 트라이(Trie) 개념 문자열의 집합을 표현하는 트리 자료구조 문자열의 검색을 빠르게 해주는 자료구조 사용 목적 두 문자열을 비교하는 경우엔 단순한 비교를 통해 진행하기 때문에 문자열의 길이만큼 시간 소요 => 문자열의 길이 O(M) * 문자열의 총 개수 O(logN) => O(Mlog(N)) 특징 루트에서부터 내려가는 경로에서 만나는 글자들을 모으면 문자열의 접두사를 얻을 수 있다. 리프 노드의 개수는 문자열의 총 개수와 동일하다. 장단점 장점 문자열 추가와 탐색이 모두 O(M)만에 가능 단점 각 노드가 자식에 대한 포인터를 저장하므로 메모리가 많이 필요 사용 예시 검색어 자동완성, 사전에서 단어 찾기, 문자열 검사 참고 https://nooblette.tistory.com/entry/%ED%8A%B8.. 힙&이진탐색트리 트리(Tree) 루프를 갖지 않고 연결된 무방향 그래프 구조 트리내에 또 다른 트리가 있는 재귀적 자료구조 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며 모든 자식 노드는 하나의 부모 노드만 갖는다. 사용 예: 디렉터리 구조, 조직도 힙(Heap) 개념 및 특징 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 **완전 이진트리란? 단 두개의 자식 노드만 갖는 이진 트리 중 노드가 왼쪽부터 차례로 채워져 있는 트리 A가 B의 부모노드이면, A의 키 값과 B의 키 값 사이에는 대소관계가 성립한다. => 형제 사이에는 대소관계x 부모노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전 이진 트리를 '최대 힙(max heap)', 작거나 같은 완전 이진 트리를 '최소 힙(mi.. 이전 1 다음
