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