공영재의 개발일지

B-tree란? B-tree는 Self-balanced Tree 중 가장 유명한 자료구조입니다. Balanced-tree를 의미하며, 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조입니다. 즉, 하나의 노드에 하나의 데이터를 저장하는 다른 Self-Balanced Tree와 달리, 하나의 노드에 여러개의 데이터를 저장하는 방식으로 Tree의 height를 줄여 탐색 시간을 더 획기적으로 줄이도록 고안된 트리입니다. (B-tree와 B+tree, B*tree가 있지만 일반적으로 B tree라 함은 B-tree를 의미합니다.) 이렇게 고안된 트리를 유지하기 위한 몇가지 규칙이 있습니다. 1. 노드 안에 k개의 데이터가 있다면 자식 노드 수는 k+1개여야 한다. 첫..

Red-Black tree란? Red-Black tree(R-B tree)는 AVL tree, Splay tree와 같은 Self-balanced Binary Search Tree입니다. Red-Black tree는 말그대로 모든 노드가 빨간색과 검정색으로 표현됩니다. 이러한 R-B tree는 균형을 유지하기 위해 아래 다섯가지 조건을 만족해야 합니다. 1. 모든 노드는 빨간색 혹은 검은색이어야 합니다. 2. 루트 노드는 검은색이다. 3. 모든 NIL은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 리프 노드) 4. 빨간색 노드의 자식은 반드시 검은색이다. 5. NIL에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. Red-Black tree의 원..

Splay tree란? Splay tree는 이진검색트리(Binary Search Tree)의 한 종류로, 다른 BST(AVL tree, R-B tree 등)보다 구현이 쉽고, 연산을 amortized O(logn)의 시간복잡도로 수행할 수 있습니다. amortized O notation은 일반적으로 사용되는 big-O notation과 달리, 시간 복잡도를 실행 시간의 상한 점근이 아닌, 최악의 경우에 대한 해당 연산의 평균 시간복잡도를 나타냅니다. 따라서 최악의 경우에서 연산 시간복잡도가 O(logn)임을 보장한다는 의미라고 생각하시면 됩니다. Splay tree는 삽입, 삭제, 검색의 연산을 수행한 뒤, splay를 통해 최근에 접근한 노드를 루트에 위치시켜 트리를 재구성합니다. 즉, 자주 탐색하는..

AVL Tree란? AVL 트리란 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)의 한 유형입니다. Adelson-Velsky와 Landis가 1962년에 발명하였으며, 이들의 앞글자를 따서 이름을 붙였습니다. AVL 트리는 각 노드의 서브트리 높이 차이가 최대 1을 유지하도록 스스로 균형을 유지하는 트리인데, 이 서브트리의 높이 차이를 균형 계수(Balance Factor, BF)라 합니다. 그렇기에 삽입과 삭제 연산을 수행할 때마다 트리의 균형 계수를 체크하고, 균형 계수가 1보다 커질 때 회전(Rotation) 연산을 통해 균형을 유지합니다. Binary Search Tree는 불균형할 때 탐색 성능이 O(logn)에서 O(n)으로 떨어지는 문제가 있었는데, ..

Graph란? 그래프란 정점(Vertex)와 간선(Edge)을 모아놓은 자료구조입니다. 그래프는 사이클이 가능하고, 방향 그래프와 무방향 그래프가 모두 존재합니다. 이러한 점에서 그래프가 트리 구조의 상위 집합 개념이라 볼 수 있습니다. 무방향 그래프에서 하나의 정점에 인접한 정점의 수를 차수(degree)라고 하며, 간선에 의해 직접 연결된 정점을 인접 정점(adjacent vertex)라고 합니다. 이러한 정점들을 지나는 경로가 같은 간선을 지나지 않을 때, 단순 경로(simple path)라고 합니다.(0 > 1 > 2 > 3) 그래프는 방향 그래프/무방향 그래프 외에도 간선에 가중치를 넣어 정점 이동 시 비용을 부과하는 가중치 그래프, 모든 정점에 경로가 존재하는 연결 그래프와 특정 정점에 경로가..

