자료구조

세그먼트 트리? 여러 개의 데이터가 존재할 때 특정 범위의 합을 구하는데 사용하는 자료구조이다. 트리 종류 중에 하나로 이진트리의 형태이다. 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)이지만..