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) 해시 충돌이란 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다. 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다. 해시 충돌은 해시 함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리며, 따라서 해시..