728x90 데이터구조4 [알고리즘] 레드-블랙 트리: 이진 탐색 트리에 균형을 더한 자료구조 JS로 레드 블랙트리 구현하기 레드-블랙 트리는 이진 탐색 트리에 균형을 더한 자료구조입니다. 이 트리는 각 노드가 블랙 또는 레드의 색을 가지며, 몇 가지 규칙에 따라 구성됩니다. 이 규칙들은 트리가 균형을 유지하도록 하며, 검색, 삽입, 삭제 등의 연산에서 최악의 경우 시간 복잡도를 O(log n)에 유지할 수 있도록 합니다. 레드-블랙 트리의 규칙1. 노드 색깔각 노드는 블랙 또는 레드의 색깔을 가집니다.2. 루트 노드루트 노드는 무조건 블랙입니다.3. 새로운 추가 노드새로운 추가 노드는 레드로 추가됩니다.4. 연속된 레드 노드연속된 레드 노드가 올 수 없습니다. 즉, 부모-자식 간에 레드-레드 연결이 발생할 수 없습니다.5. 자식 노드레드 노드의 자식은 모두 블랙입니다.6. 블랙 노드 수루트에서 리프(leaf) 노드까지의 경로.. 2024. 5. 6. [알고리즘] 트라이(Trie) 자료구조: 문자열 검색의 효율적인 해결책 문자열 검색은 컴퓨터 과학에서 중요한 문제 중 하나입니다. 특히, 대용량의 텍스트 데이터베이스나 자연어 처리 시스템에서 문자열을 효율적으로 찾아야 할 때 매우 중요한 역할을 합니다. 이를 위해 다양한 자료구조가 고안되었는데, 그 중에서도 트라이(Trie)는 문자열 검색을 위한 효율적인 해결책으로 널리 사용되고 있습니다. 이번 글에서는 트라이의 원리와 구현, 그리고 실제 응용 사례에 대해 알아보겠습니다.트라이(Trie)란?트라이는 검색 트리의 일종으로, 일련의 문자열을 저장하고 탐색하는 데 사용됩니다. 트라이는 각 문자열을 공통된 접두사(prefix)를 기준으로 묶어서 트리 구조로 나타냅니다. 이를 통해 문자열의 검색이 매우 빠르게 이루어지며, 시간 복잡도는 입력 문자열의 길이에 선형적으로 비례합니다. 즉.. 2024. 5. 5. [알고리즘] 이진 검색 트리(Binary Search Tree, BST)의 이해와 Up & Down 게임 비교 이진 검색 트리란?이진 검색 트리(Binary Search Tree, 이하 BST)는 데이터의 검색 속도를 최적화하기 위해 고안된 데이터 구조입니다. 이 구조에서 각 노드는 최대 두 개의 자식 노드(왼쪽 및 오른쪽)를 가지며, 각 노드는 다음과 같은 특정 규칙을 준수합니다:노드의 왼쪽 하위 트리에 있는 모든 요소는 해당 노드보다 작습니다.노드의 오른쪽 하위 트리에 있는 모든 요소는 해당 노드보다 큽니다.이 규칙은 BST의 모든 레벨에 걸쳐 일관적으로 적용되며, 데이터를 효과적으로 분류하고 검색하는 데 큰 도움이 됩니다. 그림에서 보면 4가 6보다 작기 때문에 왼쪽으록 가게 됩니다. 반면에 2같은 경우는 3보다 크기 때문에 3의 왼쪽으로 와야합니다.이진 검색 트리의 장점 BST의 가장 큰 장점은 탐색 성능.. 2024. 5. 4. [알고리즘] 이해하기 쉬운 트리 자료구조의 속성과 활용 트리 자료구조는 계층적인 구조를 표현하는 데 사용되며, 단방향 그래프의 한 종류로 볼 수 있습니다. 그 모양이 나무와 유사하여 트리라고 불립니다. 이 구조는 하나의 뿌리(root)에서부터 여러 가지 가지(branch)가 뻗어나가는 형태를 가지며, 데이터를 순차적으로 나열하는 선형 구조가 아니기 때문에 비선형 구조입니다. 또한, 트리는 아래로만 뻗어나가기 때문에 사이클이 없습니다.트리 자료구조는 여러 가지 속성을 가지고 있습니다. 루트(Root): 트리의 가장 위에 있는 노드로, 다른 모든 노드들은 이 루트 노드에서부터 시작합니다.노드(Node): 트리의 각 요소를 나타냅니다. 노드는 데이터를 저장하고 다른 노드와 연결된 엣지(Edge)를 가질 수 있습니다.엣지(Edge): 노드와 노드를 연결하는 선입니다.. 2024. 4. 29. 이전 1 다음 728x90
