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에서 특정 값을 가진 노드를 찾는..

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