해시맵(Hash Map)은 많이 들어본 개념이다 하지만 해시를 이용한 셋(Set)과 트리를 이용한 셋(set)과 맵(Map)은 뭘까?셋(Set)중복되지 않는 원소들의 집합으로, 특정 원소의 존재 여부를 빠르게 확인할 수 있다.맵(Map)키-값(Key-Value) 쌍으로 데이터를 저장하는 자료구조로, 각 키는 유일하며 키를 통해 값에 빠르게 접근할 수 있다.트리를 이용한 Set과 Map트리를 이용한 Set과 Map은 이진 탐색 트리(Binary Search Tree, BST), 특히 균형 이진 탐색 트리(예: 레드-블랙 트리)를 사용하여 구현된다.특징정렬된 데이터: 원소들이 자동으로 정렬된 상태로 저장된다.탐색, 삽입, 삭제의 시간 복잡도: 평균 및 최악의 경우 모두 O(log n)이다다.순회가 용이: 중..

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 노드가 있어..

AVL 트리란?AVL트리는 노드가 추가될 때, 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 트리이다.주요 특징:모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1자동으로 균형을 유지하여 항상 O(log n) 시간 복잡도 보장균형 인수 (Balance Factor)AVL 트리의 핵심은 '균형 인수(밸런스 팩터)'다.균형 인수 = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이이 값은 항상 -1, 0, 1 중 하나여야 한다.이 범위를 벗어나면 재조정(rebalancing)을 해야한다.AVL 트리 연산1. 검색 (Search)일반 이진 탐색 트리와 동일한 방식으로 수행된다.2. 삽입 (Insertion)일반적인 BST 삽입 수행삽입 경로를 따라 올라가며 균형 인수 업데..

이진탐색 트리(BST)란?모든 노드가 아래와 같은 특정 순서를 따르는 속성이 있는 이진 트리다각 노드는 최대 두 개의 자식 노드를 가진다왼쪽 서브트리의 모든 노드는 현재 노드보다 작은 값을 가진다오른쪽 서브트리의 모든 노드는 현재 노드보다 큰 값을 가진다중복된 노드가 없어야 한다.BST의 주요 연산 (조회, 삽입, 삭제) 및 시간 복잡도조회 (Search)평균 시간 복잡도: O(log n)최악의 경우 (불균형 트리): O(n)삽입 (Insertion)평균 시간 복잡도: O(log n)최악의 경우 (불균형 트리): O(n)삭제 (Deletion)평균 시간 복잡도: O(log n)최악의 경우 (불균형 트리): O(n)BST의 균형과 불균형 문제BST의 성능은 트리의 균형에 크게 의존한다. 균형 잡힌 BST..

이진 트리란?이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조다.주요 특성:각 노드는 0, 1, 또는 2개의 자식 노드를 가질 수 있다.자식 노드는 일반적으로 왼쪽 자식과 오른쪽 자식으로 구분된다.루트 노드부터 시작하여 계층적 구조를 형성한다.이진 트리의 종류1. 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워진다.2. 포화 이진 트리(Full Binary Tree): 모든 내부 노드가 두 개의 자식을 가지며, 모든 리프 노드가 같은 레벨에 있다.3. 균형 이진 트리(Balanced Binary Tree): 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하다.4. 편..

트리란?트리는 계층적 관계를 표현하는 비선형 자료구조다. 노드(node)들과 그 노드들을 연결하는 간선(edge)들로 구성되어 트리 모양의 형태를 가진다.트리의 구조루트(Root): 트리의 최상위에 있는 노드노드(Node): 트리를 구성하는 각 요소간선(Edge): 노드와 노드를 연결하는 선부모 노드(Parent Node): 서브트리를 가지는 노드자식 노드(Child Node): 부모 노드 밑에 연결된 노드형제 노드(Sibling Node): 부모가 같은 자식 노드들리프 노드(Leaf Node): 자식이 없는 노드내부 노드(Internal Node): 적어도 하나의 자식을 가진 노드서브트리(Sub Tree): 큰트리의 속하는 작은 트리트리의 특징계층적 구조트리는 계층적 구조를 가진다. 하나의 루트 노드에..