트리

트라이 트리(Trie Tree)? 트라이 트리는 문자열 검색을 빠르게 해주는 트리 형태의 자료구조이다. radix tree, prefix tree, retireval tree 라고도 한다. 여기서 트라이(Trie)는 retireval에서 따온 단어이다. 구현 위 그래프 처럼 car, cb, do, dog라는 단어를 저장한다고 가정한다. 먼저 노드를 하나 만들어 주어야 한다. import java.util.HashMap; import java.util.Map; public class Node { private final Map children; private boolean endOfWord; public Node() { children = new HashMap(); } public Map getChildr..

문제 트리에서 두 점 사이의 거리가 가장 긴 길이를 트리의 지름이라 하는데 트리의 지름을 구하는 문제이다 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q1167 { private static List tree; private static boolean[] visited; private static int maxVertex; private static int max; public static void main(String[] args) throws IOException { BufferedReader br = new..

신장 트리(Spanning Tree)? Spanning Tree는 그래프 내의 모든 정점을 연결하고 사이클이 없는 그래프이다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 특징 DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다. 하나의 그래프에는 많은 신장트리가 존재할 수 있다. Spanning tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안된다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결한다. 최소 신장 트리(MST, Minimum Spanning Tre..

세그먼트 트리? 여러 개의 데이터가 존재할 때 특정 범위의 합을 구하는데 사용하는 자료구조이다. 트리 종류 중에 하나로 이진트리의 형태이다. 0 1 2 3 4 5 6 7 8 9 5 6 9 3 8 2 5 1 4 7 위의 데이터에서 1부터 7까지의 합을 구한다 했을 때, 일반적으로 데이터를 하나씩 돌면서 더하면 O(N)의 시간이 걸린다. 하지만 세그먼트 트리를 사용하면 O(logN)의 시간에 구할 수 있다. 구현 세그먼트 트리 생성 먼저 전체 원소를 더한 값을 최상단 노드에 넣는다. 이때, 최상단 노드의 인덱스는 1을 부여한다. 트리를 구현하다보면 알겠지만, 양쪽 자식노드의 인덱스를 부여할 때 0부터 시작하는 것보다 1부터 시작하는 것이 편하다. 왼쪽자식노드 = 부모노드*2, 오른쪽자식노드 = 부모노드 * ..

이진 탐색 트리(Binary Search Tree)? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. 각 노드에 중복되지 않는 키가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 서브 트리는 각각이 다시 이진탐색트리여야 한다. 이진탐색트리는 이진탐색(Binary Search)과 연결리스트(Linked List)를 결합한 자료구조이다. 이진탐색트리(BST)는 이진탐색의 빠른 탐색 시간과 연결리스트의 빠른 삽입/삭제의 장점들을 가져왔다. 이진탐색은 탐색 시간이 O(log n)으로 빠르지만 삽입/삭제가 불가능하다. 또 연결리스트의 경우, 삽입/삭제는 O(1)이지만..