[자료구조] Set과 Map 근데 이제 해시와 트리를 곁들인
해시맵(Hash Map)은 많이 들어본 개념이다 하지만 해시를 이용한 셋(Set)과 트리를 이용한 셋(set)과 맵(Map)은 뭘까?셋(Set)중복되지 않는 원소들의 집합으로, 특정 원소의 존재 여부를 빠르게 확인할 수 있다.맵(Map)키-값(Key-Value) 쌍으로 데이터를 저장하는 자료구조로, 각 키는 유일하며 키를 통해 값에 빠르게 접근할 수 있다.트리를 이용한 Set과 Map트리를 이용한 Set과 Map은 이진 탐색 트리(Binary Search Tree, BST), 특히 균형 이진 탐색 트리(예: 레드-블랙 트리)를 사용하여 구현된다.특징정렬된 데이터: 원소들이 자동으로 정렬된 상태로 저장된다.탐색, 삽입, 삭제의 시간 복잡도: 평균 및 최악의 경우 모두 O(log n)이다다.순회가 용이: 중..
[자료구조] 트리(Tree) 시리즈 5: 레드-블랙 트리(RB-Tree)란?
RB-Tree의 정의와 특성Red-Black Tree(RB-Tree)는 자가 균형 이진 탐색 트리의 한 종류로, 각 노드에 추가적인 비트(색상)를 저장하여 트리의 균형을 유지한다.주요 특성:이진 탐색 트리의 모든 특성을 만족한다.각 노드는 red 또는 black다.트리의 균형을 유지하여 최악의 경우에도 O(log n)의 시간 복잡도를 보장한다.RB-Tree의 규칙과 속성RB-Tree는 다음 규칙을 만족해야 한다:모든 노드는 red 또는 black이다.루트 노드는 항상 black이다.모든 리프 노드(NIL)는 black이다.red 노드의 자식은 모두 black이어야한다. (red 노드는 연속될 수 없다)임의의 노드에서 그 노드의 자손인 리프 노드에 이르는 모든 경로에는 동일한 개수의 black 노드가 있어..
[자료구조] 트리(Tree) 시리즈 4: AVL트리란?(AVL Tree)란?
AVL 트리란?AVL트리는 노드가 추가될 때, 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 트리이다.주요 특징:모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1자동으로 균형을 유지하여 항상 O(log n) 시간 복잡도 보장균형 인수 (Balance Factor)AVL 트리의 핵심은 '균형 인수(밸런스 팩터)'다.균형 인수 = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이이 값은 항상 -1, 0, 1 중 하나여야 한다.이 범위를 벗어나면 재조정(rebalancing)을 해야한다.AVL 트리 연산1. 검색 (Search)일반 이진 탐색 트리와 동일한 방식으로 수행된다.2. 삽입 (Insertion)일반적인 BST 삽입 수행삽입 경로를 따라 올라가며 균형 인수 업데..
[자료구조] 트리(Tree) 시리즈 3: 이진 탐색 트리(Binary Search Tree)란?
이진탐색 트리(BST)란?모든 노드가 아래와 같은 특정 순서를 따르는 속성이 있는 이진 트리다각 노드는 최대 두 개의 자식 노드를 가진다왼쪽 서브트리의 모든 노드는 현재 노드보다 작은 값을 가진다오른쪽 서브트리의 모든 노드는 현재 노드보다 큰 값을 가진다중복된 노드가 없어야 한다.BST의 주요 연산 (조회, 삽입, 삭제) 및 시간 복잡도조회 (Search)평균 시간 복잡도: O(log n)최악의 경우 (불균형 트리): O(n)삽입 (Insertion)평균 시간 복잡도: O(log n)최악의 경우 (불균형 트리): O(n)삭제 (Deletion)평균 시간 복잡도: O(log n)최악의 경우 (불균형 트리): O(n)BST의 균형과 불균형 문제BST의 성능은 트리의 균형에 크게 의존한다. 균형 잡힌 BST..
[자료구조] 트리(Tree) 시리즈 2: 이진 트리(Binary Tree)란?
이진 트리란?이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조다.주요 특성:각 노드는 0, 1, 또는 2개의 자식 노드를 가질 수 있다.자식 노드는 일반적으로 왼쪽 자식과 오른쪽 자식으로 구분된다.루트 노드부터 시작하여 계층적 구조를 형성한다.이진 트리의 종류1. 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워진다.2. 포화 이진 트리(Full Binary Tree): 모든 내부 노드가 두 개의 자식을 가지며, 모든 리프 노드가 같은 레벨에 있다.3. 균형 이진 트리(Balanced Binary Tree): 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하다.4. 편..
[자료구조] 트리(Tree) 시리즈 1: 트리(Tree)란?
트리란?트리는 계층적 관계를 표현하는 비선형 자료구조다. 노드(node)들과 그 노드들을 연결하는 간선(edge)들로 구성되어 트리 모양의 형태를 가진다.트리의 구조루트(Root): 트리의 최상위에 있는 노드노드(Node): 트리를 구성하는 각 요소간선(Edge): 노드와 노드를 연결하는 선부모 노드(Parent Node): 서브트리를 가지는 노드자식 노드(Child Node): 부모 노드 밑에 연결된 노드형제 노드(Sibling Node): 부모가 같은 자식 노드들리프 노드(Leaf Node): 자식이 없는 노드내부 노드(Internal Node): 적어도 하나의 자식을 가진 노드서브트리(Sub Tree): 큰트리의 속하는 작은 트리트리의 특징계층적 구조트리는 계층적 구조를 가진다. 하나의 루트 노드에..