서론B Tree와 B+ Tree는 이진 탐색 트리를 확장해 하나의 노드가 2개 이상의 자식을 가질 수 있게 만든 트리이며 주로 데이터베이스, 파일 시스템에서 사용된다. 하드 디스크는 블록 단위로 읽기/쓰기 작업을 수행한다. DB의 모든 행은 블록에 저장된다. 만약 특정 행을 조회하는 쿼리를 수행하려면 행이 저장된 모든 블록을 모두 탐색해야하는데 이는 비효율적이다. 그래서 인덱스를 사용한다. 행의 키를 키로, 블록 주소를 값으로 갖는 인덱스를 사용한다. 인덱스가 저장된 블록 + 1개의 행이 저장된 블록만 탐색하면 되므로 탐색할 블록 개수가 줄어든다. 인덱스를 위한 인덱스행이 많아지면 인덱스 블록 개수도 증가한다. 때문에 인덱스를 위한 인덱스(high level index)를 둔다. DB 행이 증가할수록 ..
해시인덱스의 범위가 상당히 큰데에 비해 사용되는 공간이 적은 경우를 생각해보자. 예를 들어 인덱스 범위가 1 ~ 1억인 경우 1억 크기 배열을 사용해야하는데 이는 공간 낭비이다.또한 인덱스가 정수가 아닌 문자열이나 객체인 경우 어떻게 해야할까? 이 경우 해시 함수와 해시 테이블을 사용할만 하다. 키로 원소를 O(1)에 찾는 검색 알고리즘해시 테이블 - 원소를 저장하고 있는 공간(배열)해시 함수 - 키를 해시 테이블의 인덱스로 바꾸는 함수. 키를 해시 테이블 인덱스로 쓸 수 있다면 해시 함수가 필요 없겠지만 보통 키의 범위가 너무 크고, 정수형이 아닐기 있기에 변환 함수인 해시 함수가 필요하다. 해시 함수의 결과값을 해시 값이라 한다.충돌서로 다른 키의 해시 값이 동일 할 때 충돌이 발생했다고 한다. 키의..
Heap힙은 힙 속성을 만족하는 완전 이진 트리(이진 힙의 경우)이다. 우선 순위가 가장 높은 원소를 빠르게 찾는 용도로 사용된다. 힙을 사용하면, 원소를 추가하는 연산, 가장 우선순위가 높은 연산을 O(logN)으로 수행할 수 있다. 우선순위가 가장 높은 수가 가장 큰수라면 최대힙, 가장 작은 수라면 최소힙이라 부른다. 힙 속성 : 부모 노드는, 항상 자식 노드보다 우선순위가 높다.따라서 힙은 힙 속성, 완전 이진 트리를 만족해야한다.BBST를 쓰면 안되나?BBST보다 힙이 훨씬 빠르다. BBST도 같은 시간 복잡도를 가지며, 심지어 우선 순위가 가장 낮은 원소도 가져올 수 있지만, 같은 시간 복잡도라도 힙은 간단한 작업을 수행하기에 더 빠르다. BBST는 트리의 균형을 맞추기 위해 복잡한 작업을 수행..
Segment Tree구간 트리(Segment Tree)는 저장된 자료의 특정 구간 질의를 빠르게 대답하기 위해 저장된 자료를 전처리한 트리를 말한다. 흔히 구간 트리는 일차원 배열의 특정 구간 질의를 빠르게 대답하는데 사용된다. 예를 들어 [1, 7, 5, 3, 2] 라는 일차원 배열이 있을 때 [1, 2] 구간의 최소치를 찾는 연산을 해야 한다. 이를 연산하는 간단한 방법은 구간의 시작부터 끝까지 순회하면서 최소치를 찾으면 되며 시간 복잡도는 O(N)이 된다. 반면 구간 트리를 한 번 만들어두면 위 연산을 O(log N)으로 할 수 있다. 구간 트리의 핵심 아이디어는 배열 구간에 대한 이진 트리를 만드는 것이다. 구간 트리의 노드는 구간을 표현한다. 루트 노드는 항상 배열의 전체 구간 [0, n-1]..
Binary Search Tree (BST) 데이터 탐색 알고리즘으로 이진 탐색 알고리즘이 있다. 탐색 범위를 반으로 줄이면서 탐색하는 알고리즘이다. 정렬된 배열에서 이진 탐색 알고리즘을 적용해 O(log N)의 시간복잡도로 탐색할 수 있지만 배열의 원소를 추가, 삭제하는데 O(N)의 시간복잡도가 든다는 단점이 있다. 이를 극복하기 위해 BST를 사용한다. 균형 잡힌 BST(BBST)라면 탐색, 삽입, 삭제의 시간 복잡도를 O(log N)으로 만들 수 있다. BST는 이진 트리에 속하며 이진 탐색을 목적으로 하는 트리다. BST의 모든 노드는 아래의 규칙을 갖는다. 각 노드의 왼쪽 서브 트리에는 해당 노드의 원소보다 작은 원소를 가진 노드들이, 오른쪽 서브 트리에는 해당 노드의 원소보다 큰 원소를 가진 ..
트리 트리는 계층 구조를 표현하는 자료구조이다. 트리는 다양한 목적으로 사용되어 다양한 종류의 트리들이 등장했다. 현실 세계 계층 구조 표현 이진 검색 트리 힙 세그먼트 트리 유니온-파인드 트라이 등등 트리 용어 node(노드) : 트리 구성 요소 edge(간선) : 노드와 노드를 연결한 선 parent : 두 노드가 간선으로 연결되었을 때 상위 노드 child : 두 노드가 간선으로 연결되었을 때 하위 노드 sibling : 같은 부모를 가지는 자식 노드들 ancestor : 부모 노드와 그 부모 노드의 상위 노드들 descendant : 자식 노드와 그 자식 노드의 하위 노드들 root : 부모가 없는 최상위 노드 leaf : 자식이 없는 노드 Internal : 리프 노드가 아닌 노드 depth :..
LinkedList LinkedList는 리스트의 한 종류이다. 노드들이 물리적인 메모리 주소상으로 연속되어 있지 않지만 노드가 다음 노드로 갈 수 있는 포인터를 가짐으로써 노드들이 논리적으로 연속되어 있다. 연결 리스트에서 하나의 원소를 노드라고 한다. 노드는 데이터 필드와 링크 필드로 나뉘는데 데이터 필드는 리스트에 저장될 원소의 값을 저장하며 링크 필드는 다음 노드의 참조값을 저장한다. 연결리스트의 가장 큰 장점은 원소의 삽입, 삭제의 시간복잡도가 O(1)이다. 때문에 원소의 삽입, 삭제가 빈번하면 연결 리스트 사용을 고려할만하다. 단점은 특정 위치의 원소를 찾아가는 시간 복잡도가 O(N)이다. 배열(배열 기반 리스트)와 달리 랜덤 엑세스가 안되기 때문이다. 연결 리스트의 종류 연결 리스트는 총 세..
List 리스트는 데이터를 일렬로 저장하는 선형 자료구조이다. 리스트는 배열 기반 리스트(동적 배열)와 연결 리스트로 나뉜다. 배열 기반 리스트 : 노드들이 물리적인 메모리 주소상으로 연속되어 있다. 연결 리스트 : 노드들이 물리적인 메모리 주소상으로 연속되어 있지 않지만, 노드 안에는 다음 노드로 갈 수 있는 포인터가 있다. 또한 리스트로 비선형 자료구조를 표현할 수 있다. 연결 리스트로 트리 구현, 배열로 그래프 구현, 배열로 이진 트리 구현 등이 그 예시이다. 배열 기반 리스트 배열의 가장 큰 문제점은 한번 할당받은 후 배열의 크기가 변하지 않는다는 점이다. 이를 극복하기 위해 배열 기반 리스트를 사용한다. 배열 기반 리스트는 배열에 노드를 저장하며 배열 크기를 조절하는 resize 연산을 추가했다..
