[자료구조] 트리(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. 편..