Develog

🎯 B-Tree & B+Tree B-Tree와 B+Tree는 대용량의 데이터를 관리하기 위한 자료구조로, 데이터베이스나 파일 시스템에서 주로 사용됩니다. B-Tree란? 자식 노드의 개수가 일정하게 유지되는 트리입니다. 이진 탐색 트리의 일반화된 형태로, 노드당 키값이 여러개 저장됩니다. B-Tree는 매우 균형잡힌 트리로, 트리의 높이가 작아 검색 시간이 빠릅니다. B-Tree는 블록 단위로 데이터를 저장하는데, 이는 대용량 데이터 처리에 용이합니다. B+Tree란? B-Tree의 변형으로, 내부 노드에는 키값만 저장하고, 리프 노드에만 데이터를 저장합니다. 이로 인해 리프 노드의 개수가 많아지며, 대용량 데이터를 처리하는 데 더욱 효과적입니다. 또한, 범위 검색에 용이하며, 인덱스를 이용한 검색에도 ..

🎯 Binary Search Tree Binary Search Tree(BST, 이진 탐색 트리)는 이진 트리의 일종으로, 모든 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값을 가진 노드들이, 모든 오른쪽 서브트리에는 해당 노드보다 큰 값을 가진 노드들이 저장되어 있는 이진 트리입니다. Binary Search Tree의 특징 이진 트리의 구조를 따르고 있으므로, 모든 노드의 자식 노드의 수가 최대 2개입니다. 모든 왼쪽 서브트리의 노드들은 해당 노드보다 작은 값을 가지고 있으며, 모든 오른쪽 서브트리의 노드들은 해당 노드보다 큰 값을 가지고 있습니다. 중복된 값을 가지는 노드를 허용하지 않습니다. Binary Search Tree의 주요 연산 탐색(Search) BST에서 특정 값을 가진 노드를 찾는..

🎯 Hash 해시(Hash)는 데이터를 저장하고 검색하기 위한 자료구조 중 하나입니다. 해시는 데이터의 고유한 특정 값(키, Key)을 해시 함수(Hash Function)를 사용하여 계산한 후, 그 결과값을 배열의 인덱스로 사용해 데이터를 저장합니다. 이렇게 저장된 데이터는 O(1)의 시간 복잡도로 검색할 수 있으므로 매우 빠른 검색이 가능합니다. 해시 충돌(Hash Collision) 해시 충돌이란 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다. 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다. 해시 충돌은 해시 함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리며, 따라서 해시..

🎯 Heap Heap(힙)은 최대 값 또는 최소 값을 빠르게 찾기 위한 자료구조입니다. 일반적으로 우선순위 큐(Priority Queue)와 같이 사용됩니다. 부모 노드와 자식 노드 간의 크기 관계를 이용하여 효율적인 삽입, 삭제, 탐색 연산을 수행할 수 있는 트리 기반의 자료구조입니다. Heap의 구조 Heap은 완전 이진 트리(Complete Binary Tree)의 형태를 갖고 있습니다. 완전 이진 트리는 모든 레벨에서 노드들이 꽉 차있고, 마지막 레벨에서는 왼쪽부터 순서대로 채워져 있습니다. Heap은 크게 Max Heap과 Min Heap으로 나눌 수 있습니다. Max Heap은 부모 노드가 자식 노드보다 큰 값을 가지는 Heap이고, Min Heap은 부모 노드가 자식 노드보다 작은 값을 가지..

🎯 LinkedList LinkedList(링크드리스트)는 자료를 연속된 메모리 공간이 아닌, 각각의 노드가 자신의 다음 노드를 가리키는 방식으로 구현된 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(주소)로 구성되어 있습니다. LinkedList는 자료구조의 개념을 이해하기 쉬우며, 추가, 삭제 작업이 빈번한 상황에서는 좋은 성능을 보입니다. 그러나 검색을 빈번하게 수행해야 하는 경우에는 효율성이 떨어지기 때문에, 검색 작업이 더 많은 상황에서는 다른 자료구조를 선택하는 것이 좋습니다. LinkedList의 구조 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. LinkedList 장단점 ⭐️ LinkedList 장점 삽입과 삭제가 용..

🎯 Trie 트라이(Trie)는 검색 트리의 일종으로, 문자열 탐색에 사용되는 자료 구조입니다. 트라이는 문자열을 이진 검색 트리(Binary Search Tree)처럼 저장하지 않고, 각 노드의 문자열을 표현합니다. 이러한 방식으로 트라이는 문자열 검색 및 삽입에서 높은 성능을 보이며, 특히 문자열 검색에 대해 O(m)의 시간 복잡도를 가집니다. (m은 검색하는 문자열의 길이입니다.) Trie의 구조 ⭐️ {"A", "to", "tea", "ted", "ten", "i", "in", "inn"} 을 트라이로 구현 트라이는 문자열을 탐색하기 위한 자료구조이므로 문자열 탐색을 위해서는 다음 글자에 해당하는 노드를 타고 따라가면 된다. 또 트라이의 중요한 속성 중 하나는 루트에서부터 내려가는 경로에서 만나는..