🖥 Computer Science/자료구조

Multiway Search Tree (다원 탐색 트리) / m-way Search Tree (m 분기 탐색 트리) 한 노드가 가질 수 있는 key의 값이 최대 m-1개이고 가질 수 있는 Child의 수가 m개인 트리를 Mulituway Search Tree라 합니다. 이진 트리 : 2-way search tree AVL 트리 : 2-way search tree 2-3 트리 : 3-way search tree 정의는 다음과 같습니다. m-way Search Tree는 다음을 만족하는 검색 트리입니다. 1. Leaf Node를 제외한 모든 노드는 m개 이하의 서브 트리를 가집니다. 2. k개의 자식 노드를 갖는 노드는, k-1개의 요소(key)를 가집니다. 3. 각 노드의 key는 오름차순으로 정렬되어 있..

2-3 Tree 2-3트리는 검색 트리이지만 BST는 아닙니다. 차수가 3인 노드가 존재할 수 있으므로, Binary가 아니기 때문입니다. 2-3 Tree는 트리의 높이가 균형을 이루며 내부노드의 차수가 2 또는 3인 균형 탐색트리입니다. 2-3 Tree 조건 2-3 Tree에는 Internal Node와 External Node의 개념이 존재합니다. Internal Node(내부노드)는 Key가 들어있는 내부 노드이며, External Node(외부노드)는 데이터가 들어있지 않은 노드로써 Internal Node의 Leaf Node의 자식으로 존재하는 가상의 노드입니다. 2-3 Tree에서 각각의 내부 노드는 2-Node 이거나 3-Node 입니다. 중복된 Key는 허용하지 않습니다. 2-Node는 1..

BST의 문제점 일반적인 BST(이진 검색 트리)는 데이터가 삽입되는 순서에 따라 한쪽으로 편향되는 형태로 트리가 형성될 수 있습니다. 예를 들어 입력열이 50 -> 30 -> 100 -> 20 -> 150 인 경우 다음과 같습니다. 그러나 입력열이 20 -> 30 -> 50 -> 100 -> 150 인 경우 다음과 같습니다. 이렇게 BST는 트리의 높이를 $log(n)$ 으로 보장받지 못할 가능성이 있습니다. 트리에서의 성능은 트리의 높이와 연관되어 있습니다. 즉 트리의 높이가 $log(n)$을 보장받지 못한다면, BST의 삽입과 삭제, 검색의 연산 역시 시간복잡도 $O(log(n))$을 보장받지 못합니다. AVL 트리 AVL 트리는 이진 검색 트리(BST)의 한가지 종류로써 스스로 높이의 균형을 잡는..

들어가기에 앞서 해시가 어디에 쓰이는지 알아보도록 하겠습니다. 유튜브를 예시로 생각해 보도록 하겠습니다. 제가 어떤 사람의 동영상을 그대로 제 채널에 올리려고 한다면, 그 순간 바로 유튜브에서 중복되는 동영상이라는 에러 메세지를 보내줍니다. 동영상은 크기도 매우 크고, 그 수도 매우 많습니다. 그렇게 많은 동영상 중에서 어떻게 중복되는 동영상인지를 빠르게 판단할 수 있을까요? 앞으로 살펴볼 자료구조인 해시테이블이 바로 이것을 가능하게 만들어줍니다. Hash Function (해시 함수) 해시 함수 (Hash Function) 또는 해시 알고리즘은 임의의 데이터를 배열의 인덱스로 매핑(변환)하는 함수입니다. 해시 테이블은 배열입니다. 따라서 인덱스를 통해 접근할 때에는 O(1)의 시간복잡도로 매우 빠르게 ..

Deap이란? 완전 이진 트리(Complete Binary Tree)이며, 비어있거나 다음을 만족시키는 자료구조입니다. 1. Root 노드는 아무런 요소를 가지고 있지 않습니다. 2. 왼쪽 서브트리는 min-heap 입니다. 3. 오른쪽 서브트리는 max-heap 입니다. 만약 오른쪽 서브트리가 비어있지 않은 경우 $i_{left}$ 를 왼쪽 서브트리의 임의의 요소라 하겠습니다. $j_{right}$ 를 $i_{left}$ 에 대응되는 우측 서브트리의 요소라고 하겠습니다. 만약 $j_{right}$ 가 존재하지 않는 경우, $j_{right}$ 의 위치는 $i_{left}$ 의 부모(parent)노드에 대응되는max-heap의 원소가 됩니다. 항상 $i_{left}$ 는 $j_{right}$ 보다 작거나..

우선순위 큐 (Priority Queue) 우선순위 큐는 기존 큐와 달리 가장 먼저 들어온 원소가 가장 먼저 제거되지 않습니다. 우선순위 큐에서는 우선순위가 가장 높은 원소부터 제거됩니다. 우선순위 큐의 구현 우선순위 큐는 다양한 방법으로 구현이 가능합니다. 구현 방법 삽입 최댓값 삭제 최솟값 삭제 임의원소 삭제(찾은 후) 검색 정렬되지 않은 ArrayList $$O(1)$$ $$O(n)$$ $$O(n)$$ $$O(n)$$ $$O(n)$$ 정렬되지 않은 LinkedList $$O(1)$$ $$O(n)$$ $$O(n)$$ $$O(1)$$ $$O(n)$$ 정렬된 ArrayList (오름차순) $$O(n)$$ $$O(1)$$ $$O(n)$$ $$O(n)$$ $$O(log\;n)$$ 정렬된 LinkedList ..

힙(Heap)이란? 힙은 기본적으로 완전 이진 트리(Complete Binary Tree)이면서, 성질에 따라 최대 힙(Map Heap)과, 최소 힙(Min Heap), 두 가지 종류로 분류됩니다. 최대 힙 (Max Heap) 1. 완전 이진 트리(Complete Binary Tree)이면서 2. 각 노드의 Key 값이 자식 노드의 Key 값보다 작지 않다. 최초 힙 (Min Heap) 1. 완전 이진 트리(Complete Binary Tree)이면서 2. 각 노드의 Key 값이 자식 노드의 Key 값보다 크지 않다. 참고로 메모리 영영 중, 동적으로 메모리가 할당되는 영역은 대부분 힙 자료구조로 이루어져 있습니다. 힙에서의 삽입 최대 힙 기준으로 설명하겠습니다. 삽입하려는 노드를 가장 마지막에 추가합니..

이진 검색 트리 (Binary Search Tree - BST) 이진 검색 트리는 이진트리(Binary Tree)의 한 종류이며, 비어있거나 다음 조건을 만족해야 합니다. 1. 모든 원소는 Key를 가지고 있으며, 어떠한 원소도 동일한 키를 가지지 않습니다. 즉 Key는 유일합니다. 2. 트리의 루트는 비어있지 않은 왼쪽 서브트리의 있는 Key보다 큰 값을 가집니다. 2. 트리의 루트는 비어있지 않은 오른쪽 서브트리의 있는 Key보다 작은 값을 가집니다. 4. 왼쪽 서브트리와 오른쪽 서브트리는 또다시 이진검색트리입니다. 이진 검색 트리는 AVL트리, 2-3트리, B트리, 레드-블랙 트리 등, 앞으로 배울 여러 트리들의 기본이 되는 자료구조이므로 확실하게 알고 넘어가야 합니다. 시간복잡도 이진 검색 트리는..