Hashing이란? Hash Table을 알기 전에 Hashing의 개념부터 이해해야 합니다. Hashing이란 임의의 값을 Hash함수를 이용해서 고정된 크기의 값으로 변환시키는 작업을 의미합니다. Hash함수는 아래와 같은 종류가 있습니다. Division Method: 인풋값을 테이블의 크기로 나누어 모듈러 연산을 통한 나머지를 사용. 이때 테이블의 크기는 소수(Prime Number)여야 나머지 비트를 고려하여 효율적으로 해싱할 수 있음. Digit Folding: 키의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용 Multiplication Method: 키값 K와 0과 1사이의 실수 A, 임의의 수 m을 사용하여 kAmod1의 연산을 통해 kA의 소수점 이하 부..

Heap이란? 힙은 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리의 일종입니다. 완전이진트리란, 왼쪽부터 차례로 마지막 레벨의 노드를 제외한 모든 노드가 채워져있는 트리입니다. 최솟값이나 최댓값을 찾기 위해 배열은 O(n)의 시간이 걸리는 반면, 힙은 O(log2n)의 시간이 걸리기에 효율적입니다. 힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위해 고안되었습니다. 힙의 형태는 다음과 같습니다. 1. 왼쪽부터 채워진 완전 이진 트리이며 2. 자식보다 부모 노드의 값이 큰 최대힙과 자식보다 부모노드의 값이 작은 최소힙이 있다. 탐색을 위한 이진탐색트리(BST)와 다르게, 힙은 최솟값과 최댓값을 찾기 위함입니다. 이때 두 자료구조의 차이점은 BST는 왼쪽 자식 노드 - 부모 ..

Tree란? Tree란 노드와 브랜치를 이용하는 비선형의 자료구조로, 계층적인 구조를 표현하는데 사용됩니다. 예로 컴퓨터에서의 디렉토리 경로도 Tree 구조를 가지고 있습니다. 위 그림의 A, B 등을 각각 노드라 칭하고, 상위 계층의 노드가 없는 A 노드를 루트 노드라 합니다. A-B / B-E와 같이 수직 관계를 가지는 노드를 각각 부모 노드, 자식 노드라 하며 같은 부모를 가지는 B-C / E-F 등을 형제 노드라 부릅니다. 각 노드를 연결하는 선을 브랜치(혹은 엣지)라고 부릅니다. Tree에서 노드 Depth는 루트에서 해당 노드까지 거치는 edge의 수를 의미합니다. 노드 Level은 특정 Depth를 가지는 집합 (Level 1 = {B, C})을 의미합니다. 노드 Degree는 자식 노드의 ..

Queue란? Queue란 한쪽 끝에서 삽입이 이루어지고 반댓쪽 끝에서 삭제가 이루어지는 형태의 자료구조로, 가장 마지막에 들어온 데이터가 가장 늦게 삭제됩니다. 이러한 구조를 선입선출, FIFO(First In First Out)이라 합니다. Queue는 enQueue(item)와 deQueue()로 데이터의 삽입 및 삭제가 가능합니다. 처음 요소를 front, 마지막 요소를 rear라 칭하며 Qpeek()을 통해 front 요소를 삭제하지 않은 채로 return 할 수 있습니다. Array나 Linkedlist를 통해 Queue를 구현할 수 있습니다. Queue의 종류 Queue의 종류로는 선형 Queue와 원형 Queue가 있습니다. 그 외에도 다른 Queue들이 있지만 우선 위 두가지 Queue에..

Stack이란? Stack은 데이터를 차곡차곡 쌓아 놓은 형태의 자료구조로, 가장 마지막에 삽입된 데이터가 가장 먼저 삭제됩니다. 이러한 구조를 후입선출, 즉 LIFO(Last In First Out)이라 합니다. Stack의 연산은 크게 push(item), pop()으로 이루어집니다. 즉 pop()을 실행하면 마지막으로 push로 넣은 item이 나옵니다. 그 외에도 Peek(), isFull(), isEmpty() 등의 함수가 있습니다. Peek() 마지막으로 push한 item을 빼지않고 출력만 해주는 함수이고, isFull()은 stack overflow를 방지하기 위해 stack이 꽉 찼는지 확인할 때 쓰는 함수입니다. isEmpty()는 반대로 스택이 비어있는지 확인할 수 있고, boolea..